第3章-栈和队列

1、东北大学东北大学数据结构数据结构第第3章：栈和队列章：栈和队列主主 讲：张伟讲：张伟 单单 位：计算机学院通信与电子工程系位：计算机学院通信与电子工程系日日 期：期：2018年年11月月操作受限的线性表n栈（栈（Stack）n运算运算只只在表的在表的一端一端进行进行n队列（队列（Queue）n运算运算只只在表的在表的两端两端进行进行主要内容n栈栈n队列队列栈n栈栈n限定仅在表尾进行插入或删除操作的线性表限定仅在表尾进行插入或删除操作的线性表n表尾表尾栈顶栈顶，栈的唯一可访问元素，栈的唯一可访问元素n表头表头栈底栈底n不含元素的空表称空栈不含元素的空表称空栈n特点特点n栈存储和删除元素的顺序与元

2、素到达的顺序相反栈存储和删除元素的顺序与元素到达的顺序相反n先进后出（先进后出（FILO）n后进先出（后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈n栈栈定义定义 ADT Stack 数据对象：数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底端为栈底 基本操作：基本操作： ADT Stack栈n栈栈基本运算基本运算nSetnull（Stack） 置栈为空置栈为空nIsEmpty（Stack）判定栈是否为空）判定栈是

3、否为空nIsFull（Stack） 判定栈是否满判定栈是否满nPush（Stack，x）进栈操作，在栈顶插入元素）进栈操作，在栈顶插入元素nPop（Stack） 出栈操作，删除栈顶元素出栈操作，删除栈顶元素nGetTop（Stack） 取栈顶元素取栈顶元素元素插入栈称为元素插入栈称为“进栈进栈”“”“入栈入栈”或或“压栈压栈”（push）删除元素称为删除元素称为“出栈出栈”或或“弹出弹出”（pop）栈n栈栈存储结构存储结构n顺序栈顺序栈n链栈链栈顺序栈n概念：概念：n利用一组地址连续的存储单元依次存放自栈底到栈顶利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素的数据元素n栈底指针栈底指

4、针base，始终指向栈底位置，始终指向栈底位置n栈顶指针栈顶指针top，指示，指示栈顶元素的下一个位置栈顶元素的下一个位置n初始指向栈底，即初始指向栈底，即top=base为空栈为空栈n栈顶位置随进栈和出栈而变化栈顶位置随进栈和出栈而变化n进栈，进栈，toptop加加1 1n出栈，出栈，toptop减减1 1顺序栈n处理过程处理过程n顺序栈实际上是一维数组顺序栈实际上是一维数组top=base=0123450栈空栈空123450进栈进栈ABCDEF出栈出栈123450ABCDEFtoptopbasebasetoptoptoptoptoptoptoptoptop顺序栈n下溢（下溢（underfl

5、ow) ：ntop=0,栈空，此时出栈栈空，此时出栈n上溢（上溢（overflow) ntop=M,栈满，此时入栈栈满，此时入栈顺序栈n入栈入栈nStep1Step1：判别栈满否，若：判别栈满否，若满，则显示栈溢出信息，满，则显示栈溢出信息，停止执行；否则，执行停止执行；否则，执行step 2step 2； nStep3Step3：在：在toptop所指的位置所指的位置插入元素插入元素x x；nStep2Step2：栈顶指针：栈顶指针toptop上移上移( (加加1)1)；#define MAXSIZE n int stackMAXSIZE; int top = 0; int base=0；

6、push（int x） if（top = = MAXSIZE ） printf（“栈上溢栈上溢！n”）; exit （1）; else stack top+ = x ； /* 元素元素 x进栈进栈*/ /* 栈指针加栈指针加 1 */ 顺序栈n出栈出栈nStep1Step1：判别栈是否为空：判别栈是否为空；若空，则输出；若空，则输出 栈下溢栈下溢信息，并停止执行；否则信息，并停止执行；否则，执行，执行step2step2；nStep2Step2：弹出（删除）栈：弹出（删除）栈顶元素；顶元素； nStep3Step3：栈顶指针：栈顶指针toptop下移下移( (减减1)1)。#define MA

