第 4 章 栈与队列

2022/02/28晴18℃

1. 栈的定义

1. 栈的定义

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

💕注意：

首先它是一个线性表，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

它限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

栈的插入操作：叫做进栈，也称压栈、入栈。 栈的删除操作：叫做出栈，也有的叫作弹栈。、

2. 进栈出栈变化形式

栈对线性表的插入和删除的位置进行了限制，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

2. 栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，针对它在操作上会有些变化。特别是插入和删除操作，改名为push和pop一般叫进栈和出栈。

3. 栈的顺序存储结构及实现

1. 栈的顺序存储结构

栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。
线性表是用数组来实现的，栈这种只能一头插入删除的线性表来说，用数组下标为0的一端作为栈底比较好，因为首元素都存在栈底，变量最小，所以让它作为栈底。

定义一个top变量来指示栈顶元素在数组中的位置，这top可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出尺寸的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top = 0，因此通常把空栈的判定条件定为top = -1

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如下所示

2. 栈的顺序存储结构—进栈操作

对于栈的插入，即进栈操作

3. 栈的顺序存储结构—出栈操作

两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。

4. 两栈共享空间

其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须事先确定数组存储空间大小，万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。对于一个栈，只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个不同类型的栈，可以做到最大限度地利用其实现开辟的存储空间来操作。

同样的道理，如果有两个相同类型的栈，为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。完全可以用一个数组来存储两个栈

数组有两个端点，两个栈有两个栈底。让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n - 1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

💡关键思路：

它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，只要它们俩不见面，两个栈就可以一直使用。
栈1为空时，就是top1 = -1时；而当top2 = n时，即是栈2为空时

若栈2是空栈，栈1的top1 = n - 1时，就是栈1满了。反之，当栈1为空栈时，top2 = 0时，为栈2满。但更多的情况就是两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2为栈满。

对于两栈共享空间的push方法，除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。

因为在开始已经判断了是否有栈满的情况，所以后面的top + 1或top2 - 1是不担心溢出问题的。
对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。 这只是针对两个具有相同数据类型的栈的一个设计上的技巧，如果是不同数据类型的栈，这种办法不但不能更好地处理问题，反而会使问题变得更复杂。

5. 栈的链式存储结构及实现

1. 栈的链式存储结构

简称为链栈
由于单链表有头指针，而栈顶指针也是必须的，所以比较好的办法就是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也失去了意义，通常对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。

但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top = NULL的时候。

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。

2. 栈的链式存储结构—进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针

3. 栈的链式存储结构—出栈操作

至于链栈的出栈pop操作，假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。
对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会很好一些。

6. 栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦与要解决问题的核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

7. 栈的应用—递归

1. 斐波那契数列实现

如果兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔都不死，那么一年依赖可以繁殖多少对兔子呢？
拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔子数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对……依次类推可以列出下表

表中数字1,1,2,3,5,8,13......构成了一个序列。这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项

编号①的一对兔子经过六个月就变成8对兔子了。用数学函数来定义就是

假设需要打印出前40位的斐波那契数列数

2. 递归定义

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

3. 迭代和递归的区别：

递归使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同情况选择不同的代码实现方式。

在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值集合返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

8. 栈的应用—四则运算表达式求值

1. 后缀(逆波兰)表示法定义

一种不需要括号的后缀表达法，把它称为逆波兰(Reverse Polish Notation，RPN)表示。

对于9 + (3 - 1) × 3 + 10 ÷ 2，如果要用后缀表示法应该是什么样子：9 3 1 - 3 * 10 2 / +，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

2. 后缀表达式计算结果

后缀表达式：9 3 1 - 3 * + 1 0 2 / +

规则：
从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

1. 初始化一个空栈。此栈用来对要运算的数字进出使用。
2. 后缀表达式中前三个都是数字，所以9、3、1进栈

1. 接下来是“-”，所以将栈中的1出栈作为减数，3进栈作为被减数，并运算3-1得到2，再将2进栈
2. 接着是数字3进栈

1. 后面是“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈
2. 下面是“+”，所以栈中6和9出栈，9与6相加，得到15进栈

