Ch4 栈和队列.ppt

《Ch4 栈和队列.ppt》由会员分享，可在线阅读，更多相关《Ch4 栈和队列.ppt（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、栈和队列栈和队列曹迎春曹迎春学习目标1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。2022/12/202重点和难点n掌握栈和队列的特点，以便能在应用问题中正确使用。2022/12/203知识点n顺序栈n链栈n循环队列n链队列2022/12/204课前思考n什么是线性结构？n你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n的次序往上叠的，那么使用时候的次序应是什么样的？n在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？202

2、2/12/205n栈和队列都是线性数据结构栈：后进先出队列：先进先出n和线性表相比，它们的插入和删除操作受更多的约束和限定，故称为受限的线性表结构。2022/12/206插入删除线性表Insert(L,i,x)(1in+1)Delete(L,i)(1in)线性表允许在表内任一位置进行插入和删除栈Insert(L,n+1,x)Delete(L,n)栈只允许在表尾一端进行插入和删除队列Insert(L,n+1,x)Delete(L,1)队列只允许在表尾一端进行插入，在表头一端进行删除。栈和队列栈栈2022/12/207栈的类型定义n栈（栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表

3、。n表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（bottom）。n当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈。2022/12/208栈的类型定义n堆栈的特点：后进先出（LastInFirstOut，简称LIFO）2022/12/209栈n入栈和出栈2022/12/2010堆栈的抽象数据类型定义2022/12/2011堆栈的抽象数据类型定义2022/12/2012堆栈的java接口2022/12/2013堆栈中的异常n堆栈为空时出栈或取栈顶元素抛出异常2022/12/2014栈的顺

4、序存储实现n顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。n根据数组操作的特性，选择数组下标大的一端，即线性表顺序存储的表尾来作为栈顶。2022/12/2015Stack的顺序存储实现2022/12/2016Stack的顺序存储实现2022/12/2017Stack的顺序存储实现2022/12/2018栈的链式存储实现n链栈即采用链表作为存储结构实现的栈。n当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶。n入栈操作的实现：n出栈操作的实现：2022/12/2019将top后移栈的链式存储实现n思考：能否将链栈中的指针方向反过来

5、，从栈底到栈顶？2022/12/2020不行，如果反过来的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。堆栈的链式存储实现2022/12/2021堆栈的链式存储实现2022/12/2022堆栈的链式存储实现2022/12/2023栈的应用举例n数制转换n括弧匹配检验n迷宫求解问题n表达式求值问题n递归函数的实现2022/12/2024数制转换n数制转换原理：N=(Ndivd)d+Nmoddn例如：(1348)10=(2504)8，动画演示n思考：怎样将一个十进制的数值转换成一个八进制的数值呢？2022/12/2025用栈实现数制转换2022/12/2026思考n用栈处理数制转换

6、问题的好处在哪里？2022/12/2027括弧匹配检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（）或（）等为正确的匹配，（）或（）或()）均为错误的匹配。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。2022/12/2028括弧匹配检验n例如考虑下列括号序列：n错误匹配的情况：来的右括弧非是所期待的；来的是不速之客；直到结束，也没有到来所期待的。2022/12/2029()12345678括弧匹配检验n三类“错误匹配”情况对应到栈的操作：和栈顶的左括弧不相匹配；栈中并

7、没有左括弧等在哪里；栈中还有左括弧没有等到和它相匹配的右括弧。n思考：试着写这个算法，你的算法调试成功了吗？如果不正确的话，那么你看看哪些细节没有考虑到？2022/12/20302022/12/20312022/12/2032迷宫求解问题n思考：你做过迷宫的游戏吗？你从入口进去之后是如何找到出口的？2022/12/2033迷宫的二维数组模拟2022/12/2034迷宫求解问题n求迷宫中一条路径的算法的基本思想基本思想是：若当前位置可通，则纳入当前路径，并继续朝下一位置探索；若当前位置不可通，则应顺着来的方向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周四个方块均不可通

