1.2.2　栈和队列

栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是栈的运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。

1.栈的定义及基本运算

（1）栈的定义

栈（Stack）是仅在表的一端进行插入和删除运算的线性表。通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。当表中没有元素时称为空栈。栈为后进先出（Last In First Out，LIFO）的线性表，简称LIFO表。

栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中“最新”的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除，如图1-18所示。

【例1-3】元素是以a0，a1，…，an-1的顺序进栈，退栈的次序却是an-1，an-2，…，a1，a0。

（2）栈的基本运算

①InitStack（S）：构造一个空栈S。

②StackEmpty（S）：判栈空。若S为空栈，则返回true，否则返回false。

③StackFull（S）：判栈满。若S为满栈，则返回true，否则返回false。该运算只适用于栈的顺序存储结构。

④Push（S，x）：进栈。若栈S不满，则将元素x插入S的栈顶。

⑤Pop（S）：退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。

⑥StackTop（S）：取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。

2.顺序栈

采用顺序存储结构的栈简称顺序栈，它是运算受限的顺序表。

（1）顺序栈的类型定义

注意：顺序栈中元素用向量存放，栈底位置是固定不变的，可设置在向量两端的任意一个端点，栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置。

（2）顺序栈的基本操作

设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-＞data[0]是栈底元素。

①进栈操作：进栈时，需要将S-＞top加1。

注意：S->top==StackSize-1表示栈满，“上溢”现象——当栈满时，再做进栈运算产生空间溢出的现象。上溢是一种出错状态，应设法避免。

②退栈操作：退栈时，需将S->top减1。

注意：S->top<0表示空栈，“下溢”现象——当栈空时，做退栈运算产生的溢出现象。下溢是正常现象，常用作程序控制转移的条件。

（3）顺序栈的基本运算

①置栈空。

②判栈空。

③判栈满。

④进栈。

⑤退栈。

⑥取栈顶元素。

（4）双栈共享一个栈空间

当栈满时会发生溢出，程序报错并终止运行。为了避免这种情况，需要为栈设立一个足够大的空间。但空间设置过大，而栈中实际只有几个元素，也是一种空间浪费。

在有几个栈的情况下，各个栈所需的空间在运行中是动态变化的。如果为几个栈分配同样大小的空间，而在实际运行时，有的栈膨胀得快，很快就产生了溢出，而其他栈可能此时还有许多空闲空间，这时就必须调整栈的空间，防止栈的溢出。当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。只有当整个向量空间被两个栈占满（即两个栈顶相遇）时，才会发生上溢。因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为⎿m/2⏌和⎾m/2⏋的向量空间比较，前者发生上溢的概率比后者要小得多。

例如，程序同时需要两个栈时，可以定义一个足够的栈空间。该空间的两端分别设为两个栈的栈底，用bot[0]和bot[1]指示。让两个栈的栈顶top[0]和top[1]都向中间伸展，直到两个栈的栈顶相遇，才认为发生了溢出，如图1-19所示。

3.链栈

栈的链式存储结构称为链栈。采用链接方式表示一个栈，便于结点的插入与删除。在程序中同时使用多个栈的情况下，用链接表示不仅能够提高效率，还可达到共享存储空间的目的。

（1）链栈的类型定义

链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针，如图1-20所示。

链栈的类型说明如下：

注意：LinkStack结构类型的定义是为了方便在函数体中修改top指针本身。若要记录栈中的元素个数，可将元素个数属性放在LinkStack类型中定义。

（2）链栈的基本运算

①置栈空。

②判栈空。

③进栈。

④退栈。

⑤取栈顶元素。

注意：链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。

4.栈的应用

栈的应用非常广泛。在现实生活中，很多实际问题的求解往往是先求解的结果后输出，或者后求解的结果先输出，这类问题正好可以利用栈的“先进后出”特点来实现。还有一些问题的求解经常使用回溯法求解，该方法也需要栈的支持。在程序设计中，存在大量的递归算法，其内部的实现机制也是通过栈来完成的。

