刘勇3栈和队列.ppt
《刘勇3栈和队列.ppt》由会员分享,可在线阅读,更多相关《刘勇3栈和队列.ppt(27页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、刘勇3栈和队列 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望定义定义定义定义 只允许在一端插入和删除的线性表;只允许在一端插入和删除的线性表;只允许在一端插入和删除的线性表;只允许在一端插入和删除的线性表;允许插入和删除的一端称为允许插入和删除的一端称为允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶栈顶栈顶(top)(top),另一另一另一另一端称为端称为端称为端称为栈底栈底栈底栈底(bottom)(bottom)。特点特点特点特点 后进先出后进先出后
2、进先出后进先出(LIFO)(LIFO)栈栈(Stack)退栈进栈a0an-1an-2topbottom11/6/20222北京化工大学信息学院 数据结构ADT Stack /对象对象:由数据类型为由数据类型为StackData的元素构成的元素构成 void push(StackData x);/进栈进栈 void pop();/出栈出栈 StackData top();/取栈顶取栈顶 bool isEmpty();/判栈空否判栈空否 bool isFull();/判栈满否判栈满否(顺序栈顺序栈)栈的主要操作栈的主要操作11/6/20223北京化工大学信息学院 数据结构 top空栈toptopt
3、optoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈c11/6/20224北京化工大学信息学院 数据结构topc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop11/6/20225北京化工大学信息学院 数据结构栈的链接表示栈的链接表示 链式栈链式栈链式栈无栈满问题,空间可扩充链式栈无栈满问题,空间可扩充链式栈无栈满问题,空间可扩充链式栈无栈满问题,空间可扩充插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行链式栈的栈顶在链头链式栈的栈顶在链头链式栈的栈顶在链头链式栈的栈顶在链
4、头适合于多栈操作适合于多栈操作适合于多栈操作适合于多栈操作top11/6/20226北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 1 八进制数八进制数11/6/20227北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 2 括号匹配括号匹配()()()()匹配)(不匹配()不匹配后后出现的左括号出现的左括号先先匹配匹配 栈栈11/6/20228北京化工大学信息学院 数据结构11/6/20229北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 3 行编辑程序行编辑程序#退格符 退行符switch(ch)case#:s.pop();break;case:s.clear();b
5、reak;default:s.push(ch);break;11/6/202210北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 4 迷宫迷宫到了一个位置,先往东东走,走不通再顺时针换方向往南,西,北11/6/202211北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 4 迷宫迷宫求迷宫路径算法的基本思想是:求迷宫路径算法的基本思想是:1、起点、起点S入栈入栈2、反复执行以下步骤,直到栈为空,或者找到终点、反复执行以下步骤,直到栈为空,或者找到终点E(1)取栈顶)取栈顶m,标记,标记m已被访问,根据已被访问,根据m的方向找到下一个位置的方向找到下一个位置next;(2)如果)如
6、果next不是墙壁,也没有被访问过,将不是墙壁,也没有被访问过,将next入栈入栈(3)否则换方向继续找下一个位置)否则换方向继续找下一个位置(4)4个方向都不能通过,出栈,回到第(个方向都不能通过,出栈,回到第(1)步)步3、找到终点、找到终点E,迷宫走出,迷宫走出 在找到终点在找到终点E之前,栈空了,说明迷宫没有出去的路径之前,栈空了,说明迷宫没有出去的路径11/6/202212北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表达式运算11/6/202213北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表达式运算11/6/202214北京化工大
7、学信息学院 数据结构栈的应用举例栈的应用举例 5 表达式运算表达式运算操作数栈D,运算符栈O1、操作数入栈D2、遇到运算符OP1,和O栈顶运算符OP2比较:(1)如果OP2优先级高,则将两个栈的元素出栈,做运算,将运算结果入栈D;(2)如果OP1优先级高,OP1入栈O11/6/202215北京化工大学信息学院 数据结构栈的应用举例栈的应用举例 6 出栈合法性出栈合法性算法:1、辅助数组 bool isPushedN+1=false,1入栈S,isPushed1=true2、遍历出栈序列,对每个数字n,执行以下操作:(1)取S栈顶t,将t,t+1,t+2.n的所有不曾入栈的数字入栈,并在辅助数组
8、中标记对应下标为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不是合法的11/6/202216北京化工大学信息学院 数据结构定义定义定义定义队列是只允许在一端删除,在另一端插入的线性表队列是只允许在一端删除,在另一端插入的线性表队列是只允许在一端删除,在另一端插入的线性表队列是只允许在一端删除,在另一端插入的线性表允许删除的一端叫做允许删除的一端叫做允许删除的一端叫做允许删除的一端叫做队头队头队头队头(front)(fr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 刘勇 队列
限制150内