8、，则应从当前路径上删除该通道块。2022/12/2035迷宫求解问题n所谓“下一位置下一位置”指的是“当前位置当前位置”四周四个方向四周四个方向（下、右、上、左）上相邻的方块（下、右、上、左）上相邻的方块。n假设以栈栈S记录记录当前路径当前路径，则栈顶栈顶中存放的是存放的是当前路径上最后一个通道块当前路径上最后一个通道块。n纳入路径纳入路径的操作即为的操作即为当前位置入栈当前位置入栈；n从当前路径上删除前一通道块从当前路径上删除前一通道块的操作即为的操作即为出出栈栈。2022/12/2036初始化，将起点加入堆栈；while(堆栈不空堆栈不空)取出栈顶位置作为当前位置；如果当前位置是终点，则使

9、用堆栈记录的路径标记从起点至终点的路径；否则按照向下、右、上、左的顺序将当前位置下一个可以探索的位置入栈；/从堆栈取出的探索方向顺序则是左、上、右、下如果当前位置四周均不可通则当前位置出栈；37迷宫单元的定义2022/12/2038迷宫中从起点到终点路径的求解2022/12/20392022/12/20402022/12/20412022/12/20422022/12/2043表达式求值问题n表达式定义：表达式:=操作数运算符操作数操作数:=简单变量|表达式简单变量:=标识符|无符号整数n二元表达式的三种标识方法：假设Exp=S1+OP+S2，则称OP+S1+S2为表达式的前缀表示法前缀表示法

10、（简称前缀式前缀式）称S1+OP+S2为表达式的中缀表示法中缀表示法（简称中缀式中缀式）称S1+S2+OP为表达式的后缀表示法后缀表示法（简称后缀式后缀式）2022/12/2044表达式求值问题n例如：若a*b+(c-d/e)*f，则它的前缀式为：+*ab*-c/def中缀式为：a*b+c-d/e*f后缀式为：ab*cde/-f*+（动画演示）2022/12/2045表达式求值问题n综合比较它们之间的关系可得下列结论：1.三式中的“操作数之间的相对次序相同操作数之间的相对次序相同”；2.三式中的“运算符之间的相对次序不同运算符之间的相对次序不同”；3.中缀式丢失了括弧信息，致使运算的次序不确定

11、；4.前缀式的运算规则前缀式的运算规则为：连续出现的两个操作数和在连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式；它们之前且紧靠它们的运算符构成一个最小表达式；5.后缀式的运算规则后缀式的运算规则为：n运算符在式中出现的顺序恰为表达式的运算顺序；运算符在式中出现的顺序恰为表达式的运算顺序；n每个运算符和在它之前出现且紧靠它的两个操作数构成一每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；个最小表达式；2022/12/2046表达式求值问题n讨论后缀式的情况。1.即转换过程中不改变原表达式中操作数之间的相对次序；2.即转换过程主要是改变原表达式中各个运算符之

12、间的相对次序；3.因此，中缀式没什么用；4.虽然前缀式中已经没有原表达式中的括弧，但它已经包含了原表达式中运算的规则；5.若将原表达式转换成它的后缀式，那么我们就可以按后缀式中运算符出现的先后次序来对表达式进行运算了。2022/12/2047表达式求值问题如何按后缀式进行运算？求值规则：先找运算符，后找操作数。思考：这个算法不难吧？你头脑中是不是已经有了这个算法的大致模样了？动画演示2022/12/2048表达式求值问题n如何由原表达式转换成后缀式？例一例一原表达式：a*b/c*d-e+f后缀式：ab*c/d*e-f+（动画演示）例二例二原表达式：a+b*c-d/e*f后缀式：abc*+de/

13、f*-n优先数2022/12/2049运算符#(+-*/*优先数-1011223表达式求值问题n从原表达式求得后缀式的规则为：设立运算符栈栈；设表达式的结束符为“#”，预设运算符栈的栈底为“#”；若当前字符是操作数，则直接发送给后缀式；若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式；若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式；“(”对它之前后的运算符起隔离作用，则若当前运算符为“(”时进栈；)可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为(止。2022/12/2050递归函数的实现n当一

14、个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。n从被调用函数返回调用函数之前，应该完成：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。2022/12/2051递归函数的实现n当多个函数嵌套调用时，由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行栈式管理栈式管理。2022/12/2052递归函数的实现n在执行递归函数的过程中需要一个递归工作栈。它的作用是:将递归调用时的实在参数和函数返回