7、XSIZE n int stackMAXSIZE; int top = 0; int base = 0； pop（ ） int x; if( top = = base） printf(“ 栈下溢栈下溢 n”); exit(1); else x = stack -top ； /* 栈顶指针栈顶指针 减减1*/ return x ； 顺序栈n读栈读栈nStep1Step1：判别栈是否为：判别栈是否为空；若空，则输出提空；若空，则输出提示信息，并停止执行示信息，并停止执行；否则，执行；否则，执行step2step2；nStep2Step2：弹出栈顶元素：弹出栈顶元素；#define MAXSIZE

8、n int stackMAXSIZE; int top = 0; int base = 0； pop（ ） int x; if( top = = base） printf(“栈空不能读取栈顶元素栈空不能读取栈顶元素n”); exit(1); else x = stack top ； return x ； 顺序栈n若入栈的顺序为若入栈的顺序为1,2,3,4的话，则出的话，则出栈的顺序可以有哪些栈的顺序可以有哪些? n1234n1243n1324n1342n1423n1432n2134n2143栈的变种n两个独立的栈两个独立的栈n底部相连：双栈底部相连：双栈n迎面增长迎面增长哪一种更好些？哪一种更

9、好些？迎面增长的栈迎面增长的栈top1top2链栈n概念：概念：n用链式存储结构（即单链表）来表示栈用链式存储结构（即单链表）来表示栈n对于最大空间需要量事先不知的情况，不能使用顺对于最大空间需要量事先不知的情况，不能使用顺序栈，需要采用链栈序栈，需要采用链栈n指针方向从指针方向从栈顶向下栈顶向下链接链接 .栈底栈底top ki+2 ki+1 ki k0 topdatanext链栈n结构定义结构定义n链栈为空的条件：链栈为空的条件：top = NULLn链栈为满的条件：链栈为满的条件：t = NULLnt 为新申请的结点为新申请的结点,为为NULL表示失败表示失败struct snode El

10、emtypedata; struct snode *link; ;typedef struct snode SNODE ;链栈n处理过程处理过程 .栈底栈底topxtop .栈底栈底qtoptop链栈n入栈入栈nStep1Step1：申请一个链栈：申请一个链栈结点结点, ,若若t=NULL,t=NULL,则表则表示链满示链满; ;否则否则, ,执行执行step2 ;step2 ;nStep2Step2：在：在toptop所指结所指结点之前插入新结点点之前插入新结点, ,并并将将toptop指向新申请的结指向新申请的结点点t t。push(SNODE *top , Elemtype x) SNO

11、DE *t; t=(SNODE * ) malloc(sizeof(SNODE); if(t = = NULL ) printf(“内存中已无可用空内存中已无可用空 间间n”); exit(1); else t - data = x; t - link = top; top= t; 链栈n出栈出栈nStep1Step1：若链栈为空，：若链栈为空，则输出栈溢出信息；否则输出栈溢出信息；否则，执行则，执行step 2step 2。nStep2Step2：删除：删除toptop所指结所指结点，并使点，并使toptop指向被删指向被删除结点的后继结点。除结点的后继结点。nStep3Step3：释放被删

12、除结：释放被删除结点的存储空间。点的存储空间。pop (SNODE * top) SNODE *p; Elemtype x; if( top = = NULL ) printf(“栈溢出栈溢出n”）；）； exit(1); else p = top； top = top- link ； x = p- data ； free(p) ; 顺序栈与链栈的比较n时间效率时间效率n所有操作都只需常数时间所有操作都只需常数时间n顺序栈和链式栈在时间效率上难分伯仲顺序栈和链式栈在时间效率上难分伯仲n空间效率空间效率n顺序栈须说明一个固定的长度顺序栈须说明一个固定的长度n链式栈的长度可变，但增加结构性开销链式

13、栈的长度可变，但增加结构性开销顺序栈与链栈的比较n实际应用中，顺序栈比链式栈用得更广泛些实际应用中，顺序栈比链式栈用得更广泛些 n存储开销低存储开销低n顺序栈容易根据栈顶位置，进行相对位移，快速定位顺序栈容易根据栈顶位置，进行相对位移，快速定位并读取栈的内部元素并读取栈的内部元素 n顺序栈读取内部元素的时间为顺序栈读取内部元素的时间为O(1)，而链式栈则需要沿，而链式栈则需要沿着指针链游走，显着指针链游走，显然然慢些，读取第慢些，读取第k个元素需要时间为个元素需要时间为O(k) n一般来说，栈不允许一般来说，栈不允许“读取内部元素读取内部元素”，只能在栈顶操，只能在栈顶操作作 栈的应用n栈的特

14、点：后进先出栈的特点：后进先出n体现了元素之间的透明性体现了元素之间的透明性n常用来处理具有递归结构的数据常用来处理具有递归结构的数据n深度优先搜索深度优先搜索n表达式求值表达式求值n数制转换数制转换n行编辑处理行编辑处理 n子程序函数调用的管理子程序函数调用的管理n消除递归消除递归数制转换n非负十进制数转换成其它进制的数的一种简单方法：非负十进制数转换成其它进制的数的一种简单方法：n例，十进制转换成八进制：例，十进制转换成八进制：(66)10=(102)866/8=8 余余 28/8=1 余余 01/8=0 余余 1 结果为余数的逆序：结果为余数的逆序：102 n先求得的余数在写出结果时最后

15、写出，最后求出的余先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换。现数制转换。n同理，一个非负十进制整数同理，一个非负十进制整数N转换为另一个等价的基转换为另一个等价的基为为B的的B进制数，可以采用进制数，可以采用除除B取余法取余法来解决来解决 表达式求值n表达式求值是编译程序要处理的一个基本问题。表达式求值是编译程序要处理的一个基本问题。它的实现是栈应用的一个典型例子。它的实现是栈应用的一个典型例子。n任意一个算术表达式都是由操作数，操作符和界任意一个算术表达式都是由操作数，操作符和界限符组

16、成。操作数可为常量或变量，操作符有限符组成。操作数可为常量或变量，操作符有，/ /，界限符有（），界限符有（），# #。n前缀表示法前缀表示法OPOP + S1 + S2n中缀表示法中缀表示法 S1 + OPOP + S2n后缀表示法后缀表示法 S1 + S2 + OPOP表达式求值例如例如: Exp = a b + (c d / e) f前缀式前缀式: + a b c / d e f中缀式中缀式: a b + c d / e f后缀式后缀式: a b c d e / f + b-ca/*def*+表达式求值n中缀表达式的计算顺序中缀表达式的计算顺序n先执行括号内的计算，后执行括号外的计算。在

17、具有多先执行括号内的计算，后执行括号外的计算。在具有多层括号时，按层次反复地脱括号，左右括号必须配对层括号时，按层次反复地脱括号，左右括号必须配对n在无括号或同层括号时，先乘在无括号或同层括号时，先乘( (* *) ) 、除、除( () )，后加，后加(+)(+)、减、减(-)(-)n在同一个层次，若有多个乘除（在同一个层次，若有多个乘除（* *、）或加减、）或加减 (+(+，-) -)的的运算，那就按自左至右顺序执行运算，那就按自左至右顺序执行 23+(34*45)/(5+6+7) = ? 计算特点？计算特点？表达式求值n后缀表达式求值后缀表达式求值n先找运算符，再找操作数先找运算符，再找操

18、作数例如：例如： a b c d e / f +a bd/ec-d/e(c-d/e) f计算特点？计算特点？表达式求值n从原表达式求得后缀式方法从原表达式求得后缀式方法设立暂存设立暂存运算符运算符的的栈栈;设表达式的结束符为设表达式的结束符为“#”, 予设予设运算符栈的运算符栈的栈底为栈底为“#”若当前字符若当前字符是操作数是操作数，则，则直接发送给后缀式直接发送给后缀式;(后缀与前缀式操后缀与前缀式操作数的顺序是相同的作数的顺序是相同的)若当前字符若当前字符是运算符是运算符， 若若当前当前运算符的运算符的优先数高优先数高于栈顶运算符，则于栈顶运算符，则进栈进栈; 否则，退出栈顶运算符发送给后

19、缀式否则，退出栈顶运算符发送给后缀式;“(” 对它之前后的运算符对它之前后的运算符起隔离作用起隔离作用，“)”为自左括弧开始的表为自左括弧开始的表达式的结束符。达式的结束符。（a a）循环）循环 当（当（栈非空栈非空 and and 栈顶不是开括号栈顶不是开括号 and and 栈顶运算符的优先级不低于输入的运算符的优先级栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作：时，反复操作： 将栈顶元素弹出，放到后缀表达式序列中；将栈顶元素弹出，放到后缀表达式序列中；（b b）将输入的运算符压入栈内；）将输入的运算符压入栈内；表达式求值待处理中缀表达式待处理中缀表达式： 输出后缀表达式输出

20、后缀表达式：栈的状态栈的状态23/45567*()()34n从原表达式求得后缀式方法从原表达式求得后缀式方法表达式求值n后缀表达式求值后缀表达式求值循环：依次顺序读入表达式的符号序列（假设以作为输入序循环：依次顺序读入表达式的符号序列（假设以作为输入序列的结束），并根据读入的元素符号逐一分析：列的结束），并根据读入的元素符号逐一分析： 1. 当遇到的是一个操作数，则压入栈顶；当遇到的是一个操作数，则压入栈顶； 2. 当遇到的是一个运算符当遇到的是一个运算符, 就从栈中两次取出栈顶，按照运算符就从栈中两次取出栈顶，按照运算符对这两个操作数进行计算。然后将计算结果压入栈顶对这两个操作数进行计算。然

21、后将计算结果压入栈顶如此继续，直到遇到结束符号如此继续，直到遇到结束符号, 这时栈顶值就是输入表达式的值这时栈顶值就是输入表达式的值 表达式求值n后缀表达式求值后缀表达式求值待处理后缀表达式待处理后缀表达式：23/45567*34栈状态的变化栈状态的变化1530111885108表达式求值n表达式求值的算法表达式求值的算法算符优先算法算符优先算法n采用“算符优先法”，在表达式中,优先级的顺序是:n括号的优先级最高,对括号内的各种运算符有:先乘除、再加碱，同级运算从左至右。n先括号内，后括号外，多层括号，由内向外。n任何表达式都是由操作数、运算符和界符组成。n操作数可以是常量、变量、常数n运算符

22、有算术运算符、关系运算符、逻辑运算符n界符包括左右括号算式结束符。n运算符和界符统称为“算符”。表达式求值n表达式求值的算法表达式求值的算法算符优先算法算符优先算法n在算符集中，在每一个运算步，相邻的算符在算符集中，在每一个运算步，相邻的算符c1 c1 和和c2c2之间的关系是如下三种情况（之间的关系是如下三种情况（c1c1出现在出现在c2c2之前）：之前）：nc1c2,c1c1c2,c1c1c2,c1的优先级大于的优先级大于c2c2表达式求值n表达式求值的算法表达式求值的算法算符优先算法算符优先算法 / ( ) （） =表达式求值n表达式求值的算法表达式求值的算法算符优先算法算符优先算法n为

23、实现算符优先算法，在这里用了两个工作栈。一个存放为实现算符优先算法，在这里用了两个工作栈。一个存放算符算符OPTROPTR，另一个存放数据，另一个存放数据OPNDOPND。算法思想是：。算法思想是：n（1 1）首先置数据栈为空栈，表达式起始符）首先置数据栈为空栈，表达式起始符“”为算符栈为算符栈的栈底元素的栈底元素n（2 2）自左向右扫描表达式，读到操作数进）自左向右扫描表达式，读到操作数进OPNDOPND栈，读到运栈，读到运算符，则和算符，则和OPTROPTR栈顶元素比较栈顶元素比较（栈顶元素为栈顶元素为c1c1，读到的算，读到的算符为符为c2c2););n若若c1c2,c1c2,c1c2,

24、则将则将c1c1出栈，并在操作数栈取出两个元素出栈，并在操作数栈取出两个元素a a和和b b按按c1c1做运算做运算，运算结果进，运算结果进OPND.OPND.n重复直到表达式求值完毕。重复直到表达式求值完毕。例如：表达式例如：表达式3 3* *(7-2),(7-2),求值过程如下表：求值过程如下表：步骤步骤OPTROPTR栈栈OPNDOPND栈栈输入字符输入字符主要操作主要操作1 13 3* *(7-2)#(7-2)#PUSH(OPND,3)PUSH(OPND,3)2 23 3* *(7-2)#(7-2)#PUSH(OPTR,PUSH(OPTR,* *)3 3 * *3 3(7-2)#(7-

25、2)#PUSH(OPTR,()PUSH(OPTR,()4 4 * * （3 37-2)#7-2)#PUSH(OPND,7)PUSH(OPND,7)5 5 * * （3 73 7-2)#-2)#PUSH(OPTR,-)PUSH(OPTR,-)6 6 * * （ - -3 73 72)#2)#PUSH(OPND,2)PUSH(OPND,2)7 7 * * （3 7 23 7 2)#)#operate(7,-operate(7,-,2),2)8 8 * * （3 53 5)#)#POP(OPTR)POP(OPTR)消去括号消去括号9 9 * * 1515 # #operate(3,operate(3

26、,* *,5),5)1010 1515 # #PUSH(OPTR,PUSH(OPTR,* *)表达式求值为使两个算符比较方便为使两个算符比较方便, ,给算符设置优先级给算符设置优先级, ,如下表如下表, ,其中其中c1c1为栈内元素为栈内元素,c2,c2为栈外元素为栈外元素表达式求值算符算符栈内优先级栈内优先级栈外优先级栈外优先级* * / /4 43 3+ -+ -2 21 1( (0 05 5) )5 50 0# #-1-1-1-1栈与递归n作为数学和计算机科学的基本概念，递归是解决复杂问作为数学和计算机科学的基本概念，递归是解决复杂问题的一个有力手段，可使问题的描述和求解变得简洁、题的一

