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