（1）利用栈实现递归函数

栈的一个重要应用是在程序设计中实现递归过程。所谓递归，是指若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。以下3种情况常常用到递归方法：

①定义是递归的。例如，求n！可递归定义如下：

②数据结构是递归的。例如，单链表结点结构的定义：

③问题的解法是递归的。例如，汉诺塔问题的解法。

有大量的计算问题可归结成一个递归函数。例如，累加求和问题、求最大公约数、求解斐波那契数列、求幂运算等。另外，数学中许多著名的函数和多项式都是以递归形式给出的。例如，Ackerman（）函数，厄米特多项式、勒让德多项式等。下面以求解n！为例，说明栈在递归函数求解过程中的应用。根据n！的定义，可以写出相应的递归函数：

递归函数的调用是函数嵌套调用的特殊情形，即调用者和被调用者是同一个函数。在每次调用时系统将属于各个递归层次的信息组成一个称为“现场信息”的数据记录，这个记录中包含本层调用的一些值参数、局部变量、返回地址等，如图1-21所示。在递归调用时，先将这些“现场信息”保存在一个递归工作栈中，该工作栈按后进先出的形式组织。每递归调用一次，就为这次调用在栈顶存入一个现场信息记录，一旦本次调用结束，则将栈顶现场信息出栈，恢复到CPU中，以便返回上次调用的断点处继续执行。

在上面的程序代码中，R1为主调函数main（）调用factorial（）函数时的返回地址，R2为factorial（）函数中递归调用factorial（n-1）时的返回地址。每层调用的现场信息如表1-3所示。

程序的递归调用执行过程如图1-22所示（设n=4）。

（2）利用栈求表达式的值

所谓表达式，是由操作数、运算符、括号所组成的有意义的计算公式。根据运算符的操作对象个数，运算符可分为单目运算符、双目运算符和三目运算符。按照运算符的类型又分为算术运算符、逻辑运算符和关系运算符等。这里以双目运算符和算术表达式为例，说明栈在求解表达式值的过程中的应用。例如，12×（20-5）+30就是一个包含双目运算符的算术表达式。这类表达式中，所有运算符都出现在它的两个操作数之间，称为中缀表达式。表达式12×（20-5）+30还可写成“12205-×30+”的形式，这种形式的表达式中，不用考虑运算符的优先级以及括号，每个运算符都出现在它的两个操作数的后面，所以称为后缀表达式。

①后缀表达式的求值：利用栈求解后缀表达式的值，可以使用一个存放操作数的栈。求值过程中，按顺序依次扫描后缀表达式，当遇到操作数时就将它压入栈中；当遇到运算符时，就从栈中弹出两个操作数进行运算，然后再把运算结果压入栈中。当后缀表达式扫描结束时，留在栈顶的数就是所求表达式的值。因此，利用栈可以很方便地求出后缀表达式的值，算法实现较为简单。

②中缀表达式的求值：求解中缀表达式值时，必须考虑运算符的优先级及括号，因此算法实现较为困难。由于后缀表达式求值的算法实现较为容易，不用考虑运算符的优先级以及括号，因此在求解中缀表达式值时，可以先把中缀表达式转换为后缀表达式，这一转换过程也是栈的应用的一个典型例子。

对于中缀表达式5×（27+3×7）+22，转换为后缀表达式为“52737×+×22+”，实现这个转换的基本思想是：按顺序依次扫描中缀表达式，当读入一个操作数时就立即输出；而在读入一个运算符（如“+”或“-”）时，首先把它放进运算符栈，一直等到这个运算符的两个操作数都读完后，才能将它输出。例如，在对表达式4×6+5的处理中，当遇到“+”时已经输出的是4和6，而栈中存储着“×”，由于乘法的优先级高于加法，“×”可以从栈中弹出并输出，而“+”被放入栈中。当扫描遇到一个左括号时，立即将它压入栈中，栈中左括号的优先级被视为比任何运算符都低，继续扫描，直到出现右括号时，才将留在栈中这对括号之间的运算符逐一弹出并输出，最后弹出左括号。由于在后缀表达式中不再需要任何括号，所以不必将左、右括号输出。最后，当处理到表达式的末尾时，将栈中运算符全部弹出并输出。

