刘勇3栈和队列

《刘勇3栈和队列》由会员分享，可在线阅读，更多相关《刘勇3栈和队列（27页珍藏版）》请在装配图网上搜索。

1、2022-11-26北京化工大学信息学院 数据结构12022-11-26北京化工大学信息学院 数据结构2退栈进栈a0an-1an-2topbottom2022-11-26北京化工大学信息学院 数据结构3ADT Stack /对象对象:由数据类型为由数据类型为StackData的元素构成的元素构成 void push(StackData x);/进栈进栈 void pop();/出栈出栈 StackData top();/取栈顶取栈顶 bool isEmpty();/判栈空否判栈空否 bool isFull();/判栈满否判栈满否(顺序栈顺序栈)2022-11-26北京化工大学信息学院 数据结构

2、4 top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈c2022-11-26北京化工大学信息学院 数据结构5topc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop2022-11-26北京化工大学信息学院 数据结构6top2022-11-26北京化工大学信息学院 数据结构72022-11-26北京化工大学信息学院 数据结构82022-11-26北京化工大学信息学院 数据结构92022-11-26北京化工大学信息学院 数据结构10#退格符 退行符switch(ch)case#:s.pop();br

3、eak;case:s.clear();break;default:s.push(ch);break;2022-11-26北京化工大学信息学院 数据结构11到了一个位置，先往东东走，走不通再顺时针换方向往南，西，北2022-11-26北京化工大学信息学院 数据结构12求迷宫路径算法的基本思想是：求迷宫路径算法的基本思想是：1、起点、起点S入栈入栈2、反复执行以下步骤，直到栈为空，或者找到终点、反复执行以下步骤，直到栈为空，或者找到终点E（1）取栈顶）取栈顶m，标记，标记m已被访问，根据已被访问，根据m的方向找到下一个位置的方向找到下一个位置next；（2）如果）如果next不是墙壁，也没有被访问

4、过，将不是墙壁，也没有被访问过，将next入栈入栈（3）否则换方向继续找下一个位置）否则换方向继续找下一个位置（4）4个方向都不能通过，出栈，回到第（个方向都不能通过，出栈，回到第（1）步）步3、找到终点、找到终点E，迷宫走出，迷宫走出 在找到终点在找到终点E之前，栈空了，说明迷宫没有出去的路径之前，栈空了，说明迷宫没有出去的路径2022-11-26北京化工大学信息学院 数据结构132022-11-26北京化工大学信息学院 数据结构142022-11-26北京化工大学信息学院 数据结构15操作数栈D，运算符栈O1、操作数入栈D2、遇到运算符OP1，和O栈顶运算符OP2比较：（1）如果OP2优先

5、级高，则将两个栈的元素出栈，做运算，将运算结果入栈D；（2）如果OP1优先级高，OP1入栈O2022-11-26北京化工大学信息学院 数据结构16算法：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

6、5 1 4 2不是合法的2022-11-26北京化工大学信息学院 数据结构17a0 a1 a2 an-1frontrear2022-11-26北京化工大学信息学院 数据结构18ADT Queue/对象对象:由数据类型为由数据类型为QueueData的元素构成的元素构成 void push(QueueData x);/进队进队 void pop();/出队并取队头出队并取队头 QueueData front();/取队头取队头 bool isEmpty();/判队空否判队空否 bool isFull();/判队满否判队满否(顺序队列顺序队列)2022-11-26北京化工大学信息学院 数据结构19

7、front rear空队列front rearA进队Afront rearB进队A Bfront rearC,D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进进队C D E F GC D E F Gfront rearH进进队,溢出2022-11-26北京化工大学信息学院 数据结构20n n 2022-11-26北京化工大学信息学院 数据结构212022-11-26北京化工大学信息学院 数据结构2201234567front01234567front01234567frontrearAABCrearrear空队列空队列A进

8、队进队B,C进队进队0123456701234567A退队退队B退队退队01234567D,E,F,G,H,I进队进队frontBCrearAfrontBCrearfrontCrearDEF GHI2022-11-26北京化工大学信息学院 数据结构23frontrear2022-11-26北京化工大学信息学院 数据结构242022-11-26北京化工大学信息学院 数据结构250 1 1 0ts+ti=40 1 3 3 1 0si=51 4 6 4 1i=30 1 2 1 02022-11-26北京化工大学信息学院 数据结构261 2 1 0 1 3 3 1 0 1 4 6s=0 t=1 t=2 t=1 t=0 t=1 t=3 t=3 t=1 t=0 t=1s+t s=t s=t s=t s=t s=t s=t s=t s=ts+t s+t s+t s+t s+t s+t s+t s+t2022-11-26北京化工大学信息学院 数据结构27求第求第n层算法：层算法：（1）初始化队列为）初始化队列为0 1 0，将第将第2、3步循环步循环n-1次次（2）将队列的前两个元素）将队列的前两个元素s,t求和，结果入队，删除求和，结果入队，删除队首队首s，直到，直到t为为0为止为止（3）0入队入队