27、个有力手段，可使问题的描述和求解变得简洁、清晰、易懂清晰、易懂n符合人类解决问题的思维方式，递归能够描述和解决很多问题，符合人类解决问题的思维方式，递归能够描述和解决很多问题，为此许多程序设计语言都提供了递归的机制为此许多程序设计语言都提供了递归的机制n常常比非递归算法更易设计，尤其是当问题本身或所涉及的数常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适据结构是递归定义的时候，使用递归算法特别合适n而计算机则只能按照指令集来顺序地执行而计算机则只能按照指令集来顺序地执行n计算机内（编译程序）是如何将程序设计中的便于人类计算机内（编译程序）是如何

28、将程序设计中的便于人类理解的递归程序转换为计算机可处理的非递归程序的理解的递归程序转换为计算机可处理的非递归程序的? 栈与递归n递归函数：直接或间接调用自己的函数或过程递归函数：直接或间接调用自己的函数或过程1.递归步骤递归步骤：将规模较大的原问题分解为一个或多个规模：将规模较大的原问题分解为一个或多个规模更小、但具有类似于原问题特性的子问题更小、但具有类似于原问题特性的子问题n即较大的问题递归地用较小的子问题来描述，解原问即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题题的方法同样可用来解这些子问题2.递归出口递归出口：确定一个或多个无须分解、可直接求解的最：确定

