《栈和队列教程》由会员分享,可在线阅读,更多相关《栈和队列教程(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塔的递归函数运行示意图