3. 第三章：栈和队列

3.1 栈

• 栈（Stack）：只允许在一端进行插入或删除操作的线性表。
• 栈顶（Top）：线性表允许进行插入和删除的那一端。
• 栈底（Bottom）：固定的，不允许进行插入和删除的另一端
• 特点：1.栈是受限的线性表，所以自然具有线性关系。2.栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）

• 栈中元素后进去的必然先出来，即后进先出LIFO（Last InFirst Out）

3.1.1 顺序栈

• 栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈。

• 顺序栈的操作

• 1.判空：
• 
• 2.进栈：
• 
• 3.出栈：
• 
• 4.读取栈顶元素：
• 

3.1.2 共享栈

• 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
• 示意图

• 共享栈的结构

• 共享栈的操作：（进栈）

3.1.3 链式栈

• 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。
• 特点1.链栈一般不存在栈满的情况。2.空栈的判定条件通常定为top==NULL；
• 结构

• 链式栈的操作

• 1.进栈
• 
• 2.出栈
• 

3.2 队列

• 队列是只允许在一端进行插入，而在另一端进行删除的线性表
• 队头（Front）：允许删除的一端，又称为队首。
• 队尾（Rear）： 允许插入的一端。
• 先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO

3.2.1 顺序队列

队列的顺序存储采用一段连续的空间存储数据元素，并用两个整型变量记录队头和队尾元素的下标

• 用数组来实现队列，可以将队首放在数组下标为0的位置。

3.2.2 循环队列

把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列

循环队列队空的判定条件为：Q.front==Q.rear

队满的临界状态:(Q.rear+1)%Maxsize=Q.front

队列中元素个数为：(Q.rear-Q.front+Maxsize)%Maxsize

入队：rear=(rear+1)%MaxSize

Q.base[Q.rear]=x; //将元素x放入Q.rear所指空间
Q.rear=(Q.rear+1)%Maxsize; //Q.rear后移一位

出队：front=(front+1)%MaxSize

e=Q.base[Q.front]; //用变量记录Q.front所指元素，
Q.front=(Q.front+1)%Maxsize; // Q. front向后移一位

为什么要%Maxsize

循环队列无论入队还是出队，队尾、队头加1后都要取余运算，主要是为了处理临界状态，如图所示。队列的最大空间为Maxsize，当Q.rear=Maxsize−1时，Q.rear+1=Maxsize。而根据循环队列的规则，Q.rear的下一个位置为0才对，怎么才能变成0呢？可以考虑取余运算。即(Q.rear+1)%Maxsize=0，而此时Q.front=0，即(Q.rear+1)%Maxsize=Q.front。此时为队满的临界状态。

入队或出队时，队尾后队头加1后都有可能达到临界状态，因此加1运算后要%Maxsize，使其达到临界状态时，下标变为0。

循环队列长度计算公式

在计算元素个数时，可以分两种情况判断。

1. Q.rear Q.front：元素个数为Q.rear−Q.front。
2. Q.rear<Q.front：元素个数为Q.rear−Q.front+ Maxsize。

也可以采用取余的方法把两种情况巧妙地统一为一个语句。

队列中元素个数为：(Q.rear−Q.front+Maxsize)% Maxsize。

当Q.rear−Q.front为正数时，加上Maxsize超过了最大空间数，取余后正好是元素个数。

当Q.rear−Q.front为负数时，加上Maxsize正好是元素个数，因为元素个数小于Maxsize，所以取余运算对其无影响。

因此，%Maxsize是为了防止Q.rear−Q.front为正数的情况，+Maxsize是为了防止Q.rear−Q.front为负数的情况，

• 循环队列的操作

• 1.入队：
• 
• 2.出队：
• 

• 那如何分辨队列是空还是满呢？

• 方法一：设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满。
• 
• 方法二：我们把front=rear仅作为队空的判定条件。当队列满的时候，令数组中仍然保留一个空余单元。我们认为这种情况就是队列满了。
• 
• 
• 因此，%Maxsize是为了防止Q.rear-Q.front为正数的情况，+Maxsize是为了防止Q.rear-Q.front为负数的情况

3.2.3 链式队列

