《Ch栈和队列实用.pptx》由会员分享，可在线阅读，更多相关《Ch栈和队列实用.pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、重点和难点掌握栈和队列的特点，以便能在应用问题中正确使用。2023/3/231第1页/共83页知识点顺序栈链栈循环队列链队列2023/3/232第2页/共83页课前思考什么是线性结构？你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,n的次序往上叠的，那么使用时候的次序应是什么样的？在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？2023/3/233第3页/共83页栈和队列都是线性数据结构栈：后进先出队列：先进先出和线性表相比，它们的插入和删除操作受更多的约束和限定，故称为受限的线性表结构。2023/3/234插入删除线性表Insert(L,i,x)(1in+1)Delete(L,
2、i)(1in)线性表允许在表内任一位置进行插入和删除栈Insert(L,n+1,x)Delete(L,n)栈只允许在表尾一端进行插入和删除队列Insert(L,n+1,x)Delete(L,1)队列只允许在表尾一端进行插入，在表头一端进行删除。栈和队列第4页/共83页栈2023/3/235第5页/共83页栈的类型定义栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。表中进行插入、删除操作的一端称为栈顶（top），栈顶保存的元素称为栈顶元素。相对的，表的另一端称为栈底（bottom）。当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删除元素又称为出栈或退栈
3、。2023/3/236第6页/共83页栈的类型定义堆栈的特点：后进先出（LastInFirstOut，简称LIFO）2023/3/237第7页/共83页栈入栈和出栈2023/3/238第8页/共83页堆栈的抽象数据类型定义2023/3/239第9页/共83页堆栈的抽象数据类型定义2023/3/2310第10页/共83页堆栈的java接口2023/3/2311第11页/共83页堆栈中的异常堆栈为空时出栈或取栈顶元素抛出异常2023/3/2312第12页/共83页栈的顺序存储实现顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。根据数组操作的特性，选择数组下
4、标大的一端，即线性表顺序存储的表尾来作为栈顶。2023/3/2313第13页/共83页Stack的顺序存储实现2023/3/2314第14页/共83页Stack的顺序存储实现2023/3/2315第15页/共83页Stack的顺序存储实现2023/3/2316第16页/共83页栈的链式存储实现链栈即采用链表作为存储结构实现的栈。当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶。入栈操作的实现：出栈操作的实现：2023/3/2317将top 后移第17页/共83页栈的链式存储实现思考：能否将链栈中的指针方向反过来，从栈底到栈顶？2023/3/2318不行，如果反过来的话，删
5、除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。第18页/共83页堆栈的链式存储实现2023/3/2319第19页/共83页堆栈的链式存储实现2023/3/2320第20页/共83页堆栈的链式存储实现2023/3/2321第21页/共83页栈的应用举例数制转换括弧匹配检验迷宫求解问题表达式求值问题递归函数的实现2023/3/2322第22页/共83页数制转换数制转换原理：N=(Ndivd)d+Nmodd例如：(1348)10=(2504)8，动画演示思考：怎样将一个十进制的数值转换成一个八进制的数值呢？2023/3/2323第23页/共83页用栈实现数制转换2023/3/2324第24
6、页/共83页思考用栈处理数制转换问题的好处在哪里？2023/3/2325第25页/共83页括弧匹配检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（）或（）等为正确的匹配，（）或（）或()）均为错误的匹配。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。2023/3/2326第26页/共83页括弧匹配检验例如考虑下列括号序列：错误匹配的情况：来的右括弧非是所期待的；来的是不速之客；直到结束，也没有到来所期待的。2023/3/2327()12345678第27页/共83页括弧
7、匹配检验三类“错误匹配”情况对应到栈的操作：和栈顶的左括弧不相匹配；栈中并没有左括弧等在哪里；栈中还有左括弧没有等到和它相匹配的右括弧。思考：试着写这个算法，你的算法调试成功了吗？如果不正确的话，那么你看看哪些细节没有考虑到？2023/3/2328第28页/共83页2023/3/2329第29页/共83页2023/3/2330第30页/共83页迷宫求解问题思考：你做过迷宫的游戏吗？你从入口进去之后是如何找到出口的？2023/3/2331第31页/共83页迷宫的二维数组模拟2023/3/2332第32页/共83页迷宫求解问题求迷宫中一条路径的算法的基本思想是：若当前位置可通，则纳入当前路径，并继
8、续朝下一位置探索；若当前位置不可通，则应顺着来的方向退回到前一通道块，然后朝着除来向之外的其他方向继续探索；若该通道块的四周四个方块均不可通，则应从当前路径上删除该通道块。2023/3/2333第33页/共83页迷宫求解问题所谓“下一位置”指的是“当前位置”四周四个方向（下、右、上、左）上相邻的方块。假设以栈S记录当前路径，则栈顶中存放的是当前路径上最后一个通道块。纳入路径的操作即为当前位置入栈；从当前路径上删除前一通道块的操作即为出栈。2023/3/2334第34页/共83页初始化，将起点加入堆栈；while(堆栈不空)取出栈顶位置作为当前位置；如果当前位置是终点，则使用堆栈记录的路径标记从
9、起点至终点的路径；否则按照向下、右、上、左的顺序将当前位置下一个可以探索的位置入栈；/从堆栈取出的探索方向顺序则是左、上、右、下如果当前位置四周均不可通则当前位置出栈；35第35页/共83页迷宫单元的定义2023/3/2336第36页/共83页迷宫中从起点到终点路径的求解2023/3/2337第37页/共83页2023/3/2338第38页/共83页2023/3/2339第39页/共83页2023/3/2340第40页/共83页2023/3/2341第41页/共83页表达式求值问题表达式定义：表达式:=操作数运算符操作数操作数:=简单变量|表达式简单变量:=标识符|无符号整数二元表达式的三种标
10、识方法：假设Exp=S1+OP+S2，则称OP+S1+S2为表达式的前缀表示法（简称前缀式）称S1+OP+S2为表达式的中缀表示法（简称中缀式）称S1+S2+OP为表达式的后缀表示法（简称后缀式）2023/3/2342第42页/共83页表达式求值问题例如：若a*b+(c-d/e)*f，则它的前缀式为：+*ab*-c/def中缀式为：a*b+c-d/e*f后缀式为：ab*cde/-f*+（动画演示）2023/3/2343第43页/共83页表达式求值问题综合比较它们之间的关系可得下列结论：1.三式中的“操作数之间的相对次序相同”；2.三式中的“运算符之间的相对次序不同”；3.中缀式丢失了括弧信息，
11、致使运算的次序不确定；4.前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式；5.后缀式的运算规则为：运算符在式中出现的顺序恰为表达式的运算顺序；每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；2023/3/2344第44页/共83页表达式求值问题讨论后缀式的情况。1.即转换过程中不改变原表达式中操作数之间的相对次序；2.即转换过程主要是改变原表达式中各个运算符之间的相对次序；3.因此，中缀式没什么用；4.虽然前缀式中已经没有原表达式中的括弧，但它已经包含了原表达式中运算的规则；5.若将原表达式转换成它的后缀式，那么我们就可以按后缀式中运算
12、符出现的先后次序来对表达式进行运算了。2023/3/2345第45页/共83页表达式求值问题如何按后缀式进行运算？求值规则：先找运算符，后找操作数。思考：这个算法不难吧？你头脑中是不是已经有了这个算法的大致模样了？动画演示2023/3/2346第46页/共83页表达式求值问题如何由原表达式转换成后缀式？例一原表达式：a*b/c*d-e+f后缀式：ab*c/d*e-f+（动画演示）例二原表达式：a+b*c-d/e*f后缀式：abc*+de/f*-优先数2023/3/2347运算符#(+-*/*优先数-1011223第47页/共83页表达式求值问题从原表达式求得后缀式的规则为：设立运算符栈；设表达
13、式的结束符为“#”，预设运算符栈的栈底为“#”；若当前字符是操作数，则直接发送给后缀式；若当前字符为运算符且优先数大于栈顶运算符，则进栈，否则退出栈顶运算符发送给后缀式；若当前字符是结束符，则自栈顶至栈底依次将栈中所有运算符发送给后缀式；“(”对它之前后的运算符起隔离作用，则若当前运算符为“(”时进栈；)可视为自相应左括弧开始的表达式的结束符，则从栈顶起，依次退出栈顶运算符发送给后缀式直至栈顶字符为(止。2023/3/2348第48页/共83页递归函数的实现当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调
14、用函数的局部变量分配存储区；将控制转移到被调用函数的入口。从被调用函数返回调用函数之前，应该完成：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。2023/3/2349第49页/共83页递归函数的实现当多个函数嵌套调用时，由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行栈式管理。2023/3/2350第50页/共83页递归函数的实现在执行递归函数的过程中需要一个递归工作栈。它的作用是:将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数；保存本层的参数和局部变量，以便从下一层返回时重新使用它们。2023/3/2351第5
15、1页/共83页递归函数的实现递归过程执行过程中占用的数据区，称之为递归工作栈。每一层的递归参数等数据合成一个记录，称之为递归工作记录。栈顶记录指示当前层的执行情况，称之为当前活动记录。递归工作栈的栈顶指针，称之为当前环境指针。2023/3/2352第52页/共83页递归函数的实现例：梵塔函数动画演示2023/3/2353第53页/共83页importjava.util.Stack;publicclassHanoipublicstaticvoidmain(Stringargs)Hanoihnt=newHanoi(6);publicHanoi(intcount)this.count=count;h
16、anoi(count,A,B,C,0);2023/3/2354第54页/共83页privatevoidhanoi(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,start,destination,level);2023/3/2355第55页/共83页privateclass
17、Elementpublicintn,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;56第56页/共83页privatevoidhanoi_stack(intn,charstart,chartransit,chardestination,intl
18、evel)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);stack.push(newElement(n-1,e.start,e.desti
19、nation,e.transit,level);e=null;2023/3/2357第57页/共83页privatevoidmove(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.toString();sb.delete(0,sb.leng
20、th();2023/3/2358第58页/共83页privatevoidmove(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();privateintcount;/初始规模2023/3/2359第59
21、页/共83页队列2023/3/2360第60页/共83页队列的定义队列（queue）简称队，是一种特殊的线性表。仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾（rear），删除数据元素的一端称为队首（front）。向队尾插入元素称为进队或入队，新元素入队后成为新的队尾元素；从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队首元素。队列的特性：（FirstInFirstOut,简称FIFO）2023/3/2361第61页/共83页队列的抽象数据类型定义2023/3/2362第62页/共83页队列的抽象数据类型定义2023/3/2363第63页
22、/共83页Queue接口2023/3/2364第64页/共83页异常类定义2023/3/2365第65页/共83页队列的顺序存储实现2023/3/2366第66页/共83页循环数组设想数组A0.capacity-1中的单元不是排成一行，而是围成一个圆环，即A0接在Acapacity-1的后面。这种意义下的数组称为循环数组。2023/3/2367第67页/共83页循环队列循环队列是队列的一种顺序存储表示。为什么要称作循环队列而不说是顺序队列呢？动画演示2023/3/2368第68页/共83页循环队列的操作入队操作将新元素入队时，可在队尾指针指示的单元中存入新元素，并将队尾指针rear按逆时针方向
23、移一位。出队操作将队首指针front依逆时针方向移一位。2023/3/2369第69页/共83页循环队列的操作2023/3/2370第70页/共83页思考判别循环队列为空的条件应该是什么？在队列初始化的函数中，设置队头和队尾指针均为0，那么能否由队头指针为0来作为队列空的判别条件呢？由于顺序存储结构是一次性地分配空间，因此在入队列的操作中首先应该判别当前队列是否已经满了，那么队列满的判别条件又是什么呢？2023/3/2371第71页/共83页循环队列中各关键量2023/3/2372第72页/共83页Queue的顺序存储实现2023/3/2373第73页/共83页Queue的顺序存储实现2023
24、/3/2374第74页/共83页Queue的顺序存储实现2023/3/2375第75页/共83页Queue的顺序存储实现2023/3/2376第76页/共83页队列的链式存储实现采用带头结点的单链表结构实现队列的链式存储。选择链表的头部作为队首，链表的尾部作为队尾。2023/3/2377第77页/共83页Queue的链式存储实现2023/3/2378第78页/共83页2023/3/2379第79页/共83页80第80页/共83页排队问题的系统模拟编制一个事件驱动仿真程序以模拟理发馆内一天的活动，要求输出在一天的营业时间内，到达的顾客人数、顾客在馆内的平均逗留时间和排队等候理发的平均人数以及在营业时间内空椅子的平均数。动画演示2023/3/2381第81页/共83页2023/3/2382第82页/共83页2023/3/2383感谢您的欣赏！第83页/共83页