5.队列的定义及基本运算

（1）队列的定义

队列是不同于栈的另一种特殊的线性表，只允许在一端进行插入，在另一端进行删除。这和日常生活中的排队现象是一致的。根据队列的特点，队列需要两个队列指针来说明：允许插入的一端称为队尾，通常用一个队尾指针（rear）表示，它总是指向队尾元素所在的存储位置：允许删除的一端称为队头，用一个队头指针（front）表示，它总是指向队头元素的前一个位置。用移动rear与front指针来进行插入和删除操作。显然，在队列中，最先插入的元素将被最先删除，因此又称队列为先进先出（First In First Out，FIFO）的线性表，如图1-23所示。若给定队列Q=（a0，a1，…，an-1），则称a0是队头元素，an-1是队尾元素。元素a0，…，an-1依次入队，出队的顺序与入队相同，a0出队后，a1才能出队，…，an-2出队后，an-1才能出队。若队列无元素，则为空队列，如图1-23所示。队列的基本操作除了入队和出队外，还有建立和撤销队列等操作。

（2）队列的存储结构

从存储结构看，队列也有顺序队列与链式队列两种。

①顺序队列：队列的顺序表示是用一维数组来描述，这里要用两个指针front和rear，front指向队头，rear指向队尾元素，MaxSize是数组的最大长度。队列的顺序表示及其入队和出队，如图1-24所示（图中f为front，r为rear）。

在图1-24所示的情况下，当再有元素需要入队时将产生“溢出”，然而队列中尚有3个空元素单元，称这种现象为“假溢出”。“假溢出”现象的发生说明上述存储表示是有缺陷的。改进方法是采用循环队列结构，即把数组从逻辑上看成是一个头尾相连的环，在有新元素需要入队时，只要队列中有空位值，就可以将新元素存入。

图1-25给出了循环队列结构及其入队和出队的操作。为了使入队和出队实现循环，可利用取余运算符％。

队头指针进1：front=（front+1）％MaxSize

队尾指针进1：rear=（rear+1）％MaxSize

在循环队列结构下，当front==rear时为空队列，当（rear+1）％MaxSize==front时为满队列。满队列时实际仍有一个元素的空间未使用，这里暂不讨论。

②链式队列：队列的链接表示是用单链表来存储队列中的元素，队头指针front和队尾指针rear分别指向队头结点和队尾结点，如图1-26所示。链接方式表示的队列称为链式队列。

和栈一样，队列的应用也非常广泛。例如，在计算机操作系统中，对各种软、硬件资源的管理都是利用队列实现的。在处理器调度中，将用户的作业控制块JCB和进程控制块PCB用多个队列组织和调度；在设备管理中，对设备控制块DCB的管理也是利用队列实现设备的分配和回收；操作系统利用打印队列，实现多个用户共享同一台打印机。

最后，需要指出的是，对于栈和队列的应用，只要掌握一点，那就是在什么情况下用栈和队列作为解决问题的数据结构。判断的要点是：如果这个问题满足后进先出的原则，就可以使用栈来处理；如果这个问题满足先进先出的原则，就可以使用队列来处理。比如，有一个数组序列，输入时按顺序输入，但是输出时需要逆序输出，那么就可以利用栈来处理，把这个数组存入一个栈中就可以很容易地按逆序输出结果。例如，要设计一个算法判断一个算术表达式的圆括号是否正确配对就可以用栈来求解，即对表达式进行扫描，凡遇到“（”就进栈，遇到“）”就退掉栈顶的“（”，表达式扫描完毕时，栈应为空。