栈和队列教程

1、栈和队列教程Company Document number : WTUT-WT88Y-W8BBGB-BWYTT-19998栈和队列教程栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队 列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。 但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在 各种软件系统中，因此在面向对象的程序设计中，它们是多型数据类型。本章除了讨论栈和队列的 定义、表示方法和实现外，还将给出一些应用的例子。3.1抽象数据类型栈的定义栈(stack)是限定仅在表尾进行插入或

2、删除操作的线性表。因此，对栈来说，表尾端有其特殊含 义，称为栈顶(top),相应地，表头端称为栈底(bottom) o不含元素的空表称为空栈。假设栈S二6“比，弘)，则称为栈底元素，6为栈顶元素。栈中元素按创，弘的次序 进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的(如图) 所示)。因此，栈又称为后进先出(last in first out)的线性表(简称LIFO结构)，它的这个 特点可用图(b)所示的铁路调度站形象地表示。伍)栈的示意图； 用饮路训度站表示栈栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。下面给出栈 的抽象数据类型的

3、定义:ADT Stack数据对象：D二坷 WiWElemSet, i=l, 2,n, nNO数据关系:Rl=ai-1, ai I ai-I,咗D, i二2,n约定&端为栈顶，旳端为栈底。基本操作:InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&s)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE,否则FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetT

