《栈和队列教程》由会员分享，可在线阅读，更多相关《栈和队列教程（9页珍藏版）》请在金锄头文库上搜索。
1、 Revised as of 23 November 2020栈和队列教程栈和队列教程栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。本章除了讨论栈和队列的定义、表示方法和实现外，还将给出一些应用的例子。3.1 抽象数据类型栈的定义栈(stack) 是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义
2、，称为栈顶(top)，相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。 假设栈，则称为栈底元素，为栈顶元素。栈中元素按的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的（如图(a)所示）。因此，栈又称为后进先出（last in first out）的线性表（简称LIFO结构），它的这个特点可用图(b)所示的铁路调度站形象地表示。 栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。下面给出栈的抽象数据类型的定义：ADT Stack 数据对象: D=|ElemSet,i=1,2,n,n0 数据关系：R1=|,D,i=2,n
3、 约定端为栈顶，端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&s) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则FALSE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTop(S,&e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(&S,e) 初始条件：栈S已存在。
4、操作结果：插入元素e为新的栈顶元素。 Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse(S,visit() 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。ADT Stack 本书在以后各章中引用的栈大多为如上定义的数据类型，栈的数据元素类型在应用程序内定义，并称插入元素的操作为入栈，删除栈顶元素的操作为出栈。. 栈的表示和实现 和线性表类似,栈也有两种存储表示方法。 顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈
5、底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top=0表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈空间不够使用时再逐段扩大。为此，可设定两个常量：STACK_INIT_SIZE(存储空间初始分配量)和STACKINCREMENT(存储空间分配增量)，并以下述类型说明作为顺序栈的定义。typedef struct SElemType
6、*base; SElemType *top; int stacksize; SqStack; 其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL,则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。图展示了顺序栈中数据元素和栈顶指针之间的对应关系。以下是顺序栈的模块说明。Move disk
7、%i from %c to %cn, +c, n, x, z); 1 2 if(n=1) 3 move(x, 1, z); / 将编号为1的圆盘从x移到z 4 else 5 hanoi(n-1, x, z, y); / 将x上编号为1至n-1的圆盘移到y，z作辅助塔 6 move(x, n, z); / 将编号为n的圆盘从x移到z 7 hanoi(n-1, y, x, z); / 将y上编号为1至n-1的圆盘移到z，x作辅助塔 8 9 算法 栈与递归的实现（三）显然，这是一个递归函数，在函数的执行函数中，需多次进行自我调用。那么，这个递归函数是如何执行的先看任意两个函数之间进行调用的情形。 与
8、汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数若在函数A中调用了函数B，则称函数A为调用函数，称函数B为被调用函数。之间的链接及信息交换需通过栈来进行。 通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成3件事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部变量分配存储区；（3）将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也应完成3件工作：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函数保存的返回地址将控制转移到调用函数。当有
9、多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。例如，在图（c)所示主函数main中调用了函数first，而在函数first中又调用了函数second，则图（a)展示从函数second退出之后正执行函数first中某个语句时栈的状态（图中以语句标号表示返回地址）。 一个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此，和每次调
10、用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入“下一层”，即第i+1层。反之，退出第i层递归应返回至“上一层”，即第i-1层。为了保证递归函数正确执行，系统需设立一个“递归工作栈”在实际的系统中，一般都综合考虑递归调用和非递归调用统一处理，在此，我们只讨论直接递归调用的处理机制。作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出
11、一个工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。 例如，图展示了语句hanoi(3,a,b,c)(3-4)执行过程（从主函数进入递归函数到退出递归函数而返回至主函数）中递归工作栈状态的变化情况。由于算法所示的递归函数中只含4个值参数，则每个工作记录包含5个数据项：返回地址和4个实在参数，并以递归函数中的语句行号表示返回地址，同时假设主函数的返回地址为0。图中表示栈顶指针。实际上，在调用函数和被调用函数之间不一定传递参数的值，也可以传递参数的地址。通常，每个程序设计语言都有它自己约定的传递方法（包括被调用函
12、数的执行结果如何返回调用函数等）。由于递归函数结构清晰，程序易读，而且它的正确性容易得到证明，因此，利用允许递归调用的语言（例如C语言）进行程序时，给用户编制程序和调试程序带来很大方便。因为对这样一类递归问题编程时，不需用户自己而由系统来管理递归工作栈。递归运行的层次运行语句行号递归工作栈状态（返址，n值，x值，y值，z值）塔与圆盘的状态说明11,2,4,50，3，a，b，c由主函数进入第一层递归后，运行至语句（行）5，因递归调用而进入下一层。21,2,4,56，2，a，c，b0，3，a，b，c由第一层的语句（行）5进入第二层递归，执行至语句（行）5。31,2,3,96，1，a，b，c6，2，
13、a，c，b0，3，a，b，c由第二层的语句（行）5进入第三层递归，执行语句（行）3，将1号圆盘由a移至c后从语句（行）9退出第三层递归，返回至第二层的语句（行）6。26,76，2，a，c，b0，3，a，b，c将2号圆盘由a移至b后，从语句（行）7进入下一层递归。31,2,3,98，1，c，a，b6，2，a，c，b0，3，a，b，c将1号圆盘由c移至b后，从语句（行）9退出第三层，返回至第二层的语句（行）8。28,96，2，a，c，b0，3，a，b，c从语句（行）9退出第二层，返回至第一层的语句（行）6。16,70，3，a，b，c将3号圆盘由a移至c后，从语句（行）7进入下一层递归。21,2,4
14、,58，2，b，a，c0，3，a，b，c从第二层的语句（行）5进入第三层递归。31,2,3,96，1，b，c，a8，2，b，a，c0，3，a，b，c将1号圆盘由b移至a后，从语句（行）9退出第三层递归，返回至第二层语句（行）6。26,78，2，b，a，c0，3，a，b，c将2号盘由b移至c后，从语句（行）7进入下一层递归。31,2,3,98，1，a，b，c8，2，b，a，c0，3，a，b，c将1号圆盘由a移至c后，从语句（行）9退出第三层，返回至第二层语句（行）8。28,98，2，b，a，c0，3，a，b，c从语句（行）9退出第二层，返回至第一层语句（行）8。18,90，3，a，b，c从语句（行）9退出递归函数，返回至主函数。0栈空继续运行主函数。图 Hanoi塔的递归函数运行示意图