15、地址传递给下一层执行的递归函数；保存本层的参数和局部变量，以便从下一层返回时重新使用它们。2022/12/2053递归函数的实现n递归过程执行过程中占用的数据区，称之为递归递归工作栈。工作栈。n每一层的递归参数等数据合成一个记录，称之为递归工作记录递归工作记录。n栈顶记录指示当前层的执行情况，称之为当前活当前活动记录动记录。n递归工作栈的栈顶指针，称之为当前环境指针当前环境指针。2022/12/2054递归函数的实现n例：梵塔函数n动画演示2022/12/2055importjava.util.Stack;publicclassHanoipublicstaticvoidmain(Stringa

16、rgs)Hanoihnt=newHanoi(6);publicHanoi(intcount)this.count=count;hanoi(count,A,B,C,0);2022/12/2056privatevoidhanoi(intn,charstart,chartransit,chardestination,intlevel)if(n=1)move(n,start,destination);return;level+;hanoi(n-1,start,destination,transit,level);move(n,start,destination);hanoi(n-1,transit,s

17、tart,destination,level);2022/12/2057privateclassElementpublicintn,level;publiccharstart,transit,destination;publicElement(intn,charstart,chartransit,chardestination,intlevel)this.n=n;this.start=start;this.transit=transit;this.destination=destination;this.level=level;58privatevoidhanoi_stack(intn,cha

18、rstart,chartransit,chardestination,intlevel)Stackstack=newStack();stack.push(newElement(n,start,transit,destination,level);while(!stack.empty()Elemente=stack.pop();if(e.n=1)move(e.start,e.destination);elsestack.push(newElement(n-1,e.transit,e.start,e.destination,level);move(e.start,e.destination);st

19、ack.push(newElement(n-1,e.start,e.destination,e.transit,level);e=null;2022/12/2059privatevoidmove(intmark,charstart,chardestination)StringBuffersb=newStringBuffer();sb.append(move);sb.append(mark);sb.append(from);sb.append(start);sb.append(to);sb.append(destination);sb.append(rn);System.out.print(sb

20、.toString();sb.delete(0,sb.length();2022/12/2060privatevoidmove(charstart,chardestination)StringBuffersb=newStringBuffer();sb.append(move);sb.append(thetopdiskfrom);sb.append(start);sb.append(to);sb.append(destination);sb.append(rn);System.out.print(sb.toString();sb.delete(0,sb.length();privateintco

21、unt;/初始规模2022/12/2061队列队列2022/12/2062队列的定义n队列（queue）简称队，是一种特殊的线性表。仅允许在表的一端进行插入，而在表的另一端进行删除。n在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。n向队尾插入元素称为进队或入队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。n队列的特性：（FirstInFirstOut,简称FIFO）2022/12/2063队列的抽象数据类型定义2022/12/2064队列的抽象数据类型定义2022/12/2065Queue接

22、口2022/12/2066异常类定义2022/12/2067队列的顺序存储实现2022/12/2068循环数组n设想数组A0.capacity-1中的单元不是排成一行，而是围成一个圆环，即A0接在Acapacity-1的后面。这种意义下的数组称为循环数组。2022/12/2069循环队列n循环队列是队列的一种顺序存储表示。n为什么要称作循环队列而不说是顺序队列呢？n动画演示2022/12/2070循环队列的操作n入队操作将新元素入队时，可在队尾指针指示的单元中存入新元素，并将队尾指针rear按逆时针方向移一位。n出队操作将队首指针front依逆时针方向移一位。2022/12/2071循环队列的

23、操作2022/12/2072思考n判别循环队列为空的条件应该是什么？在队列初始化的函数中，设置队头和队尾指针均为0，那么能否由队头指针为0来作为队列空的判别条件呢？n由于顺序存储结构是一次性地分配空间，因此在入队列的操作中首先应该判别当前队列是否已经满了，那么队列满的判别条件又是什么呢？2022/12/2073循环队列中各关键量2022/12/2074Queue的顺序存储实现2022/12/2075Queue的顺序存储实现2022/12/2076Queue的顺序存储实现2022/12/2077Queue的顺序存储实现2022/12/2078队列的链式存储实现n采用带头结点的单链表结构实现队列的链式存储。选择链表的头部作为队首，链表的尾部作为队尾。2022/12/2079Queue的链式存储实现2022/12/20802022/12/208182排队问题的系统模拟n编制一个事件驱动仿真程序以模拟理发馆内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在馆内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。n动画演示2022/12/20832022/12/2084