数据结构-栈与队列

现在我要问问大家，这个最先进栈的元素，是不是就只能是最后出战呢? 答案是不一定，要看什么情况。栈对线性表的插入和删除的位置进行了限制 ，并没有对元素进出的时间进行限制，也就是说，在不是所有元素都进栈的情况下，事先进去的元素也可以出栈，只要保证是栈顶元素出栈就可以。

举例来说，如果我们现在是有 3 个整型数字元素 1、 2、 3 依次进栈，会有哪些出栈次序呢?

有没有可能是 312 这样的次序出栈呢？答案是肯定不会。因为 3 先出栈，就意味着，3曾经进栈，既然 3 都进栈了，那也就意味着， 1 和 2 已经进栈了，此时， 2 一 定是在 1 的上面，就是更接近栈顶，那么出栈只可能是 321，不然不满足 123 依次进栈的要求，所以此时不会发生1比2先出栈的情况。

从这个简单的例子就能看出，只是 3 个元素，就有 5 种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。这个知识点一定要弄明白。

栈的抽象数据类型

对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化。特别是插入和删除操作，我们改名为push 和pop，英文直译的话是压和弹，更容易理解。你就把它当成是弹夹的子弹压入和弹出就好记忆了，我 们一般叫进栈和出栈。

由于栈本身就是一个线性表，那么上一章我们讨论了线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

栈的顺序存储结构及实现

栈的顺序存储结构

栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，用下标0的一端作为栈底。因为首元素都在栈底，变化最小，所以让它作栈底。

定义一个top变量来指示栈顶元素在数组中的位置。存储栈的长度胃StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定为top=-1。

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

栈的顺序存储结构一一进栈操作

栈的顺序存储结构一一出栈操作

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

两栈共享空间

栈的顺序存储是很方便，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。不过它有一个很大的缺陷，就是必须实现确定数组存储空间大小，万一不够用了，就需要编码手段来扩展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。 如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这又何必呢？我们完全可以用一个数组来存储两个栈，只不过需要一点技巧。 我们的做法如图4-5-1，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

关键思路是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。 从这里也可以分析出，栈1为空时，就是top1=-1时；而当top2=n时，即是栈2为空时，那什么时候栈满呢？ 想想极端的情况，若栈2是空栈，栈1的 top1 等于 n-1 时，就是栈1满了。 反之，当栈1为空栈时， top2等于0时，为栈2满。但更多的情况，其实就是我刚才说的，两个栈见面之时，也就是两个指针之间相差 1 时，即top + 1 == top2为栈满。

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

使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。这样使用两栈共享存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出。

当然这只针对两个具有相同数据类型的栈的一个设计上的技巧，如果是不相同数据类型的栈，这种办法不但不能更好地处理问题，反而会使问题变得更复杂，要注意这个前提。

栈的链式存储结构及实现

栈的链式存储结构

栈的链式存储结构，简称为链栈。

想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢?由于单链表有头指针，而栈顶指针也是必须的，那干吗不让它俩合二为一呢，所以比较好的办法是把栈顶放在单链表的头部(如图 4-6-1 所示)。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。 但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是 top=NULL的时候。

栈的链式存储结构一一进栈操作

对于链栈的进栈 push 操作，假设元素值为 e 的新结点是 S， top 为栈顶指针，示意图如图 4-6-2 所示代码如下。

栈的链式存储结构一一出栈操作

假设变量 p 用来存储要删除的钱顶结点，将栈顶指针下移一位，最后释放 p 即可，如图 4-6-3 所示。

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

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

栈的作用

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

所以现在的许多高级语言，比如 )ava、 C#等都有对栈结构的封装， 你可以不用关注它的实现细节，就可以直接使用 Stack 的 push 和 pop 方法，非常方便。

栈的应用一一递归

递归的定义

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

当然，写递归程序最怕的就是陷入永不结束的无穷递归中 ， 所以， 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。 比如刚才的例子，总有一次递归会使得 i<2 的，这样就可以执行return i 的语句而不用继续递归了。

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

递归与栈之间有什么关系？

前面我们已经看到递归是如何执行宫的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的 需求，显然很符合钱这样的数据结构，因此， 编译器使用植实现递归就没什么好惊讶的了。

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