29、一个或多个无须分解、可直接求解的最小子问题（小子问题（称为递归的终止条件递归的终止条件）栈与递归n阶乘阶乘n！的递归定义如下：的递归定义如下： 1, if 1factiorial( )factiorial(1), if 1nnnnn栈与递归n栈的一个最为广泛的应用：程序运行环境所提供的函数栈的一个最为广泛的应用：程序运行环境所提供的函数调用机制，调用机制，对用户而言透明对用户而言透明n运行时环境：目标计算机上用来管理存储器并保存执行过程所运行时环境：目标计算机上用来管理存储器并保存执行过程所需的信息的寄存器及存储器的结构需的信息的寄存器及存储器的结构n函数调用函数调用n静态分配：（在非递归）数

30、据区的分配可以在程序运行前进行，静态分配：（在非递归）数据区的分配可以在程序运行前进行，直到整个程序运行结束才释放。采用静态分配时，函数的调用直到整个程序运行结束才释放。采用静态分配时，函数的调用和返回处理比较简单，不需要每次分配和释放被调函数的数据和返回处理比较简单，不需要每次分配和释放被调函数的数据区区n动态分配：在递归调用的情况下，被调函数的局部变量不能静动态分配：在递归调用的情况下，被调函数的局部变量不能静态地分配某些固定单元，而须每调用一次就分配一份，以存放态地分配某些固定单元，而须每调用一次就分配一份，以存放当前所使用的数据，当返回时随即释放。故其存储分配只能在当前所使用的数据，当