链队列类似一个单链表，需要两个指针front和rear分别指向队头和队尾。从队头出队，从队尾入队，为了出队时删除元素方便，可以增加一个头节点。

• 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。

• 为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。

• 链式队列的操作

• 1.入队：我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的。
• 
• 2.出队：出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点。
• 

3.2.4 双端队列

栈是后进先出，队列是先进先出，如何具有这两种特性呢？

栈是在一端进出，队列是在一端进、另一端出，能否设计两端都可以进出呢？

允许两端都可以进行入队和出队的队列，就是双端队列，如图所示。

双端队列是比较特殊的线性表，具有栈和队列两种性质。

循环队列表示的双端队列，可以用环形形象地表达出来。双端队列和普通循环队列的区别如图所示。双端队列包括前端和后端，可以从前端进入、前端出队、后端进队、后端出队。

3.3 栈和队列的应用

3.3.1.括号匹配：假设有两种括号，一种圆的()，一种方的[]，嵌套的顺序是任意的。

• 算法思想：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。
• 代码

3.3.2.表达式求值：

• 规则：从左到右扫描表达式的每个数字和符号，遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将运算结果进栈，直到最终获得结果。

3.3.3.递归：

• 要理解递归，你要先理解递归，直到你能理解递归。如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。
• 1.阶乘

• 时间复杂度：O(NlogN)

• 2.斐波那契数列

• 时间复杂度   O(2^n)

3.3.4.如何将中缀表达式转换成后缀表达式？

• 1.按运算符优先级对所有运算符和它的运算数加括号。(原本的括号不用加)
• 2.把运算符移到对应的括号后。
• 3.去掉括号。
• 例子

3.3.5 数制的转换

题目：将一个十进制数n转换为二进制数。

解题思路

十进制数转换为二进制，可以采用辗转相除、取余数的方法得到。例如十进制数11转二进制。先求余数11%2=1，求商11/2=5，然后用商5再求余数，求商，直到商为0，结

束。

11%2=1　11/2=5

5%2=1　 5/2=2

2%2=0　 2/2=1

1%2=1　 1/2=0

先求出的余数是二进制数的低位，后求出的余数是二进制数的高位，将得到的余数逆序输出就是所要的二进制数，即11的二进制数为1011。如何将余数逆序输出呢？逆序输出正好符合栈的先入后出性质，因此可以借助栈来实现。

算法步骤

1）初始化一个栈S。

2）如果n!=0，将n%2入栈S，更新n=n/2。

3）重复运行第2步，直到n=0为止。

4）如果栈不空，弹出栈顶元素e，输出e，直到栈空。

十进制数11转二进制的计算步骤如下：

1）初始时，n=11；

2）n%2=1，1入栈，更新n=11/2=5；

3）n %2 =1，1入栈，更新n=5/2=2；

4）n %2 =0，0入栈，更新n=2/2=1；

5）n %2 =1，1入栈，更新n=1/2=0；

6）n=0时，算法停止。

3.3.6 回文判定

题目：回文是指正读反读均相同的字符序列，如“abba”和“abcscba”均是回文，也就是说字符串沿中心线对称，如图3-55所示，但“foot”和“bed”不是回文。试写一个算法判定给定的字符串是否为回文

解题思路

回文是中心对称的，可以将字符串前一半入栈，然后，栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较，若相等，则再将出栈一个元素与后一个字符比较……直到栈空为止，则字符序列是回文。在出栈元素与串中字符比较不等时，则字符序列不是回文。

算法步骤

1）初始化一个栈S。

2）求字符串长度，将前面一半的字符依次入栈S。

3）如果栈不空，弹出栈顶元素e，与字符串后一半元素比较。若n为奇数，则跳过中心点，比较中心点后面的元素。如果元素相等，则继续比较直到栈空，返回true；如果元

素不等，返回false。

完美图解

假设字符串str="abcscba"，字符串存储数组如图所示。

字符串长度为7，将字符串前一半（7/2=3个元素）依次入栈，如图

当i=3时取数结束，因为字符串长度为奇数，需要跳过中心点，从i=4开始，字符串中的字符与出栈元素比较，如图所示。

3.4 栈和队列的比较