《刘勇3栈和队列.ppt》由会员分享，可在线阅读，更多相关《刘勇3栈和队列.ppt（27页珍藏版）》请在三一办公上搜索。
1、2023/6/27,北京化工大学信息学院 数据结构,1,栈(Stack)八进制数、括号匹配、行编辑程序、迷宫、表达式求值、出栈合法性队列(Queue)杨辉三角,第三章 栈和队列,2023/6/27,北京化工大学信息学院 数据结构,2,定义 只允许在一端插入和删除的线性表；允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。特点 后进先出(LIFO),栈(Stack),2023/6/27,北京化工大学信息学院 数据结构,3,ADT Stack/对象:由数据类型为StackData的元素构成 void push(StackData x);/进栈 void pop();/出栈 S
2、tackData top();/取栈顶 bool isEmpty();/判栈空否 bool isFull();/判栈满否(顺序栈),栈的主要操作,2023/6/27,北京化工大学信息学院 数据结构,4,top,空栈,top,top,top,top,top,a 进栈,b 进栈,a,a,b,a,b,c,d,e,e 进栈,a,b,c,d,e,f 进栈溢出,a,b,d,e,e 退栈,c,2023/6/27,北京化工大学信息学院 数据结构,5,top,c 退栈,b 退栈,a,b,a,a 退栈,空栈,top,a,b,d,d 退栈,c,top,a,b,c,top,top,2023/6/27,北京化工大学信息
3、学院 数据结构,6,栈的链接表示 链式栈,链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作,top,2023/6/27,北京化工大学信息学院 数据结构,7,栈的应用举例 1 八进制数,2023/6/27,北京化工大学信息学院 数据结构,8,栈的应用举例 2 括号匹配,()()()()匹配)(不匹配()不匹配后出现的左括号先匹配 栈,2023/6/27,北京化工大学信息学院 数据结构,9,2023/6/27,北京化工大学信息学院 数据结构,10,栈的应用举例 3 行编辑程序,#退格符 退行符switch(ch)case#:s.pop();break;case:
4、s.clear();break;default:s.push(ch);break;,2023/6/27,北京化工大学信息学院 数据结构,11,栈的应用举例 4 迷宫,到了一个位置，先往东走，走不通再顺时针换方向往南，西，北,2023/6/27,北京化工大学信息学院 数据结构,12,栈的应用举例 4 迷宫,求迷宫路径算法的基本思想是：1、起点S入栈2、反复执行以下步骤，直到栈为空，或者找到终点E（1）取栈顶m，标记m已被访问，根据m的方向找到下一个位置next；（2）如果next不是墙壁，也没有被访问过，将next入栈（3）否则换方向继续找下一个位置（4）4个方向都不能通过，出栈，回到第（1）步
5、3、找到终点E，迷宫走出 在找到终点E之前，栈空了，说明迷宫没有出去的路径,2023/6/27,北京化工大学信息学院 数据结构,13,栈的应用举例 5 表达式运算,2023/6/27,北京化工大学信息学院 数据结构,14,栈的应用举例 5 表达式运算,2023/6/27,北京化工大学信息学院 数据结构,15,栈的应用举例 5 表达式运算,操作数栈D，运算符栈O1、操作数入栈D2、遇到运算符OP1，和O栈顶运算符OP2比较：（1）如果OP2优先级高，则将两个栈的元素出栈，做运算，将运算结果入栈D；（2）如果OP1优先级高，OP1入栈O,2023/6/27,北京化工大学信息学院 数据结构,16,栈
6、的应用举例 6 出栈合法性,算法：1、辅助数组 bool isPushedN+1=false,1入栈S，isPushed1=true2、遍历出栈序列，对每个数字n，执行以下操作：（1）取S栈顶t，将t,t+1,t+2.n的所有不曾入栈的数字入栈，并在辅助数组中标记对应下标为true（2）取S栈顶t，若s=n，S出栈；若s!=n，则出栈序列非法。,已知自然数1，2，.，N（1=N=100）依次入栈，请问序列C1，C2，.，CN是否为合法的出栈序列。如3 4 2 1 5是合法的而3 5 1 4 2不是合法的,2023/6/27,北京化工大学信息学院 数据结构,17,定义队列是只允许在一端删除，在另
7、一端插入的线性表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,First In First Out),a0 a1 a2 an-1,front,rear,队列(Queue),2023/6/27,北京化工大学信息学院 数据结构,18,ADT Queue/对象:由数据类型为QueueData的元素构成 void push(QueueData x);/进队 void pop();/出队并取队头 QueueData front();/取队头 bool isEmpty();/判队空否 bool isFull();/判队满否(顺序队列),队列的主要操作,2
8、023/6/27,北京化工大学信息学院 数据结构,19,队列的进队和出队,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C,D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,2023/6/27,北京化工大学信息学院 数据结构,20,队列的进队和出队原则,进队时队尾指针先进一 rear=rear+1，再将新元素按 rear 指示位置加入。出队时队头指针先
9、进一 front=front+1，再将下标为 front 的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。解决办法之一：将队列元素存放数组首尾相接，形成循环(环形)队列。,2023/6/27,北京化工大学信息学院 数据结构,21,队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从QueueSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%QueueSize;队尾指针进1:rear=(rear+1)%QueueSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%Queu
10、eSize=front,循环队列(Circular Queue),2023/6/27,北京化工大学信息学院 数据结构,22,0,1,2,3,4,5,6,7,front,0,1,2,3,4,5,6,7,front,0,1,2,3,4,5,6,7,front,rear,A,A,B,C,rear,rear,空队列,A进队,B,C进队,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A退队,B退队,0,1,2,3,4,5,6,7,D,E,F,G,H,I进队,front,B,C,rear,A,front,B,C,rear,front,C,rear,D,E,F,G,H,I,2023/6/2
11、7,北京化工大学信息学院 数据结构,23,队列的链接表示 链式队列,队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 front=NULL,front,rear,2023/6/27,北京化工大学信息学院 数据结构,24,队列的应用举例 逐行打印二项展开式(a+b)i 的系数,杨辉三角形(Pascals triangle),2023/6/27,北京化工大学信息学院 数据结构,25,分析第 i 行元素与第 i+1行元素的关系,从前一行的数据可以计算下一行的数据,0 1 1 0,2023/6/27,北京化工大学信息学院 数据结构,26,从第 i 行数据计算并存放第 i+1 行数据,1 2 1 0 1 3 3 1 0 1 4 6,s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1,s+t s=t s=t s=t s=t s=t s=t s=t s=t,s+t s+t s+t s+t s+t s+t s+t s+t,2023/6/27,北京化工大学信息学院 数据结构,27,求第n层算法：（1）初始化队列为0 1 0，将第2、3步循环n-1次（2）将队列的前两个元素s,t求和，结果入队，删除队首s，直到t为0为止（3）0入队,
