一.栈和队列的定义和特点
1.概述：栈和队列是限定插入和删除只能在表“端点”进行的线性表
2.栈的特点——后进先出（队尾插入和删除），因此，栈也被称为后进先出（Last In First Out）的线性表，简称LIFO结构。
队列的特点——先进先出（队尾插入，队头删除）（可理解为排队）
3.栈的相关介绍
3.1栈的概念：栈是仅在表尾进行插入，删除操作的线性表，表尾（an端）成为栈顶Top，表头（a1端）称为栈底Base，插入元素到栈顶操作称作入栈，从栈顶删除最后一个元素的操作称为出栈 。
3.2【思考】：假设3个元素a，b，c依次入栈，则它们的出栈顺序有几种可能？
【分析】：情况1，a，b，c先入栈，然后出栈情况是cba; 情况2，a入栈出栈，b入栈出栈，c入栈出栈，出栈情况是abc; 情况3，a入栈出栈，b，c入栈，然后c，b出栈，出栈情况是acb。因此按此还可以得到bac;bca等序列。但是同学们可以想一想，根据栈的原理，不可能出现cab的情况。
3.3栈的存储结构：顺序栈或链栈均可，但顺序栈更常见
4.队列的相关介绍
4.1队列的概念：表尾插入，在另一端（表头）删除。因此队列（queue）是一种先进先出（First In First Out）的线性表，简称为FIFO结构。
4.2存储结构：顺序队或链队（以循环顺序更常见）
二.案例的引入（栈）
1.进制转换
1.1转换法则——除以d（进制数），倒序取余。
例：把十进制数220转化为8进制数
因此每次计算的余数入栈（433），然后出栈顺序即为334
1.2.括号的匹配的检验（嵌套性）
如：【{（）}】或{【】（）}为正确格式；而（【）】为错误格式（不能交叉），（【（））为错误格式（少了一个】不能匹配）。
因此：可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。(1)当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号;(2)从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况;(3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
1.3.表达式求值——算符优先算法
介绍：任何一个算术表达式都由操作数（常数、变量)、算术运算符（+、-、*、/)）和界限符(括号、表达式结束符‘#’、虚设的表达式起始符‘#’)组成。后两者统称为算符。
因此算法为：设置两个栈:一个是算符栈OPTR，用于寄存运算符。另一个称为操作数栈OPND，用于寄存运算数和运算结果。求值的处理过程是自左至右扫描表达式的每一个字符，当扫描到的是运算数，则将其压入栈OPND；当扫描到的是运算符时，若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理；若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。继续处理当前字符，直到遇到结束符为止。（比较复杂，后面会详细介绍）
三.栈的表示和操作的实现——顺序栈
（初始化，进栈，出栈，取栈顶元素等）
和线性表一样，我们先介绍对栈的操作函数（抽象数据类型定义）
InitStack(&S) //初始化；构造一个空栈S
DestoryStack（&S） //销毁栈操作
StackEmpty（S） //判断是否为空栈
StackLength（S） //求栈的长度
GetTop（S，&e） //取栈顶元素，用e返回S的栈顶元素（所以e前面要加寻址符）
ClearStack（&S） //栈置空操作
Push（&S，e） //入栈操作，插入元素为e的新的栈顶元素
Pop（&S，&e） //出栈操作，删除S的栈顶元素an，并用e返回其值1.总体介绍 ：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。附设top指针，指示栈顶元素在顺序栈中的位置；另设base指针，指示栈底元素在顺序栈中的位置。但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址，另外用stacksize表示栈可使用的最大容量。
2.入栈出栈的形象介绍
空栈：base==top是栈空标志 栈满top-base==stacksize
栈中元素个数：top-base（两个指针相减代表两个指针间差距几个元素，可以理解为整数相减（但两指针需要指向同一数组）
栈满时的处理方式：（1）报错，返回操作系统，（2）分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈。
因此使用数组作为顺序栈存储方式容易产生溢出，溢出分为两类，上溢：栈已经满了但还要压入元素，下溢：栈已经空了但还要弹出元素。（上溢是一种错误，使问题处理无法进行，而下溢一般认为是一种结束条件）
3.顺序栈的数据类型定义
【4.1】顺序栈的表示
#define MAXSIZE 100 //宏定义，定义栈（数组）的大小
typedef struct{
SElemType *base; //栈底指针
SElemType *top； //栈顶指针
int stacksize; //栈可用最大容量
}SqStack; //typedef之后，用SqStack即可表示整个结构体4.顺序栈的初始化
算法：分配一段空间，将base指针和top指针指向同一位置
【4.2】顺序栈的初始化
Status InitStack(SqStack &S){//构造一个空栈
S.base=new SElemType[MAXSIZE]; //开辟一段空间，这里偷懒用了C++的语法或者：
// S.base=( SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW); //储存空间分配失败，退出
S.top=S.base; //栈顶指针等于栈底指针
S.stacksize=MAXSIZE; //栈容量的定义
return OK;
}
5.判断顺序栈是否为空
算法：顺序栈为空，top指针与base指针相等
【4.3】判断顺序栈是否为空
Status StackEmpty(SqStack S){ //栈为空则返回TURE
if(S.top==S.base)
return TURE;
else
return FALSE;
}6.求顺序栈的长度
【4.4】求顺序栈的长度
int StackLength(SqStack S)
{
return S.top-S.base;
}7. 清空顺序栈
算法：不用删除元素，只用将top指针指向栈底即可
【4.5】清空顺序栈
Status ClearStack(SqStack S){
if(S.base) S.top=S.base; //if(S.base)的意思是如果栈不为空
return OK;
}8.销毁顺序栈
算法：清空，再释放内存（不在存在指针）
【4.6】销毁顺序栈
Status DestroyStack(SqStack &S){
if(S.base){
delete S.base;
S.stacksize=0;
S.base=S.top=NULL; //将结构类型中的值设为空
}
return OK；
}四.重要操作——顺序栈
1.顺序栈的入栈
算法：判断栈是否已经满了，然后将元素e压入栈底，栈顶指针加1
【4.7】顺序栈的入栈操作
Status Push(SqStack &S,,SElemType e){
if(S.top-S.base==S.stacksize) //栈满
return ERROR;
*S.top=e;
S.top++; //这两步可以简写为：*S.top++=e;
return OK;
}2.顺序栈的出栈
算法：判断栈是否为空（下溢），若空则出错，获取栈顶元素e，栈顶指针下移（减1）
【4.8】顺序栈的出栈
Status Pop(SqStack &S,SElemType &e){
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if(S.top==S.base) //等价于if（StackEmpty（S））,该函数有介绍过
return ERROR;
S.stop--;
e=*S.top;
return OK;
}五.栈的表示和操作的实现——链栈
链栈是运算受限的的单链表，只能在链表头部进行操作
1.链式栈的表示
【4.9】链栈的表示
typedef strct StackNode{
SElemType data;
struct StackNode *next; //嵌套定义，仍用结果类型定义指针
}StackNode,*LinkStack; //*LinkStack：指针类型指向结点
LinkStack S; //S表示这个栈（指向结点的指针型）
如图，请注意每个结点的next域指向的不是后继，而是它的前驱，如an的next域指向an-1位置 ，因此对于数据结构这门学科一定要学会灵活运用基本操作。
重要的：（1）链表的头指针就是栈顶；（2)不需要头节点； （3）基本不存在栈满的情况；（4）空栈相当于头指针指向空 ；（5）插入和删除操作仅栈顶处执行
2.链栈的初始化
算法：构造空栈S，并让头指针指向它
【4.10】链栈的初始化
void InitStack(LinkStack &S){
S=NULL; //构造一个空栈，栈顶指针置为空
return OK;
}3.判断链栈是否为空
算法：判断头指针是否为空
【4.11】判断链栈是否为空
Status StackEmpty(LinkStack S）{
if(S==NULL) return TRUE;
else return FALSE;
}4.链栈的入栈
算法：S既是指向栈顶的头指针，又可以用S来代表整个栈，入栈时，分配一块空间，给data赋值为e。大概梳理一下流程就是，每次入栈都是将新结点插入栈顶，首先需要生成新的结点，并把data域置为元素值，然后next域就是上一个插入的结点,插入后有了新的栈顶，还要修改头指针S让它指向新栈顶（头指针S保持指向栈顶）
【4.12】链栈的入栈
Status Push(LinkStack &S,SElemType e){
p=new StackNode; //生成新结点p
p->data=e; //将新结点数据域置为e
p->next=S; //将新结点插入栈顶
S=p; //修改栈顶指针（让S指针指向新的栈顶）
return OK;
}5.链栈的出栈
算法：有了入栈的基础，出栈就很简单了，首先我们用e来保存出栈元素的值，然后因为“出栈”操作，因此它的下一个结点成为新的栈顶，所以需要移动指针S到下一个结点位置，但是在移动之前，要保存要出栈结点的地址，否则delete时找不到位置。
【4.13】 链栈的出栈
Status Pop(LinkStack &S,SElemType &e){
if(S==NULL) return ERROR;
e=S->data; //出栈元素的数据保存在e中中
p=S; //还是防止找不到了，先保存
S=S-next; //S移到下一个位置，待出栈后它就是新的栈顶
delete p; //删除
return OK;
}6.取栈顶元素
算法：这个也是很简单的，因为头指针本来就指向栈顶 。
【4.14】取栈顶元素
SElemType GetTop(LinkStack S){
if(S!=NULL)
return S->data;
}六.栈与递归
1.递归的定义：若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。若一个过程直接或间接地调用自己，则称该过程为递归。
2.三种常见递归：（1）函数，（2）数据结构本身递归特性，（3）可递归求解的问题
因此，递归的本质其实是数学思想分而治之，问题不断转化，就找到了递归的出口。
这里的基本项，我们亦可以称之为：出口（这里需要同学们掌握函数的递归调用的知识了），不是很清楚函数递归的同学们可以通过这篇文章了解递归的基本知识：(13条消息) 数据结构必备知识——函数的递归调用_电子科大不知名程序员的博客-CSDN博客
3.函数调用过程调用前,系统完成:(1)将实参,返回地址等传递给被调用函数(2)为被调用函数的局部变量分配存储区(3)
将控制转移到被调用函数的入口调用后,系统完成:⑴保存被调用函数的计算结果(2)释放被调用函数的数据区(3)依照被调用函数保存的返回地址将控制转移到调用函数
因此可知，在递归的过程中，需要保存一系列的值：实参，返回地址，局部变量，再待调用结束后返回，该过程称为记录现场。
4.当有多个函数构成嵌套调用
具体调用过程我简单的给大家画一画：
总结一下就是：一级一级的调用自身，直到能返回时（就是遇到出口了），再延顺序一级一级的返回。（后调用先返回），其中通过递归工作栈来在调用区间存储数据。（这里系统它会自己实现）
七.队列的顺序表示和操作的实现
1.关于队列（相关概念已在上文提到）——头删尾插（约定a1为队列头，an为队列尾）
插入元素称为入队，删除元素称为出队。
2. 和线性表一样，我们仍先介绍对队列的操作函数（抽象数据类型定义）
InitQueue(&Q) //构造空队列
DestroyQueue(&Q) //队列Q已存在，将其销毁
ClearQueue(&Q) //队列Q已存在，将其清空
QueueLength(&Q) //队列Q已存在，换回Q的元素个数，即队长
GetHead(Q,&e) //Q为非空队列，用e返回对头元素
EnQueue(&Q,e) //队列Q已存在，插入元素e为Q的队尾元素
DeQueue(&Q,&e) //队列Q已存在，删除Q的对头元素，用e返回其值
.......3.同样的，队列的储存方式也分为两种：顺序队列和链队列
【4.15】队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 //最大队列长度
Typedef strct{
QElemType *base; //初始化的动态分配存储空间
int front; //头指针
int rear; //尾指针（其实这里不是指针变量，但是为了方便理解，这里还是可以这样子称）
}SqQueue;*base将其理解为一个数组，来存放元素 ，而front和rear这里定义的不是指针类型，而是普通类型，因此使用它时不能用“->”,而是用“.”
4.初始、入队、出队介绍
初始：front=rear=0
J1,J2,J3入队：base[rear]=x;rear++;
J1,J2出队：x=base[front];front++; 空对标志：front==rear;
那么这里可以思考一个问题，随着元素入队出队后，rear指针的位置在不断改变，那么当rear不断改变位置，即使数组里面元素未满，也会因rear指针的位置改变出现溢出的情况。不妨设数组大小为MAXQSIZE，rear=MAXQSIZE时，发生溢出。根据我们上面说的，其实溢出分为两者类型：
（1）真溢出：front=0，rear=MAXQSIZE，即队列（数组）确实已经满了
（2）假溢出：front！=0，rear=MAXQSIZE，其实数组中还要空闲位置
解决假上溢的办法：将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为MAXQSIZE时，若向量的开始端空着，又可从头使用空着的空间。当front为MAXQSIZE时，也是一样。（把这个表想象为循环的对列）
base[0]接在base[MAXQSIZE-1]之后，若rear+1==M，则令rear=0;
实现方法：利用模（mod，C语言中：%）运算。 ——取余
插入元素:Q.base[Q.rear]=x
Q.base=(Q.rear+1) %MAXQSIZE; //防止假上溢
删除元素:x=Q.base[s.front]
Q.front=(Q.front+1)%MAXQSIZE //防止假下溢
5.判断队空队满：按照上述思路，不难发现，无论是队空还是队满，front指针和rear指针都会指向同一个位置，即（front==rear）,那这个问题该怎么解决呢？
解决方案：少用一个元素空间，这样的话，队空还是尾指针等于头指针，队满时，头指针跟尾指针就相差一个位置，有：
队空：front==rear；
队满：(rear+1)%MAXQSIZE==front;
八.(循环)队列的顺表示和实现（重要操作）
1.队列的初始化
【4.16】队列的初始化
Status InitQueue(SqQueue &Q){
Q.base=new QElemType[MAXQSIZE] //分配数组空间，用C的malloc语法为：
// Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base) exit(OVERFLOW); //存储分配失败
Q.front=Q.rear=0; //头指针尾指针置为0，队列为空
return OK;
}
2.求队列的长度
按照我们最开始想的，我们只用rear-front就可以知道队列的长度了，但我们为了解决假溢出问题，把这个队列整成了循环队列，那么rear的位置就不一定在front的上面了，那又该怎么办呢？
其实只用从rear指针为什么会跳到front的下面——因为我们对MAXQSZIE取了余！所以我们执行：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
【4.17】求队列的长度
int QueueLength(SqQueue Q){
return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
}3. 循环队列入队（前面已经引入了）
【4.18】循环队列入队
Status EnQueue &Q,QElemType e){
if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; //这里是真队满了
Q.base[Q.rear]=e; //新元素加入队尾
Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针+1
return OK;
}4.循环队列出队（只能在队头出队）
【4.19】循环队列出队
Status DeQueue(SqQueue &Q,QElemType &e){
if(Q.front==Q.rear) return ERROR; //队空不行
e=Q.base[Q.front]; //保存对头元素
Q.front=(Q.front+1)%MAXQSIZE; //队头指针+1
return OK;
}5.取队头元素
【4.20】 取队头元素
SElemType GetHead(SqQueue Q){
if(Q.front!=Q.rear) //队列不为空
return Q.base[Q.front]; //返回队头指针元素的值这里需要注意与出队的区别：同样都是取队头元素 ，但是出队时同时要移动front指针的位置，而这里并不改变队头指针。
九.链队——队列的链式表示和实现
若用户无法估计所用队列的长度，则宜采用链队列
【4.21】 链队列的类型定义
#define MAXQSIZE 100 //最大队列长度
typedef struct Qnode{ //Qnode：链队 Lnode：链表 Snode:链栈（命名具有辨识度）
QElemType data;
stuct Qnode *next; //经典嵌套结构，这里不多赘述
}QNode,*QueuePtr; //Qnode可代表结点类型，而*QueuePtr则是指向结点的指针类型
//和普通链表不一样的是，它不仅仅只用头节点就可以搞定了，还是有Q.front和Q.rear
//将Q.front和Q.rear可以放在一起用一个结构定义
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针(这里是指针了）
}LinkQueue;1.分析：链队列运算指针变化状况
2.链队列的初始化
【4.22】链队列的初始化
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //在内存中生成结点
if(!Q.front) exit(OVERFLOW); //内存不够的情况
Q.front->next=NULL; //跟链表一样，仍然是next域置空
return OK;
}3.链队列的操作——销毁链队列
算法：从对头结点开始，依次释放所有结点，需要引入指针变量p来保存位置防止丢失
【4.23】销毁链队列
Status DestoryQueue(LinkQueue &Q){
while(Q.front！=NULL）{
p=Q.front->next; //p保存队头结点
free(Q.front); //释放
Q.front=p; //赋予队头节点p的地址，即原先的Q.front->next位置
}
return OK;
}4.链队列的入队（将元素e加入到队尾）
【4.24】链队列入队
Status EnQueue(LinkQueue &Q,QElemType){
p=(QueuePtr)malloc(sizeof(Qnode)); //在空间中分配出一块空间
if（！p）exit(OVERFLOW); //分配失败
p->data=e; //将p的数据域赋值为p
p->next=NULL; //p在队尾
Q-rear->next=p; //将p地址赋值给尾指针的next域
Q.rear=p; //让尾指针指向新的p指向的结点（新尾结点）
return OK;
}5.链队列的出队（删掉头节点即可）
【4.25】 链队列的出队
//设删除的是a1,a1的下一个是a2
Status DeQueue (LinkQueue &Q,QElemType &e){//用e返回出队的元素
if(Q.front=Q.rear) return ERROR; //代表的是链队列为空
p=Q.front->next; //p指向的是a1的位置
e->p->data; //保存出队列元素的值
Q.front->next=p->next; //删除a1后，那么front的后继即是a2(p->next)
//这里需要注意一个问题，如果链栈中只含有一个元素（头结点下一个就是尾结点），那么删除的就是尾结点
if(Q.rear==p) Q.rear=Q.front;
delete p;
return OK;
}6.链队列求队头元素：直接找头节点下一个位置的data域即可
【4.26】求链队列的队头元素
Status GetHead(LinkQueue Q,QElemType &e){ //用e返回值
if(Q.front==Q.rear) return ERROR；
e=Q.front->next->data;
return OK; //与出栈的区别仍然是这里不用移动指针
}好了这就是栈和队列的所有基本操作和知识点已经全部讲完了，谢谢各位的阅读！