31、返回时随即释放。故其存储分配只能在执行调用时才能进行：在内存中开辟一个称为执行调用时才能进行：在内存中开辟一个称为运行栈运行栈（runtime stack）的足够大的动态区）的足够大的动态区栈与递归n函数运行时的动态存储分配函数运行时的动态存储分配用作动态数据分配的存储区可按多种方式组织。典型的组织是将这用作动态数据分配的存储区可按多种方式组织。典型的组织是将这个存储器分为栈（个存储器分为栈（stack）区域和堆（）区域和堆（heap）区域）区域n栈区域用于分配具有后进先出栈区域用于分配具有后进先出LIFO特点的数据（诸如函数的调用）特点的数据（诸如函数的调用）n堆区域则用于不符合堆区域则用于

32、不符合LIFO（诸如指针的分配）的动态分配（诸如指针的分配）的动态分配栈与递归n运行栈中的活动记录运行栈中的活动记录 活动记录（活动记录（activation record）是动态存储分配中一个重要的单元）是动态存储分配中一个重要的单元n当调用或激活函数时，函数的活动记录包含了为其局部数据分配的当调用或激活函数时，函数的活动记录包含了为其局部数据分配的存储空间存储空间栈与递归n运行栈随着程序执行时发生的调用链或生长或缩小运行栈随着程序执行时发生的调用链或生长或缩小n每次调用一个函数时，执行进栈操作，把被调函数的活动信每次调用一个函数时，执行进栈操作，把被调函数的活动信息压入栈中，即每个新的活动

