第三章栈和队列一、大纲要求二、知识点梳理三、实际应用：
第三章栈和队列一、大纲要求栈和队列的基本概念
栈和队列的顺序存储结构
栈和队列的链式存储结构
栈和队列的应用
特殊矩阵的压缩存储
二、知识点梳理栈定义：
一类受限的线性表，只允许在一端进行插入和删除操作。
栈顶：
可以运行插入和删除的一端
栈底：
与栈顶相对
上图操作受限的线性表
本质上而言栈和队列都是线性表
特点：
FILO先进后出firstinlastout可以想成是开车进一个死胡同只能从后倒车
存储结构：
顺序栈和链栈（原因在与栈的本质是线性表）
数学性质：
N=(1/n+1)C(n:2n)
//顺序栈的定义Ttypeofstruct{Tdata[maxsize];ttop;//栈顶指针}SqStack;//顺序栈类型定义//考研中基本不需要自己定义算法题会提前告知xxstackxxstackvoidfunc（xxstack,,,）{函数体}//链栈节点定义typeofstructLNode{intdata;structLNode*next;//本体引用//考链栈的题目几乎为0}LNode;
//栈
队列的定义：
也是一种操作受限的线性表，限制其在表的一端进行插入而在另一端进行删除操作。
队尾：
可以插入的一端
队头：
可以删除的一段
特点：
FIFO可以想象成是开车过隧道，隧道一端进另一端出。
存储结构：
顺序队和链队
//顺序队列的定义typeofstruct{intdata[maxsize];intfront;intrear;}SqQueue;//链队节点定义typeofstructQNode{intdata;structQNode*next;}QNode;//链队类型定义typeofstruct{QNode*front;QNode*rear;}LiQueue;
顺序栈：
两个状态和两个操作
空栈：
top=-1
满栈：
top=maxSize-1
非法状态：
上溢和下溢（上溢即栈满仍进，下溢即空栈仍出）
进栈：
++top;data[top]=x;
//或data[++top]=x；
出栈：
x=data[top];top--;
//或x=data[top--]；
//初始化栈stvoidinitStack(SqStackst){st.top=-1;//***}//判断栈空boolisEmpty(SqStackst){if(st.top==-1)returntrue;elsereturnfalse;}//进栈intpush(SqStackst,intx){if(st.top==maxSize-1)//栈满判断语句return0;else:st.data[++st.top]=x;//***return1;}//出栈intpop(SqStackst,intx){if(st.top==-1)//判断栈空return0;else:x=st.data[st.top--]//***return1;}
链栈：
使用比顺序栈少但是相似lst
栈空：
lst-next=NULL;
栈满：
存在吗？内存上线？
进栈：
建立元素p在链lst的头插lst是头结点
p-next=lst-next;lst-next=p;
出栈：
单链表的删除操作
p=lst-next;x=p-data;lst-next=p-next;free(p);
//链栈的初始化操作voidinitStack(Lnode*lst){lst=(LNode*)malloc(sizeof(LNode));lst-next=NULL;}//判断栈空代码boolisEmpty(LNode*lst){if(lst-next==NULL)returntrue;elsereturnfalse;}//进栈代码voidpush(LNode*lst,intx){LNode*p;p=(LNode*)malloc(sizeof(LNode));p-next=NULL;//头插p-data=x;p-next=lst-next;lst-next=p;}//出栈代码intpop(LNode*lst,intx){LNode*p;if(lst-next==NULL)return0p=lst-next;//指向栈顶x=p-data;lst-next=p-next;//删除free(p);//释放内存return1;}
总结：
以上可以看出顺序栈的使用是比链栈简单很多的，因此在考试的频率上特别是算法题，基本都是顺序栈，不用链栈。
顺序队
如图所示，不可以继续添加元素，否则会造成数组越界而遭致程序出错。然而此时又不应该扩充数组，因为还有大量实际空间未被占用。此时我们应该如何解决这个问题呢？我们将其实现为循环队列。
循环队列（解决假溢出问题）
两个状态：
队空：qu.rear==qu.front
队满：（qu.rear+1）%maxSize==qu.front
两个操作：
进队：
qu.rear=(qu.rear+1)%maxSize;
qu.data[qu.rear]=x
出队：
qu.front=(qu.front+1)%maxSize;
x=qu.data[qu.front]
(这种设计有什么好处呢)
思考：
当rear==front的时候，队列可能是满，也可能是空。
因为存在满和空两种情况，我们需要分别判断：
☆满：当队列添加元素到rear的下一个元素是front的时候，也就是转圈子要碰头了，我们就认为队列满了。(Q.rear+1)%MAXSIZE=Q.front
☆空：当队列删除元素到frontrear的时候，我们认为队列空了。**Q.rearQ.front不一定为0**
图示：
说明：
为了解决刚才这个问题令队列空间中的一个单元闲置，使得队列非空时，Q.rear与Q.front之间至少间隔一个空闲单。
队列长度：Q.rear-Q.front；
队头元素：Q.base[Q.front+1]；
队尾元素：Q.base[Q.rear]；
//初始化队列voidinitQueue(SqQueuequ){qu.front=qu.rear=0;}//判断队空intisQueueEmpty(SqQueuequ){if(qu.front==qu.rear)return1;elsereturn0;}//进队算法intenQueue(SqQueuequ,intx){if((qu.rear+1)%maxSize==qu.front)//判断队满return0;qu.rear=(qu.rear+1)%maxSize;qu.data[qu.rear]=x;return1;}//出队算法intdeQueue(SqQueuequ,intx){if(qu.front==qu.rear)//判断是否队空return0;qu.front=(qu.front+1)%maxSize;x=qu.data[qu.front];return1;}
链队：
队空：lqu-rear==NULL;/lqu-front==NULL;
队满:存在吗（内存上限）
进队：(相当于非空链尾插)
lqu-rear-next=p;
lqu-rear=p;
出队：(相当于多元素链（1）头删除)
p=lqu-front;
lqu-front=p-next;
x=p-data;free(p);
//初始化voidinitQueue(LiQueue*lqu){lqu=(Liqueue*)malloc(sizeof(LiQueue))lqu-front=lqu-rear==NULL;}//判断队空intisQueueEmpty(LiQueue*lqu){if(lqu-rear==NULL
lqu-front==NULL)return1;elsereturn0;}//入队voidenQueue(LiQueue*lqu,intx){QNode*p;p=(QNode*)malloc(sizeof(QNode));p-data=x;p-next=NULL;if(lqu-rear==NULL)//空队加第一个元素lqu-front=lqu-rear=p;else{//尾插法lqu-rear-next=p;lqu-rear=p;}}//出队代码intdeQueue(LiQueue*lqu,intx){QNode*p;if(lqu-rear==NULL)return0;elsep=lqu-front;if(lqu-front==lqu-rear)//单元素链的出队处理lqu-front=lqu-rear=NULL;else//删除一个节点lqu-front=lqu-front-next;x=p-data;free(p);return1;//出队成功}
总结：能用顺序队就用顺序队。
三、实际应用：1.动态扩容顺序栈
2.栈在函数中的调用（寄存器）
栈是程序设计中的一种经典数据结构，每个程序都拥有自己的程序栈。栈帧也叫过程活动记录，是编译器用来实现函数调用过程的一种数据结构。C语言中，每个栈帧对应着一个未运行完的函数。从逻辑上讲，栈帧就是一个函数执行的环境：函数调用框架、函数参数、函数的局部变量、函数执行完后返回到哪里等等。栈是从高地址向低地址延伸的。每个函数的每次调用，都有它自己独立的一个栈帧，这个栈帧中维持着所需要的各种信息。
寄存器ebp(basepointer)指向当前的栈帧的底部（高地址），可称为“帧指针”或“基址指针”；寄存器esp(stackpointer)指向当前的栈帧的顶部（低地址），可称为“栈指针”。
在C和C++语言中，临时变量分配在栈中，临时变量拥有函数级的生命周期，即“在当前函数中有效，在函数外无效”。这种现象就是函数调用过程中的参数压栈，堆栈平衡所带来的。堆栈平衡是指函数调完成后，要返还所有使用过的栈空间。
函数调用其实可以看做4个过程：
压栈:函数参数压栈，返回地址压栈
跳转:跳转到函数所在代码处执行
执行:执行函数代码
返回:平衡堆栈，找出之前的返回地址，跳转回之前的调用点之后，完成函数调用
3.栈进行表达式求值
首先提出中前后缀表达式相互转换问题
//只要遇到中转前的必须复习一下这个
波兰表示法（中缀转前缀）
首先设定一个操作符栈，从右到左顺序扫描整个中缀表达式，如果是操作数，则直接归入前缀表达式；
如果是操作符，则检测器是否是右括号，如果是右括号，则直接将其入栈；
如果是左括号，则将栈中的操作符依次弹栈，归入前缀表达式，直至遇到右括号，将右括号弹栈，处理结束；
如果是其他操作符，则检测栈顶操作符的优先级与当前操作符的优先级关系，
如果栈顶操作符优先级大于当前操作符的优先级，则弹栈，并归入前缀表达式，直至栈顶操作符优先级小于等于当前操作符优先级，这时将当前操作符压栈。
当扫描完毕整个中缀表达式后，检测操作符栈是否为空，如果不为空，则依次将栈中操作符弹栈，归入前缀表达式。
//总结：1.中转前用了1个栈：操作符栈（也可以是两个操作数栈/表达式栈，不用逆序输出）
2.中转前怎么遍历：从右到左
3.中转前遇到右括号：入栈，而且如果非括号操作符遇到栈顶是右括号的，直接入栈。
4.无括号表达式
逆波兰表示法（中缀表达式转换成后缀表达式算法）
从左至右扫描一中缀表达式；
若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈；
若读取的是运算符：
(1)若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(2)若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(3)若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈
该运算符为左括号"("，则直接存入运算符堆栈；
该运算符为右括号")"，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止；
该运算符为非括号运算符：
当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。
总结：1.中转后用了2个栈：操作数栈（逆序输出）操作符栈
2.中转后怎么遍历：从左到右
3.中转后遇到左括号：入栈
4.无括号表达式
求解波兰表达
从运算数侧依次扫描。
如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
如果扫描的项目是一个运算符，则对栈的顶上两个操作数执行该运算。
将运算结果重新压入堆栈。
重复步骤第2-5步，堆栈中即为结果值。
4.进制转换
以二进制为例余数依次进制最后全部出栈
5.栈进行括号匹配（编辑器）
//栈//左括号入栈进栈//出栈匹配if}or】or）:top{[(出栈else：0//循环结束ifstackisnull=1:return1else:return0
6.实现浏览器页面进退访问
7.共享栈
结构体
7.双端队列