栈及队列的应用举例(全).pptVIP

栈和队列的应用举例;栈的应用;数制转换 例. 给定十进制数 N=1348,转换为八进制数 R=2504 其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2;数制转换 1.依次求余数,并送入栈中： (1) r1=1348%8=4 //求余 n1=1348/8=168 //整除 (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=2504;判定表达式中的刮号匹配 1.刮号匹配的表达式 例. {...(...( )...)...} [...{...( )...( )...}...] 2.刮号不匹配的表达式 例. {...[ }...] [...(...( )...)...) 3.判定刮号不匹配的方法 例. ( ...{ ...{ ...}...] ↑ ↑ ↑ ↑ ↑ (1) (2) (3) (4) (5);行编辑程序 例.;表达式求值 例：4 + 2 * 3 – 10 / ( 7 – 5 );算法思想： 设立：s1----操作数栈,存放暂不运算的数和中间结果 s2----算符栈,存放暂不运算的算符 1.置s1,s2为空栈；开始符#进s2； 2.重复： { 2.1 从表达式读取“单词”w----操作数/算符 2.2 若w为操作数，则w进s1； 2.3 若w为算符，则： 2.3.1 若ws2的顶算符，则w进s2； 2.3.2 若w=s2的顶算符，且w=“)”，则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的顶算符。;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ; 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;;从入口出发，按某一方向向未走过的前方探索 若能走通，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探 直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。;队列的应用举例;用队列进行迷宫求解的基本思想是： 从迷宫的入口[1][1]出发，向四周有哪些信誉好的足球投注网站，记下所有一步能到达的坐标点； 然后依次从每一点出发，向四周有哪些信誉好的足球投注网站，记下所有从入口点出发，经过两步可以到达的坐标点…… 依次进行下去，一直到达迷宫的出口处[4][4]。 然后从出口处沿有哪些信誉好的足球投注网站路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。 ;0;【例】汽车加油站随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加2个队列。　;【例】模拟打印机缓冲区在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。;【例】CPU分时系统在一个带有多个终端的??算机系统中，同时有多个用户需要使用CPU运行各自的应用