第章栈和队列

1、第 3 章 限定性线性表栈和队列 第第3章章 限定性线性表限定性线性表栈和队列栈和队列 3.1 栈栈 3.2 栈的应用举例栈的应用举例3.3 栈与递归的实现栈与递归的实现3.4 队列队列 第 3 章 限定性线性表栈和队列 3.1 3.1 什么是栈什么是栈? ? 例 算术表达式5+6/2-3*4。正确理解： 5+6/2-3*4 = 5+3-3*4 = 8-3*4 = 8-12 = -4 p由两类对象构成的： 运算数，如2、3、4 运算符号，如+、-、*、/ p不同运算符号优先级不一样 第 3 章 限定性线性表栈和队列 后缀表达式后缀表达式 中缀表达式：运算符号位于两个运算数之间。如 a + b

2、* c - d / e 后缀表达式：运算符号位于两个运算数之后。如 a b c *+ d e /-例 6 2 / 3 - 4 2 *+ = ? 后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号 。1. 遇到运算数怎么办？如何“记住”目前还不未参与运算的数？ 2. 遇到运算符号怎么办？对应的运算数是什么？ 需要有种存储方法，能顺序存储运算数，需要有种存储方法，能顺序存储运算数， 并在需要时并在需要时“倒序倒序”输出！输出！第 3 章 限定性线性表栈和队列 对象: 6 (运算数 )例 6 2 / 3 - 4 2 *+ = ? 对象: 2 ( 运算数 )对象: / ( 运算符 ) 对象

3、: 3 (运算数 ) 对象: - (运算符) 对象: 4 (运算数 ) 对象: 2 (运算数 ) 对象: * ( 运算符 )对象: + (运算符) Pop: 8top62toptop2 6 /= 33333-= 0042top24*= 8880+= 88T( N ) = O ( N )8第 3 章 限定性线性表栈和队列 栈（Stack）：具有一定操作约束的线性表 只在一端（栈顶栈顶，Top）做 插入、删除 插入数据：入栈入栈（Push） 删除数据：出栈出栈（Pop） 后入先出后入先出：Last In First Out（LIFO）第 3 章 限定性线性表栈和队列 图图3.1 栈栈 ana2a1

4、进栈出栈栈顶栈底进栈出栈(a) 栈的示意图(b) 铁路调序栈的表示第 3 章 限定性线性表栈和队列 栈的抽象数据类型描述栈的抽象数据类型描述ADT Stack 数据对象集数据对象集：一个有0个或多个元素的有穷线性表。 基本操作：基本操作： （1） InitStack(&S) 初始条件： S为未初始化的栈。 操作结果： 将S初始化为空栈。 （2） ClearStack(&S) 初始条件： 栈S已经存在。 操作结果： 将栈S置成空栈。 第 3 章 限定性线性表栈和队列 （3） StackEmpty(S) 初始条件：栈S已经存在。 操作结果：若S为空栈，则函数值为TRUE，否则FAL

5、SE （4） Push(&S,e) 初始条件：栈S已经存在。 操作结果：在S的顶部插入(亦称压入)元素e；第 3 章 限定性线性表栈和队列 （5） Pop(&S, &e) 初始条件：栈S已经存在。 操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值。 （6） GetTop(S, &e) 初始条件： 栈S已经存在。 操作结果：取栈S的顶部元素。与Pop(&S, e)不同之处在于GetTop(S,&e)不改变栈顶的位置。第 3 章 限定性线性表栈和队列 Push 和 Pop 可以穿插交替进行； 按照操作系列 (1)Push(S,A), Push

6、(S,B),Push(S,C),Pop(S),Pop(S),Pop(S) 栈输出是？(2) 而Push(S,A), Pop(S),Push(S,B),Push(S,C),Pop(S),Pop(S) 栈输出是? 例 如果三个字符按ABC顺序压入堆栈 ABC的所有排列都可能是出栈的序列吗？ 可以产生CAB这样的序列吗？ CBAACB第 3 章 限定性线性表栈和队列 3.1.2 栈的表示和实现栈的表示和实现 1. 顺序栈顺序栈 顺序栈是用顺序存储结构实现的栈，由一个一维数组和一个记录栈顶元素位置的变量组成。define TRUE 1define FALSE 0typedef struct SElem

