数据结构学习笔记（六）

Answer 1

栈是限定仅在表尾进行插入和删除操作的线性表。队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

栈的定义：栈（stack）是限定仅在表尾进行插入和删除操作的线性表。把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称后进先出（Last In First Out）的线性表，简称LIFO结构。

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

例如：有3个整型数字元素1、2、3依次进栈，会产生哪些出栈次序？如果元素数量多，出栈的变化将会更多。

栈的顺序存储结构及实现：栈的顺序存储其实也是线性表顺序存储的简化，简称为顺序栈。下标为0的一端作为栈底比较好，因为首元素都存在栈底，变化最小，所以让它作为栈底。定义一个top变量来指示栈顶元素在数组中的位置，好比游标卡尺的游标，可以来回移动。意味着栈顶的top可以变大变小，但是不能超过存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top=0。因此，空栈的判定条件为top=-1。

若现在有一个栈，StackSize为5，则栈普通情况、空栈和栈满情况如图所示。

进栈操作：进栈操作，也就是栈的插入，如图所示。

出栈操作：出栈操作pop。入栈和出栈没有涉及任何循环语句，因此时间复杂度均为O（1）。

两栈共享空间：对于两个相同类型的栈，我们可以做到最大限度地利用其事先开辟的存储空间进行操作。可以用一个数组来存储两个栈。操作方法如下：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈底为栈的末端，即下标为数组长度n-1处。如上图所示。这样两个栈如果增加元素，就是两端点向中间延伸。

关键思路就是：它们在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，只要它们不见面，两个栈就可以一直使用。

栈1为空时，top1=-1，当top2=n时，栈2为空。两个指针之间相差1时，即top1+1==top2为栈满。使用这样的数据结构通常都是两个栈的空间需求有相反关系的时候，也就是一个栈增长，一个栈缩短的情况。否则，很快会因为栈满而溢出。

栈的链式存储结构及实现：栈的链式存储结构简称链栈。我们把栈顶放在单链表的头部。对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。对于空栈来说，链表原定义是头指针向空，链栈的空其实就是top=NULL。

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

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

链栈的进栈和出栈操作时间复杂度都为O（1）。

如果栈的使用过程中元素变化不可预料，时大时小，最好用链栈。反之，如果它的变化在可控范围内，建议使用顺序栈。

栈的作用：栈的引入简化了程序设计的问题，划分不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

栈的应用——递归：一个递归的例子：斐波那契数列。兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子，假设所有兔子都不死，那么一年后可以繁殖多少对兔子？这个数列有一个特点：前面相邻两项之和，构成了后一项。用数学函数来定义就是：

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

递归过程退回的顺序是她前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复这些数据。这显然很符合栈这样的数据结构。

栈的应用——四则运算表达式求值：栈的一个常见应用：数学表达式的求值。逆波兰表示（RPN），是一种不需要括号的后缀表达法。

例如：对于“9+（3-1）×3+10÷2”，如果要用后缀表示法是“9 3 1-3*+10 2/+”叫后缀的原因在于所有符号都是在要运算数字的后面出现的。这是计算机喜欢的表达方式。

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

下面拿着“9 3 1-3*+10 2/+”这样的后缀表示法结合上面的规则进栈进行计算。

由此可以看出这个后缀表达式是正确的，那么这个后缀表达式是怎么转化的呢？中缀表达式转后缀表达式：把平时所用的标准四则运算表达式，即9+（3-1）×3+10÷2叫做中缀表达式。由于所有的运算符号都在两数字的中间，现在我们的问题就是中缀到后缀的转化。

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

让计算机具有处理中缀表达式的能力就两步：核心：使用栈的后进先出特性。