33、记录都分配在栈的顶部息压入栈中，即每个新的活动记录都分配在栈的顶部n每次从函数返回时，执行出栈操作，释放本次的活动记录，每次从函数返回时，执行出栈操作，释放本次的活动记录，恢复到上次调用所分配的数据区中恢复到上次调用所分配的数据区中n被调函数中变量地址全部采用相对于栈顶的相对地址来表示被调函数中变量地址全部采用相对于栈顶的相对地址来表示n一个函数在运行栈中可有若干不同的活动记录，每个代一个函数在运行栈中可有若干不同的活动记录，每个代表一个不同的调用表一个不同的调用n对于递归函数来说，递归的深度就决定了其在运行栈中活动对于递归函数来说，递归的深度就决定了其在运行栈中活动记录的数目记录的数目n当函

34、数递归调用时，函数体的同一个局部变量，在不同的递当函数递归调用时，函数体的同一个局部变量，在不同的递归层次被分配给不同的存储空间，放在内部栈的不同位置归层次被分配给不同的存储空间，放在内部栈的不同位置栈与递归n调用可以分解成以下三步来实现：调用可以分解成以下三步来实现：n调用函数发送调用信息。调用信息包括调用方要传送给被调调用函数发送调用信息。调用信息包括调用方要传送给被调方的信息，诸如实参、返回地址等方的信息，诸如实参、返回地址等n分配被调方需要的局部数据区，用来存放被调方定义的局部分配被调方需要的局部数据区，用来存放被调方定义的局部变量、形参变量（存放实参）、返回地址等，并接受调用方变量、

