2.3 栈 与 队
2.3 栈 与 队
栈与队是线性表的特例，也就是在进行插入、删除运算时，增加了某些约束，以满足某些特殊的应用。根据它们的运算特性，也可以称栈为后进先出（LIFO）表，队为先进先出
（FIFO）表。
在本节中除了介绍有关栈和队的特点和基本运算外，将用较大的篇幅介绍递归技术。它包括栈在递归技术中的应用，递归程序的阅读和编制方法等，为学习后面的结构运算作准备。
顺序栈与链栈
1. 顺序栈
顺序栈是用顺序表作为存储结构，它与一般的顺序表一样，必须事先开辟一个足够大的连续存储空间。由于它只能在表的一端（栈顶）进行插入、删除运算，因此只要设置一个栈顶指针（top）来指示当前栈的情况。在顺序栈中，所谓栈顶指针实际上是一个整型变量，用来记录当前栈顶元素的序号，对顺序栈进行插入、删除过程就是修改栈顶指针的过程。在顺序栈设计插入、删除算法时，还须考虑溢出情况。当栈空时，若还要进行删除运算，则应发出“下溢出”信号；当栈满时，若还要进行插入运算，则应发出“上溢出”信号。由于顺序栈的插入、删除运算比较简单，这里不再举例。
2. 链栈
链栈是用线性链表构成的栈，当栈的大小事先不能确定时选用，如图2.14所示。
其中top为栈顶指针，若top=nil表示栈空，若再要进行删除运算，将发出“下溢出”信号，显然，链栈不会出现“上溢出”。
链栈的插入算法为：
INSTACK(top, x) //将x元素插入以top为栈顶的链栈中//
1. GENTNODE（p）；data (p)←x
2. next (p)←top //插入//
3. top←p
4. return
链栈的删除算法为：
DESTACK （top，y） //将链表栈顶元素删除，放入y中//
1. if（top=nil）then“下溢出”
2. else {y←data (top);r←top
3. top←next (top);RET (r)} //修改栈顶指针，回收结点//
4. return
顺序队与链队
1.顺序队
顺序队采用顺序表结构，由于队的插入和删除分别在队的两端（队尾和队头）进行，因此要设两个指针，即队尾指针（rear）和队头指针（front）。在一般的顺序队列中进行插入、删除运算时往往会出现“假溢出”现象。为此通常采用循环队列的形式，如图2.15所示。
循环队列同样需要设一个头指针（front）与一个尾指针（rear），在循环队列中进行插入、删除运算时，同样要考虑队的“上溢出”与“下溢出”问题。
在长度为n的循环队列Q中插入一元素的算法为：
INQUE1 (Q，n, front, rear, x) //在循环队列Q[0：n-1]中插入元素x//
1. rear←（rear+1）mod n
2. if （rear=front）then“下溢出”
3. else Q[rear]←x
4. return
循环队列的删除算法为
DEQUE1 （Q，n，front，rear，y）
1. if（front=rear）then“下溢出”
2. else {front←（front+1）mod n
3. y←Q[front]}
4. return
必须注意的是，循环队列的插入过程是先找插入位置，然后作出判断；而删除过程则是先做判断，然后再找删除位置。目的是它们都会用到（front=rear）作为队满或队空的判据。还有一点留意的是用这种算法在循环队列中永远会空一个位置。例如在图2.15中，假设front指在Q[6]而rear指在Q[4]，这说明当时循环队列中尚有Q[5]和Q[6]两个空位置，当要插入一个元素时，rear←（rear+1）mod n得到rear=5，进行正常的插入运算。但当再要插入一个元素时，rear修改为6，出现（rear=front），算法告之“上溢出”。但是实际上Q[6]当时还是空的。
如果要避免出现上述情况，可以在算法中增加一个flg变量，作为队空或队满的标志（设fla=1队满，flg=0队空）。这一算法作为练习题由读者完成。
2. 链队
用链结构表示的队列称为链队，在链队中设尾指针rear与头指针front，分别为链队进行插入与删除时用。
链队的插入算法为：
INSQ（x，front，rear）//将x元素插入链队中//
1. GETNODE（p）；data（p）←x；next（p）←nil //构成x结点//
2. if（rear=nil）then front←rear←p //空表时插入x//
3. else {next（rear）←p;rear←p} //插入x，修改rear//
4. return
链队的插入过程如图2.16所示
链队的删除算法为
DELQ（y，front，rear）//从链队删除一个元素//
1. if （front=nil）then “下溢出”
2. else {p←front；front←next（p）
3. y←data（p）；RET（p）} //删除队头结点//
4. return
链队的删除过程如图2.17所示。
2.3.3 递归
在软件设计中，特别是数据结构的算法设计中，许多问题的求解过程均有这样的特征：先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。而这些自问题具有与原问题相同的求解方法，于是可以再将它们划分为若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自下而上引用、合并，最后解答的过程称为递归过程。
例2.13求顺序表（a
，a
，…，a
）中最大的元素
算法思想：将线形表分解成（a
，a
，…，a
）和（a
，…，a
）两个字表，分别求得子表中的最大元素a
和a
，比较a
和a
中的大者，就可以求得线性表中的最大元素。而求子表中的最大元素方法与总表相同，即再分别将它们分成两个更小的子表，如此不断分解，直到表中只有一个元素为止。
算法表示如下：
MAX（A，i
，i
）//求顺序表A中i
到i
之间最大元素//
1. if （i
=i
）then m←A[i
] //递归出口//
2. else {mid←（i
+i
）div 2
3. m
←MAX （A，i
，mid）
4. m
←MAX （A，mid+1，i
）
5. if （m
> m
）then m←m
6. else m←m
}
7. return (m)
采用递归技术编写程序，在要解复杂的问题时比较直观、易读，对提高设计水平有较大的帮助。但对初学者来说，要真正理解和掌握这种方法，并能熟练地运用于实践中，还有不少困难。鉴于在后面的内容中将大量使用递归方法定义结构及编制各种算法，因此我们在这里结合栈在递归技术中的应用，对递归的实现原理、递归程序的阅读及正确使用递归技术编制各种算法作一些介绍。
1.递归调用的实现原理
从例2.13中可以看出，递归过程是子程序直接或间接地调用自己的过程，称为递归调用。但如果仅有这些操作，那么将会出现由于无休止得调用而引起死循环。因此，一个正确的递归程序虽然每次调用的是相同的子程序，但它的参量、输入数据等均有变化，并且在正常的情况下，随着调用的不断深入，必定会出现调用到某一层的子程序时，不再执行递归调用而终止程序的执行，我们称能使递归子程序本次执行不再进行递归调用，从前结束操作的部分称为递归出口，例如2.13中的语句1。
递归调用是子程序嵌套调用的一种特殊情况，即它是调用自身代码。为此我们也可以把每一次递归调用理解成为调用自身代码的一个复制件。由于每次调用时，它的参量和局部变量均不相同，因此也就保证了各个复制件执行时的独立性。
但这些调用在内部实现时，并不是每次调用真的去复制去复制一个复制件存放到内存中，而是采用代码共享的方式，也就是它们都是调用同一个子程序代码，而系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的子程序的参量值。这些单元以栈的形式存放，每调用一次入栈一次，当返回时执行退栈操作，把当前栈顶保留的值送回相应的参量中进行恢复，并按栈顶中的返回地址，不断点继续执行。下面通过对计算Fibonacci序列，介绍递归调用过程实现的内部机理。
例2.14Fibonacci序列算法如下：
Fib （n）
1. if （n=1）or（n=2）
2. then x←1
3. else
4. x←Fib（n-1）+Fib（n-2）
5. return (x)
表2.1 中为按上述算法求解Fib（5）时，递归调用过程中，程序执行及堆栈的变化情况。
|
序号 |
执行程序 |
执行语句 |
中断地址 |
进出栈 |
栈内情况 |
继续执行 |
备注 | |||||||||
|
返址 n Fib | ||||||||||||||||
|
1 |
Fib（5） |
1，4 |
d1：Fib（4） |
进 |
|
Fib（4） |
| |||||||||
|
2 |
Fib（4） |
1，4 |
d2：Fib（3） |
进 |
|
Fib（3） |
| |||||||||
|
3 |
Fib（3） |
1，4 |
d3：Fib（2） |
进 |
|
Fib（2） |
| |||||||||
|
4 |
Fib（2） |
1，2，5 |
返回d3 |
退 |
|
Fib（3） |
求得Fib（2）=1 | |||||||||
|
5 |
Fib（3） |
4 |
d4：Fib（1） |
进 |
|
Fib（1） |
| |||||||||
|
6 |
Fib（1） |
1，2，5 |
返回d4 |
退 |
|
Fib（3） |
求得Fib（1）=1 | |||||||||
|
7 |
Fib（3） |
5 |
返回d2 |
退 |
|
Fib（4） |
求得Fib（3）=2 | |||||||||
|
8 |
Fib（4） |
4 |
d5：Fib（2） |
进 |
|
Fib（2） |
| |||||||||
|
9 |
Fib（2） |
1，2，5 |
返回d5 |
退 |
|
Fib（4） |
求得Fib（2）=1 | |||||||||
|
10 |
Fib（4） |
5 |
返回d1 |
退 |
|
Fib（5） |
求得Fib（4）=3 | |||||||||
|
11 |
Fib（5） |
4 |
d6：Fib（3） |
进 |
|
Fib（3） |
| |||||||||
|
12 |
Fib（3） |
4 |
d7：Fib（2） |
进 |
|
Fib（2） |
| |||||||||
|
13 |
Fib（2） |
1，2，5 |
d7：Fib（4 |
退 |
|
Fib（3） |
求得Fib（2）=1 | |||||||||
|
14 |
Fib（3） |
4 |
d8：Fib（1） |
进 |
|
Fib（1） |
| |||||||||
|
15 |
Fib（1） |
1，2，5 |
返回d8 |
退 |
|
Fib（3） |
求得Fib（1）=1 | |||||||||
|
16 |
Fib（3） |
5 |
返回d6 |
退 |
|
Fib（5） |
求得Fib（3）=2 | |||||||||
|
17 |
Fib（5） |
5 |
|
|
|
结束 |
求得Fib（5）=5 |
Fib（5）的执行是从表2.1的序号1开始执行语句1、3、4，当遇到其中的Fib（5-1）时，必须中断当前执行的程序，转去执行Fib（4），此时要把当前断点的地址d
以及参量5入栈，进入序号2的Fib(4)的执行。同理又进入Fib(3)及Fib(2)的执行。而执行到Fib(2)时，因为年，转入递归出口，程序执行完1、2、5语句后，得到Fib(2)=1,返回时，从当前栈顶获得返回地址d
，并将参量恢复为3，退去栈顶元素，从断点d
处继续执行Fib(3)的语句4、5、…，如此反复进行，直到最后求得Fib(5)=5。从以上过程我们可以得出：
(1)每递归调用一次，就需进栈一次，称为递归深度，当n越大，递归深度越深，开辟的栈也越大。
（2）每当遇到递归出口或完成本次执行时，需从栈顶元素中得到返回地址，并恢复参量值，当全部执行完毕时，栈应为空。
2.递归程序的阅读
上面介绍的递归调用的实现原理是理解递归的基础，但在实际应用时，常常要求能够较快地求出某递归程序的调用结果，上述方法显然不能满足要求，因此需要提供一种比较快捷实用的阅读程序方法。下面介绍一种根据内部实现原理，采用图形描述方式的阅读程序的方法：
（1） 按次序写出当前调用层上的执行语句，并用有向线段表示执行的次序。
（2） 当遇到调用语句时，写出实际调用形式（实参），并用有向线段指向下一层调用，作为调用路线。在调用子程序结束处，用一有向线段作为返回路线，指向调用操作的下一步。
（3） 若为函数，在返回路线上标出本次调用所得的函数值。
例2．15 已知p(w)算法为：
P（w）
1. if (w>0) then
2. {p(w-1)
3. write (w)
4. p (w-1)}
5. return
画出计算p（3）的执行路线图。
图2.18为计算p（3）的执行路线，执行结果输出序列：1，2，1，3，1，2，1。
例2.16用例2.14中Fib算法计算Fib（5）。
图2.19是Fib（5）的执行线路图，执行结果为：Fib（5）=5。
2. 递归程序的编写
在编写递归程序之前，首先要确定本子程序的功能描述以及各变量的含义。确定递归出口的条件，然后从两方面进行算法设计：
（1）写出子程序中与递归出口相对应的操作。
（2）写出非递归出口处对应的操作，这部分可设定一些数据来调用，检验是否能实现本算法要求的功能。
（3）用条件语句将上述两部分连接起来，就成为一个完整的子程序。
在上面三部分中第二步是设计的难点，因为设计者往往觉得本身程序还没有编写出来，就要调用自身。这就要多思考、多实践，把问题逐渐想清楚。
我们仍以例2.14的求解Fibnacci序列为例说明。
例2.16Fibnacci序列的定义如下
Fib（n）=
编写求解Fib（n）的递归程序。
（1）当1或2为递归出口，用描述语言表示为：
if （n=1）or （n=2）
then F←1
（2）若数据为非递归出口（n>2时），按定义应是Fib（n-1）和Fib（n-2）两项之和，的程序如下：
F←Fib（n-1）+ Fib（n-2）
综合上述两部分得：
Fib（n）
1. if（n=1）or （n=2）
2. then F←1
3. else F←Fib（n-1）+Fib（n-2）
4. return
在上述例子中，由于各种条件及相应的操作都已清楚表示出来了，因此编程比较容易实现。然而，在许多情况下并没有很清楚地交待出这种分解，这时就要先对问题进行分析、分解，例如例2.13中对问题的处理。我们将在后面有关二叉树的算法设计中作进一步讨论。