1. 接着是10与2两数字进栈
2. 接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈

1. 最后一个是符号“+”，所以15与5出栈并相加，得到20，将20出栈
2. 结果是20出栈，栈变为空

3. 中缀表达式转后缀表达式

把平时所用的标准四则运算表达式，即“9 + (3 - 1) × 3 + 10 ÷ 2”叫做中缀表达式。
中缀表达式“9 + (3 - 1) × 3 + 10 ÷ 2”转化为后缀表达式“9 3 1 -3*+ 102 /+”

规则：
从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号出栈，一直到最终输出后缀表达式为止。

1. 初始化—空栈，用来对符号进出栈使用。

1. 第一个字符是数字9，输出9，后面是符号“+”，进栈。
2. 第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。
3. 第四个字符是数字3，输出，总表达式为9 3，接着是“-”，进栈。

1. 接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，需要去匹配此前的“(”，所以栈顶依次进栈，并输出，直到“)”出栈为止。此时左括号上方只有“-”，因此输出“-”。总的输出表达式为9 3 1 -。
2. 接着是数字3，输出，总的表达式为9 3 1 - 3。紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。

1. 之后是符号“+”，此时当前栈顶元素“*”比这个“+”的优先级高，因此栈中元素出栈并输出(没有比“+”号更低的优先级，所以全部出栈)，总输出表达式为9 3 1- 3 *。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指中缀表达式中开头的9后面那个“+”
2. 紧接着数字10，输出，总表达式变为9 3 1 - 3 * + 10。后是符号“÷”，所以“/”出栈。

1. 最后一个数字2，输出，总的表达式为9 3 1 - 3* + 10 2。
2. 因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 — 3 * + 10 2 / +。

要想让计算机具有处理我们通常的标准(中缀)表达式的能力，最重要的就是两步：

1. 将中缀表达式转换为后缀表达式(栈用来进出运算的符号)
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)

9. 队列的定义

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队伍是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

假设队列是q = (a1,a2,...,an),那么a1就是队头元素，而an是队尾元素。在删除时，总是从a1开始，而插入时，列在最后。

10. 队列的抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

11. 循环队列

1. 队列顺序存储的不足

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)

如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列如下图所示，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置

出队a1、a2，则front指针指向下标为2的位置，rear不变，如图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。

假设这个队伍的总个数不超过5个，但目前如果接着入队的话，因数组末尾已经占用，再向后加，就会产生数组越界的错误，队列在下标为0和1的地方还是空闲的。把这种现象叫做“假溢出”。

2. 循环队列定义

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。把队列的这种头尾相接的顺序存储结构称为循环队列。
下图的rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了。

接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如下图左所示。若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下右图所示。

此时问题又出来了，空队列时，front = rear，现在当队列满时，也是front = rear，如何判断此时的队列究竟是空还是满呢？
办法一是设置一个标志变量flag，当front == rear，且flag = 0时为队列空，当front == rear，且flag = 1时为队列满。

办法二是当队列空时，条件就是front = rear，当队列满时，修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。

如下图左所示，就认为此队列已经满了，也就是说，不允许下图右的情况出现。

重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的1最大尺寸为QueueSize，那么队列满的条件是(rear + 1) % QueueSize == front(取模“%”的目的就是为了整合rear与front大小为一个问题)。
比如上面这个例子，QueueSize = 5，上图左中front =0，而rear = 4,(4+1) % 5 =0，所以此时队列满。再比如上图右，front = 2而rear =1.(1 + 1) % 5 =2，所以此时队列也是满的。而对于前两个图，front = 2而rear = 0,(0+1) % 5 =1,1≠2，所以此时队列并没有满。

单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以还需要研究一下不需要担心队列长度的链式存储结构。

12. 队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，把它简称为链队列。为了操作上的方便，将队头指针指向链队列的头结点，而队尾指针指向终端结点

空队列时，front和rear都指向头结点

1. 队列的链式存储结构—入队操作

入队操作时，其实就是在链表尾部插入结点

2. 队列的链式存储结构—出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实就是它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

13. 总结

1. 栈
2. 队列
3. 链式存储结构