35、形参变量（存放实参）、返回地址等，并接受调用方传送来的调用信息传送来的调用信息n调用方暂停，把计算控制转到被调方，亦即自动转移到被调调用方暂停，把计算控制转到被调方，亦即自动转移到被调用的函数的程序入口用的函数的程序入口n当被调方结束运行，返回到调用方时，其返回处理一当被调方结束运行，返回到调用方时，其返回处理一般也分三步进行：般也分三步进行：n传送返回信息，包括被调方要传回给调用方的信息，诸如计传送返回信息，包括被调方要传回给调用方的信息，诸如计算结果等算结果等n释放分配给被调方的数据区释放分配给被调方的数据区n按返回地址把控制转回调用方按返回地址把控制转回调用方栈与递归n非递归程序的实现原

36、理非递归程序的实现原理n与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程与递归函数的原理相同，只不过把由系统负责的保存工作信息变为由程序自己保存序自己保存n减少保存数据的冗余减少保存数据的冗余(主要是节省了局部变量的空间主要是节省了局部变量的空间)，提高存储效率，提高存储效率n减少函数调用的处理以及冗余的重复计算，提高时间效率减少函数调用的处理以及冗余的重复计算，提高时间效率n程序要完成的工作分成两类：程序要完成的工作分成两类：n手头工作手头工作 程序正在做的工作，必须有其结束条件，不能永远做下去程序正在做的工作，必须有其结束条件，不能永远做下去n保存在栈中的待完成的工作保存在栈

37、中的待完成的工作 由于某些工作不能一步完成，必须暂缓由于某些工作不能一步完成，必须暂缓完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的完成，把它保存在栈中，保存的待完成工作必须含有完成该项工作的所有必要信息。所有必要信息。n程序须有序地完成各项工作程序须有序地完成各项工作手头工作和待完成工作可互相切换手头工作和待完成工作可互相切换n待完成工作必须转换成手头工作才能处理待完成工作必须转换成手头工作才能处理队列n队列队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。n队尾(rear)允许插入的一端n队头(front)允许删除的一

38、端n队列中没有元素时，称为空队列n队列特点队列特点n先进先出(FIFO)a1 a2 a3.an 入队入队出队出队frontrear队列队列Q=(a1,a2,an)队列n定义ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为队列头，端为队列头， an 端为队列尾端为队列尾 基本操作：基本操作： ADT Queue队列n队列队列基本运算基本运算nSetnull（Stack） 置队列为空置队列为空nIsEmpty（Q） 判定队列是否为空判定队列是否为

