《栈和队列的应用举例(全)》由会员分享，可在线阅读，更多相关《栈和队列的应用举例(全)（22页珍藏版）》请在金锄头文库上搜索。
1、栈和队列的应用举例栈的应用举例 u栈的基本用途 n保存暂时不用的数据或存储地址 n可简化程序设计栈的应用例1：数制转换（十转N） 用栈暂存低位值 例2：括号匹配的检验 用栈暂存左括号 例3：表达式求值用栈暂存运算符和操作数 例4：迷宫求解用栈实现递归调用 例5：行编辑程序 例6：二叉树的遍历数制转换 例. 给定十进制数 N=1348,转换为八进制数 R=2504 其运算过程如下：n n div 8 n mod 81348 168 4168 21 021 2 52 0 2低位高位数制转换 1.依次求余数,并送入栈中：(1) r1=1348%8=4 /求余n1=1348/8=168 /整除(2)
2、r2=168%8=0 /求余n2=168/8=21 /整除(3) r3=21%8=5 /求余n3=21/8=2 /整除(4) r4=2%8=2 /求余n4=2/8=0 /整除 2.依次退栈,得R=25044045042504(1) 4进栈(3) 5进栈(2) 0进栈 (4) 2进栈 判定表达式中的刮号匹配1.刮号匹配的表达式例. .(.( ).).( ).( ).2.刮号不匹配的表达式例. . .(.( ).).) 3.判定刮号不匹配的方法例. ( . . . (1) (2) (3) (4) (5)( (1)“(”进栈(3)“”进栈(5)“”退栈，“”与“”不匹配(2)“”进栈(4)“”退栈,
3、“”与“”匹配行编辑程序 例.data stru*cture 栈底 栈顶 输入文本(进栈)data stru 栈底 栈顶 e,r,u,t,c,*,*退栈(输错了，删除)data stru 栈底 栈顶 再输入文本cturedata structure 栈底 栈顶 表达式求值 例：4 + 2 * 3 10 / ( 7 5 )求值规则： 1.先乘除,后加减； 2.先括号内,后括号外； 3.同类运算,从左至右。 约定：1-左算符2-右算符1=#，为开始符2=#，为结束符算符优先关系表+ - * / （ ） #+ -*/ （）# s2的顶算符，则w进s2；2.3.2 若w=s2的顶算符，且w=“)”，则
4、pop(s2)；2.3.3 若ws2的顶算符，则： pop(s1,a)；pop(s1,b)；pop(s2,op)；c=b op a； push(s1,c)；转2.3.1； 直到现在w=“#”=s2的顶算符。s1 s2例. # 4 + 2 * 3 12 / ( 7 5 ) # 4 #24+#324*+# 4+#64+# #10#1 2 10/-#s1 s2 s1 s2 s1 s2 s1 s2s1 s2 s1 s2 s1 s2 s1 s2a=3；b=2；op=*；c=2*3=6 ；a=6；b=4；op=+；c=4+6=10；例. # 4 + 2 * 3 12 / ( 7 5 ) # 1210（/-
5、#571210- （/-#1210（/-#a=5；b=7；0p=“-”；c=7-5=2；21210（/-#21210/-#10-#a=2；b=12；0p=“/”；c=12/2=6； a=6；b=10；c=10-6=4；610-#s1 s2 s1 s2 s1 s2 s1 s2s1 s2 s1 s2 s1 s2 s1 s2例. # 4 + 2 * 3 12 / ( 7 5 ) # 4#s1 s2栈s1最后的顶(底)元素为表达式的值 迷宫求解从入口出发，按某一方向向未走过的前方探索 若能走通，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点 ，换下一个方向再继续试探直到所
6、有可能的通路都探索到，或找到一条通路， 或无路可走又返回到入口点。求解思想：回溯法迷宫求解队列的应用举例 队列的基本用途 保存暂时不用的数据 或存储地址 可简化程序设计 例.用队列进行迷宫求解用队列进行迷宫求解的基本思想是：n从迷宫的入口11出发，向四周搜索，记下所有一步能到 达的坐标点；n然后依次从每一点出发，向四周搜索，记下所有从入口点出 发，经过两步可以到达的坐标点n依次进行下去，一直到达迷宫的出口处44。n然后从出口处沿搜索路径回溯直到入口点，这样就找到了从 入口到出口的一条最短路径。 01100000101011100110000010101010474101-11115492548
7、354744262335332432122112序号 行 列 前驱由于先到达的点要先向下搜索，故引 进一个“先进先出”数据结构队列 来保存已到达的点的坐标。到达迷宫 的出口点(4,4)后，为了能够从出口点 沿搜索路径回溯直至入口，对于每一 点，在记下点的坐标的同时，还要记 下到达该点的前驱点。【例】汽车加油站 随着城市里汽车数量的急速增长，汽车加油 站也渐渐多了起来。通常汽车加油站的结构 基本上是：入口和出口为单行道，加油车道 可能有若干条。每辆车加油都要经过三段路 程，第一段是在入口处排队等候进入加油车 道；第二段是在加油车道排队等候加油；第 三段是进入出口处排队等候离开。实际上， 这三段都
8、是队列结构。若用算法模拟这个过 程，就需要设置加油车道数加2个队列。 队列的应用【例】模拟打印机缓冲区 在主机将数据输出到打印机时，会出现主机速度与 打印机的打印速度不匹配的问题。这时主机就要停 下来等待打印机。显然，这样会降低主机的使用效 率。为此人们设想了一种办法：为打印机设置一个 打印数据缓冲区，当主机需要打印数据时，先将数 据依次写入这个缓冲区，写满后主机转去做其他的 事情，而打印机就从缓冲区中按照先进先出的原则 依次读取数据并打印，这样做即保证了打印数据的 正确性，又提高了主机的使用效率。由此可见，打 印机缓冲区实际上就是一个队列结构。【例】CPU分时系统 在一个带有多个终端的计算机系统中，同时有多个 用户需要使用CPU运行各自的应用程序，它们分别通 过各自的终端向操作系统提出使用CPU的请求，操作 系统通常按照每个请求在时间上的先后顺序，将它 们排成一个队列，每次把CPU分配给当前队首的请求 用户，即将该用户的应用程序投入运行，当该程序 运行完毕或用完规定的时间片后，操作系统再将CPU 分配给新的队首请求用户，这样即可以满足每个用 户的请求，又可以使CPU正常工作。【例】打印杨辉三角形杨辉三角形元素入队顺序000000011FR 0110121FR011FR0110FR01101FR011012FR0110121FR