栈的应用一一四则运算表达式求值

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

我们举个例子，对于"9+ (3-1) X3+10-:-2"，如果要用后缀表示法应该是什么样子:"931-3*+102/+"，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。显然，这里没有了括号。

后缀表达式计算结果

为了解释后缀表达式的好处，我们先来看看，计算机是如何应用后缀表达式计算最终的结果20的。 后缀表达式：931-3*+102/+ 规则：:从左到右遍历表达式的每个数字和符号，遇到是数字就进枝，遇到是符号，就将处于桔顶两个数字出拢，进行运算，运算结果进钱，一直到最终获得结果。

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

3. 接下来是"-"，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈，如图4-9-2的左图所示。
4. 接着是数字3进栈，如图4-9-2的右图所示。

   

5. 后面是"*"，也就意味着栈中3和2出栈， 2与3相乘，得到6，并将 6进栈，如图4-9-3的左图所示。
6. 下面是"+"，所以栈中6和9出栈，9与6相加，得到15，将15进栈，如图4-9-3的右图所示。

7. 接着10和2两数字进栈，如图4-9-4的左图所示。
8. 接下来是符号"/"，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，如图4-9-4右图所示。

9. 最后一个是符号"+"，所以15与5出栈并相加，得到20，将20进栈，如图4-9-5的左图所示
10. 结果是20出栈，栈变为空，如图4-9-5的右图所示。

中缀表达式转后缀表达式（具体百度）

队列的定义

队列 ( queue ) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列是一种先进先出 (First In First Out) 的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的抽象数据类型

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

循环队列

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。先来看队列的顺序存储结构

队列顺序存储的不足

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

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

可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须 存储在数组的前 n 个单元这一条件，出队的性能就会大大增加。 也就是说，队头不需 要一定在下标为 0 的位置， 如图 4-12-3 所示。

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

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

出队 a1、 a2，则 front指针指向下标为 2 的位置， rear 不变，如图 4-12-5 的左图所示，再入队 a5，此时 front 指针不变， rear 指针移动到数组之外。嗯?数组之外， 那将是哪里?如图 4-12-5 的右图所示。

问题还不止于此。假设这个队列的总个数不超过 5 个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我 们的队列在下标为 0 和 1 的地方还是空闲的。 我们把这种现象叫做"假溢出"。

循环队列定义

我们把队列的这种头尾相接的顺序存储结构称为循环队列。

刚才的例子继续，图 4-12-5 的 rear 可以改为指向下标为 0 的位置，这样就不会造成指针指向不明的问题了，如图 4-12-6 所示。

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

• 此时问题又出来了，我们刚才说，空队列时， fronr =rear，现在当队列满时，也是 front=rear，那么如何判断此时的队列究竟是空还是满呢?

• 办法一是设置一个标志变量 flag， 当 front == rear，且 flag = 0 时为队列空， 当 front== rear，且 flag= 1 时为队列满。
• 办法二是当队列空时，条件就是 front = rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 例如图 4-12-8 所示，我们就认为此队列已经满了，也就是说，我们不允许图 4-12-7 的右图情况出现。

  

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

另外，当 rear> front 时，即图 4-12-4 的右图和 4-12-5 的左图，此时队列的长度 为 rear-front 但当 rear < front 时，如图 4-12-6 和图 4-12-7 的左图，队列长度分为 两段， 一段是 QueueSize-front， 另一段是 0 + rear，加在一起，队列长度为 rear-front + QueueSize。因此通用的计算队列长度公式为: (rear- front + QueueSize) %QueueSize

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

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

空队列时， front 和 rear 都指向头结点，如图 4-13-2 所示。

队列的链式存储结构一一入队操作

人队操作时，其实就是在链表尾部插入结点，如图 4-13-3 所示。

队列的链式存储结构一一出队操作

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

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

总结

栈和队列，它们都是特殊的线性表， 只不过对插入和删除操作做了限制。

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

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

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。

因此它们各自有各自的技巧来解决这个问题。

对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。 对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列 ，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是 O(n)的时间复杂度变成了O(1)。 它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图 4-14-1 所示。

参考：《大话数据结构》

感谢你花时间读到结尾！：D

后端一枚，默默搬砖撸代码，如果觉得不错欢迎关注我的公众号