39、空nEnQueue（Q，x）入队操作，在队尾插入元素）入队操作，在队尾插入元素nDeQueue（Q，&x） 出队操作，删除队头元素出队操作，删除队头元素nGetHead（Q，&x） 返回队头元素返回队头元素队列n队列类型队列类型n顺序队列顺序队列n用一维数组表示的队列用一维数组表示的队列n循环队列循环队列n将顺序队列臆造为一个环状的空间将顺序队列臆造为一个环状的空间n链队列链队列n用链表表示的队列用链表表示的队列顺序队列n利用一组地址连续的存储单元依次存放自从队头利用一组地址连续的存储单元依次存放自从队头到队尾的数据元素到队尾的数据元素n采用一维数组实现采用一维数组实现n另附设两个指针另附设两

40、个指针nfrontfront为队头指针为队头指针, ,指示队头元素的位置指示队头元素的位置nrear rear 为队尾指针为队尾指针, ,指示队尾元素的下一个位置指示队尾元素的下一个位置n初值初值front=rear=0n空队列条件：空队列条件：front=rearn入队列：入队列：Qrear+=xn出队列：出队列： x = Qfront+#define MAXSIZE n int QMAXSIZE； int front,rear;顺序队列n入队入队/ /出队操作出队操作(1) 空队列空队列rear(2) A,B,C入队入队A B Cfrontfrontrear入队时，入队时，rear在变在变

41、(3) A,B出队，出队， D,E入队入队C D E frontrear 出队时，出队时，front在变在变(4) 反复反复 出队出队/入队入队frontrear假溢出发生假溢出发生假溢出：假溢出：随着元素不断入随着元素不断入/出队出队列，列，rear和和front指针会不断向指针会不断向后移动（如后移动（如(2)（3）所示），）所示），最终会指向数组的最大下标位置最终会指向数组的最大下标位置（如图（如图(4)所示）。由于所示）。由于rear和和front指针只能单方向移动，这指针只能单方向移动，这时元素无法入队列，但是队列中时元素无法入队列，但是队列中仍有大量空闲位置仍有大量空闲位置,这种情

42、况称这种情况称为假溢出。为假溢出。 H I 顺序队列n溢出溢出n当front=0,rear=M时，再有元素入队发生溢出真溢出n当front0,rear=M时，再有元素入队发生溢出假溢出n如何解决？当当rear = MAXSIZE 时，即超过队列末端时，时，即超过队列末端时，令令rear = 0；从而使队列的首尾相连接。；从而使队列的首尾相连接。 用表达式描述用表达式描述: if （rear = MAXSIZE ） rear = 0 ; else rear = rear + 1 ;循环队列n基本思想基本思想n把队列设想成环形，让Q0接在QM-1之后，若rear+1=M,则令rear=0;n实现n

43、入队nQrear=x; rear=(rear+1)%M; n出队nx=Qfront; front=(front+1)%M; 0M-11frontrear.frontrear(a) 空队列空队列0123n-1n-2iji+1i-1frontrear(b) 满队列满队列0123n-1n-2iji+1i-1循环队列循环队列n为了区分队空和队满区分队空和队满情况，可由两种方法：n另设一个标志位来区别队列是空还是满n少用一个元素空间，以“队头指针在队尾指针的下一位置”上作为队满标志n队空条件为front=rearn队满条件为(rear+1)%M=front30124567frontrear循环队列空30

44、124567frontrearABCDFGE循环队列满30124567frontrearABCD非空循环队列循环队列n入队操作入队操作nStep1：判别队列是否已满;nStep2：将新结点元素值存入队尾单元，队尾指针后移一个位置。addqueue(Elemtype x) if (front = (rear+1) % MAXIZE ) printf(“循环队列已满循环队列已满n”); exit(1); else Qrear = x ; rear = (rear+1) % MAXSIZE; 循环队列n出队操作出队操作nStep1：判别队列是否为空;若空,则显示队列下溢;nStep2：删除队头元素，队头指针后移一个位置。delqueue(Elemtype &e ) if ( front = rear ) p