7、Type * base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /栈可使用的最大容量 SqStack; 第 3 章 限定性线性表栈和队列 图3.2 顺序栈中的进栈和出栈 43210432104321043210第 3 章 限定性线性表栈和队列 顺序栈基本操作的实现如下:(1) 初始化。 Status InitStack (SqStack &S) S.base = (SElemType *)malloc (STACK_INIT_SIZE *sizeof(SElemType); if (! S.base) exit (OVERFLOW); S

8、.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;第 3 章 限定性线性表栈和队列 (2) 取栈顶元素 Status GetTop(SqStack S, SElemType &e) if (S.top = = S.base) return ERROR; e= * (S.top-1); return OK;第 3 章 限定性线性表栈和队列 (3) 入栈。 Status Push(SqStack &S, SElemType e) if (S.top - S.base= S.stacksize) S.base=(SElem

9、Type*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; 第 3 章 限定性线性表栈和队列 (4) 出栈 Status Pop(SqStack &S, SelemType &e) if( S.top= =S.base) return ERROR; e=*-S.top; return OK;第

10、 3 章 限定性线性表栈和队列 在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0、M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。第 3 章 限定性线性表栈和队列 图3.3 共享栈 Stack:0M 1top0top1第 3 章 限定性线性表栈和队列 2. 链栈链栈 图3.4 链栈示意图 栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只

11、能在链栈的栈顶进行。 栈顶指针Top应该在链表的哪一头？ 第 3 章 限定性线性表栈和队列 3.2 栈的应用：表达式求值栈的应用：表达式求值 回忆：应用栈实现后缀表达式求值的基本过程回忆：应用栈实现后缀表达式求值的基本过程： 从左到右读入后缀表达式的各项（运算符或运算数）； 1.运算数运算数：入栈； 2.运算符运算符：从栈中弹出适当数量的运算数，计算并结果入栈； 3.最后，栈顶上的元素就是表达式的结果值。 第 3 章 限定性线性表栈和队列 中缀表达式求值中缀表达式求值 基本策略：将中缀表达式转换为后缀表达式，然后求值基本策略：将中缀表达式转换为后缀表达式，然后求值 如何将中缀表达式转换为后缀？

12、 观察一个简单例子： 3 + 4 * 5 -6 3 4 5 * + 6 1.运算数相对顺序不变 2.运算符号顺序发生改变 需要存储“等待中”的运算符号 要将当前运算符号与“等待中”的最后一个运算符号比较 有括号怎么办？有括号怎么办？栈第 3 章 限定性线性表栈和队列 例 3 * (4 +5 ) / 6 = ? 3 4 5 + * 6 /top输出: 3输入对象: 3 (操作数) 输入对象: * (乘法)输入对象: ( (左括号)输入对象: 4 (操作数)输入对象: + (加法)输入对象: 5 (操作数)输入对象: ) (右括号)输入对象: / (除法)输入对象: 6 (操作数)(4+5T( N

13、 ) = O ( N )*+*/6 /第 3 章 限定性线性表栈和队列 中缀表达式如何转换为后缀表达式中缀表达式如何转换为后缀表达式 从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理。 运算数：直接输出； 左括号：压入栈； 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）； 运算符： 若优先级大于栈顶运算符时，则把它压栈； 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈； 若各对象处理完毕，则把栈中存留的运算符一并输出。 第 3 章 限定性线性表栈和队列 栈的其他应用：栈的其他应用

14、： 函数调用及递归实现 深度优先搜索 回溯算法 第 3 章 限定性线性表栈和队列 3.3 栈与递归的实现栈与递归的实现 栈非常重要的一个应用是在程序设计语言中用来实现递归。递归递归是指在定义自身的同时又出现了对自身的调用。直接递归函数直接递归函数间接递归函数间接递归函数第 3 章 限定性线性表栈和队列 递归过程的实现递归过程的实现 一个函数调用另一个函数时，在运行被调用函数之前，系统做的工作有： (1) 保留本层参数与返回地址（将所有的实在参数、返回地址等信息传递给被调用函数保存）； (2) 给下层参数赋值（为被调用函数的局部变量分配存储区）； (3) 将程序转移到被调函数的入口。 第 3 章

15、 限定性线性表栈和队列 而从被调用函数返回调用函数之前，系统也应完成三件工作： (1) 保存被调函数的计算结果； (2) 恢复上层参数（释放被调函数的数据区）； (3) 依照被调函数保存的返回地址，将控制转移回调用函数。 当多个函数调用时按后调用先返回后调用先返回的原则。 第 3 章 限定性线性表栈和队列 系统将整个程序运行时所需的数据空间安排在一个栈中，每次调用一个函数时就为它在栈顶分配一个存储区，当一个函数返回时就释放它的存储区，当前正在运行的函数所有数据必在栈顶。void first(int,int); void first(int s,int t)void second(int); v

16、oid main() int i; int m,n; sencond(i); 2: first(m,n); 1: void second(int d) int x,y; 第 3 章 限定性线性表栈和队列 例例：n阶Hanoi塔问题：假设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2, ，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵循下列原则： (1) 每次只能移动一个圆盘； (2) 圆盘可以插在X、Y和Z中的任何一个塔座上； (3) 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 第 3 章 限定性线性表栈和

17、队列 如何实现移动圆盘的操作呢？如何实现移动圆盘的操作呢？ n=1时 1：X - Z n1时 1(n-1)：X - Y n：X - Z 1 (n-1)：Y - Z 如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同特征属性的问题，只是问题的规模小个1，因此可以用同样方法求解。第 3 章 限定性线性表栈和队列 void hanoi(int n,char x,char y,char z) /*将塔座X上编号为1至n的n个圆盘按规则搬到塔座Z上， Y可用作辅助塔座 */ 12 if(n=1) 3 move(x,1,z); /* 将编号为1的圆盘从X移动Z */4 else 5 ha

18、noi(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 第 3 章 限定性线性表栈和队列 下面给出三个盘子搬动时hanoi(3, A, B, C) 递归调用过程， 如图3.5所示。 hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1号搬到C move(A-B) 2号搬到B hanoi(1,C,A,B) move(C-B) 1号搬到B move(A-

19、C) 3号搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1号搬到A move(B-C) 2号搬到C hanoi(1,A,B,C) move(A-C) 1号搬到C 第 3 章 限定性线性表栈和队列 图3.5 Hanoi塔的递归函数运行示意图 321a321abc321abc321abc321abcbc321abc321abc321abc第 3 章 限定性线性表栈和队列 递归的优点递归的优点 通过上面的例子可看出，递归既是强有力的数学方法， 也是程序设计中一个很有用的工具。其特点是对递归问题描述简捷，结构清晰，程序的正确性容易证明。 递归算法求解问题的要

20、素递归算法求解问题的要素 递归算法就是算法中有直接或间接调用算法本身的算法。 递归算法的要点如下： (1) 问题具有类同自身的子问题的性质，被定义项在定义中的应用具有更小的尺度。 (2) 被定义项在最小尺度上有直接解。 第 3 章 限定性线性表栈和队列 设计递归算法的方法是： (1) 寻找方法，将问题化为原问题的子问题求解（例n!=n*(n-1)!）。 (2) 设计递归出口，确定递归终止条件(例求解n!时，当n=1时，n! =1)。 第 3 章 限定性线性表栈和队列 递归算法到非递归算法转换递归算法到非递归算法转换 递归算法具有两个特性： (1) 递归算法是一种分而治之、把复杂问题分解为简单问

21、题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效的。 （2） 递归算法的时间效率低。 第 3 章 限定性线性表栈和队列 1) 消除递归的原因 其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低且费时。 其二： 无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN语言中无递归机制 。 其三：递归算法是一次执行完，这在处理有些问题时不合适，也存在一个把递归算法转化为非递归算法的需求。 第 3 章 限定性线性表栈和队列 2) 简单递归消除 在简单情况下，将递归算法可简化为线性序列执行，可直接转换为循环实现。 递归进层三件事： 保存

22、本层参数、 返回地址; 传递参数，分配局部数据空间;控制转移。递归退层三件事： 恢复上层；传递结果；转断点执行。 第 3 章 限定性线性表栈和队列 尾递归尾递归 是指递归调用语句只有一个，而且是处于算法的最后。我们以阶乘问题的递归算法Fact(n)为例讨论尾递归算法的运行过程。为讨论方便，我们列出阶乘问题的递归算法Fact(n)，并简化掉参数n的出错检查语句，改写递归调用语句的位置在最后，算法如下： long Fact(int n) if(n=0) return 1; return n * Fact(n-1); 第 3 章 限定性线性表栈和队列 图图3.6 递归调用变化情况示意递归调用变化情况

23、示意 栈：调 f(2) 前调 f(1) 后2r3r返 f(1) 后2r3r返 f(3) 前调 f(2) 后3r调 f(0) 后2r3r1r返 f(2) 后3rf(3)f(2)f(1)f(0)6213*22*11第 3 章 限定性线性表栈和队列 图3.7 f(3)递归调用流程变化示意 f(3)f(2)f(1)f(0)3*22*111自下而上返回阶段自上而下递归进层阶段第 3 章 限定性线性表栈和队列 由图3.7可看出，整个计算包括自上而下递归调用进层和自下而上递归返回退层两个阶段，所有递归调用直接或间接依赖f(0)，所以整个阶段分两步，计算顺序在第二阶段，先计算f(0)f(1)f(n)，工作变量

24、y记录中间结果。 第 3 章 限定性线性表栈和队列 循环结构的阶乘问题算法Fact(n)如下： long Fact(int n) int fac=1; for(int i=1;inext = NULL; return OK; 第 3 章 限定性线性表栈和队列 （2）销毁队列Status DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear = Q.front-next;free (Q.front);Q.front = Q.rear; return OK;第 3 章 限定性线性表栈和队列 （3） 入队操作 Status EnQueue (Lin

25、kQueue &Q, QelemType e) p= (QueuePtr) malloc(sizeof(QNode); if (!p) exit ( OVERFLOW); p-data = e; p-next = NULL; Q.rear - next =p; Q.rear = p; return OK;第 3 章 限定性线性表栈和队列 （4） 出队操作 Status DeQueue (LinkQueue &Q, QelemType &e) if ( Q.front = Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.

26、front-next =p-next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;第 3 章 限定性线性表栈和队列 2. 队列的顺序存储实现队列的顺序存储实现 队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素位置的变量rear组成。 0 1 2 3 4 5frontrear例 一个工作队列 操作过程：（1）a, b, c, d依次入队（2）a, b, c依次出队（3）e, f入队 （4）g入队 (能入否？)abcdefrearrearrearrearrearrearfront第 3

27、 章 限定性线性表栈和队列 1 0 2 3 4 5 frontrear循环队列循环队列操作过程：（1）a, b, c, d依次入队abcdefgrearfront（2）a, b, c依次出队（3）e, f入队 （4）g入队rear（5）m, n 入队mnrear思考思考: （1）这种方案：堆栈空和满的判别条件是什么？）这种方案：堆栈空和满的判别条件是什么？ （2）为什么会出现空、满无法区分？根本原因？）为什么会出现空、满无法区分？根本原因？ （6）x 入队第 3 章 限定性线性表栈和队列 图3.9 循环队列 012354rearfront(a) 空队列012354e6e7e8e3e4e5012354(b) 队列满(b) 一般情况frontreare3e4e5frontrear第 3 章 限定性线性表栈和队列 如何区分队列如何区分队列“空空”和和“满满”另设一个标志位以区分队列是空还是满；少用一个元素空间，当队列头指针在队列尾指针的下一个