4、op(S, &e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S, e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop (&S, &e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S, visit() 初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit ()o 旦v isit()失败，则操作 失效。ADT Stack本书在以后各章中引用的栈大多为如上定义的数据类型，栈的数据元素类型在应用程序内定义，并 称插入元素的操作为入栈，删除栈顶元素的操作为出栈。.

5、栈的表示和实现和线性表类似，栈也有两种存储表示方法。顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素， 同时附设指针top指示栈顶元素在顺序栈中的位置。通常的习惯做法是以top二0表示空栈，鉴于C 语言中数组的下标约定从0开始，则当以C作描述语言时，如此设定会带来很大不便；另一方面， 由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定 栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈空间不 够使用时再逐段扩大。为此，可设定两个常量：STACK_INIT_SIZE(存储空间初始分配量)和 ST

6、ACKINCREMENT(存储空间分配増量).并以下述类型说明作为顺序栈的定义。typedef structSElemType *base;SElemType *top;int stacksize;SqStack;其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行 第一次存储分配，base可称为栈底指针，在顺序栈中它始终指向栈底的位置.若base的值为 NULL,则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top二base可作为栈空的标 记，每当插入新的栈顶元素时，指针top増1 ；删除栈顶元素时，指针top减1,因此，非空栈中的 栈顶

7、指针始终在栈顶元素的下一个位置上。图展示了顺序栈中数据元素和栈顶指针之间的对应关 系。top以下是顺序栈的模块说明。delta next栈顶A图3. 3琏栈示意图+ */(1348)ifi = (2504)s#0 I若若(3-1)n=0nT (3-2) lFib(n-l)4Fib(n-2)其他情形rn+1若 m二0Ack (m, n)=- Ack (m-1, 1)若 n=0(3-3)-Ack (m- I, Ack (ni, rr I) Jl他j QMove disk %i from %c to %cn, +c, n, x,z); 1 2 if(n=l)3 move(x, 1, z) ;/将编号

8、为1的圆盘从x移到z4 else5 hanoi(n-l, x, z, y) : /将x上编号为1至nT的圆盘移到y, z作辅助塔6 move (x, n, z) ; /将编号为n的圆盘从x移到z7 hanoi(n-l, y, x, z) ; /将y上编号为1至nT的圆盘移到z, x作辅助塔8 9 算法栈与递归的实现(三)显然，这是一个递归函数，在函数的执行函数中，需多次进行自我调用。那么，这个递归函数是如 何执行的先看任意两个函数之间进行调用的情形。与汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中调用函数和被调用函数若在函数A中调用了函数B,则称函数A为调用函数

9、，称函数B为被调用函 数。之间的链接及信息交换需通过栈来进行。通常.当在一个函数的运行期间调用另一个函数时.在运行被调用函数之前，系统需先完成3件 事：（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；（2）为被调用函数的局部 变量分配存储区；（3）将控制转移到被调函数的入口。而从被调用函数返回调用函数之前，系统也 应完成3件工作：（1）保存被调函数的计算结果；（2）释放被调函数的数据区；（3）依照被调函 数保存的返回地址将控制转移到调用函数。当有多个函数构成嵌套调用时，按照“后调用先返回”的 原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的

10、数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数 退出时，就释放它的存储区，则当前正运行的函数的数据区必在栈顶。例如，在图（c）所示主函数 main中调用了函数first,而在函数first中又调用了函数second,则图（a）展示从函数second退出之 后正执行函数first中某个语句时栈的状态（图中以语句标号表示返回地址）。顶(a)栈顶（b）void f i rsi.(int s. int t); void second(int d):void mainO int n; first(ni, n):1:1int rirst(int s. int t)

11、int i:second (i);2:int second(int d)( int xf v; (c)图3.6主函数main执行期间运行栈的状态个递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数, 因此，和每次调用相关的一个重要的概念是递归函数运行的“层次”。假设调用该递归函数的主函数 为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入“下一层”，即第 冲层。反之，退出第i层递归应返回至“上一层”，即第层。为了保证递归函数正确执行，系统 需设立一个“递归工作栈”在实际的系统中，一般都综合考虑递归调用和非递归调用统一处理，在 此，我们只讨论

12、直接递归调用的处理机制。作为整个递归函数运行期间使用的数据存储区。每一层 递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回 地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个 工作记录，则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为“活动记录”， 并称指示活动记录的栈顶指针为“当前环境指针”。例如，图展示了语句hanoi (3, a, b, c)(34)执行过程(从主函数进入递归函数到退出递归函数而返回至主函数)中递归工作栈状态的变化 情况。由于算法所示的递归函数中只含4个值参数，则每个工作记录包含5

13、个数据项：返回地址和 4个实在参数，并以递归函数中的语句行号表示返回地址，同时假设主函数的返回地址为0。图中 表示栈顶指针。实际上，在调用函数和被调用函数之间不一定传递参数的值，也可以传递参数的地址。通常， 每个程序设计语言都有它自己约定的传递方法(包括被调用函数的执行结果如何返回调用函数 等)o由于递归函数结构清晰，程序易读，而且它的正确性容易得到证明，因此，利用允许递归调用的语言（例如C语言）进行程序时，给用户编制程序和调试程序带来很大方便。因为对这样一类递归问题编程时，不需用户自己而由系统来管理递归工作栈。递归运行的层次运行语句行号1,2, 4, 51,2, 4, 51,2, 3, 96

14、,71,2, 3, 9递归工作栈状态（返址，n值，x值，y值,值）塔与圆盘的状态0, 3, a, b, c2由主函数进入 第一层递归 后，运行至语 句（行）5, 因递归调用而 进入下一层。由第一层的语 句（行）5进 入第二层递 归，执行至语 句（行）5。由第二层的语 句（行）5进 入第三层递 归，执行语句（行）3,将1 号圆盘由a移 至c后从语句（行）9退出 第三层递归， 返回至第二层 的语句（行） 6。将2号圆盘由 。移至b后， 从语句（行） 7进入下一层 递归。将1号圆盘由 c移至b后， 从语句（行）9退出第三 层，返回至第 二层的语句（行）8。6,71,2, 4, 51,2, 3,96,71,2, 3,9从语句（行） 9退出第二 层，返回至第 层的语句（行）6。将3号圆盘由 a移至c后， 从语句（行） 7进入下一层 递归。从第二层的语 句（行）5进 入第三层递 归。将1号圆盘由 b移至a后， 从语句（行） 9退出第三层 递归，返回至 第二层语句（行