栈和队列的应用举例(全)

【例】CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个 用户需要使用CPU运行各自的应用程序，它们分别通 过各自的终端向操作系统提出使用CPU的请求，操作 系统通常按照每个请求在时间上的先后顺序，将它 们排成一个队列，每次把CPU分配给当前队首的请求 用户，即将该用户的应用程序投入运行，当该程序 运行完毕或用完规定的时间片后，操作系统再将CPU 分配给新的队首请求用户，这样即可以满足每个用 户的请求，又可以使CPU正常工作。
1 0 0 0
1 0 1 1
0 0 0 0
1 2 3 4 5 6 7 8 9 10
1 2 2 3 2 4 3 2 1 4
1 1 2 2 3 2 4 4 4 4
-1 1 1 3 3 4 5 5 5 7
队列的应用
【例】汽车加油站
随着城市里汽车数量的急速增长，汽车加油 站也渐渐多了起来。通常汽车加油站的结构 基本上是：入口和出口为单行道，加油车道 可能有若干条。每辆车加油都要经过三段路 程，第一段是在入口处排队等候进入加油车 道；第二段是在加油车道排队等候加油；第 三段是进入出口处排队等候离开。实际上， 这三段都是队列结构。若用算法模拟这个过 程，就需要设置加油车道数加2个队列。
队列的应用举例
• 队列的基本用途 • 保存暂时不用的数据 或存储地址 • 可简化程序设计 例.用队列进行迷宫求解
用队列进行迷宫求解的基本思想是：
从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能 到达的坐标点；
然后依次从每一点出发，向四周搜索，记下所有从入口点 出发，经过两步可以到达的坐标点„„ 依次进行下去，一直到达迷宫的出口处[4][4]。 然后从出口处沿搜索路径回溯直到入口点，这样就找到了 从入口到出口的一条最短路径。
【例】打印杨辉三角形
1 1 1 1 1 1 6 5 15 4 10 20 3 6 10 15 2 3 4 5 6 1 1 1 1 1 1 i= 1 2 3 4 5 6
0 11 0 0 0 0 0
1 1 1 1 6 6 1 1 5 5 15 15 1 1 4 4 10 10 20 20 1 1 3 3 6 6 2 2
0
4
4
(1) 4进栈 (2) 0进栈 2 5 0 4 5
0
4
(3) 5进栈 (4) 2进栈
判定表达式中的刮号匹配 1.刮号匹配的表达式 例. {...(...( )...)...}
{ ( (1)“(”进栈 ( (2)“{”进栈
[...{...( )...( )...}...]
2.刮号不匹配的表达式 例. {...[ }...] [...(...( )...)...)
数制转换 例. 给定十进制数 N=1348,转换为八进制数 R=2504
其运算过程如下： n n div 8 1348 168 168 21 21 2 2 0 n mod 8 4 低位 0 5 高位 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
← 输入文本(进栈)
data stru
↑ 栈底 ↑ 栈顶
e,r,u,t,c,*,*退栈(输错了，删除)
data stru
↑ 栈底 ↑ 栈顶
← 再输入文本cture
data structure
↑ 栈底 ↑ 栈顶
表达式求值 例：4 + 2 * 3 – 10 / ( 7 – 5 ) ① ② ⑤ ④ ③
求值规则： 1 2 1.先乘除,后加减； 2.先括号内,后括号外； + 3.同类运算,从左至右。 * 约定： / 1----左算符 （ 2----右算符 ） 1=#，为开始符 # 2=#，为结束符
0 0
1 0
1 0
0 0
1
1
0
1
1
1
0
0
由于先到达的点要先向下搜索，故引 进一个“先进先出”数据结构——队 列来保存已到达的点的坐标。到达迷 宫的出口点(4,4)后，为了能够从出口 点沿搜索路径回溯直至入口，对于每 一点，在记下点的坐标的同时，还要 记下到达该点的前驱点。
序号 行 列 前驱
0 0 1 1
栈和队列的应用举例
栈的应用举例
栈的基本用途 保存暂时不用的数据或存储地址 可简化程序设计
栈的应用
例1：数制转换（十转N） 用栈暂存低位值 例2：括号匹配的检验 用栈暂存左括号 例3：表达式求值 用栈暂存运算符和操作数 例4：迷宫求解 用栈实现递归调用 例5：行编辑程序 例6：二叉树的遍历
【例】模拟打印机缓冲区
在主机将数据输出到打印机时，会出现主机速度与 打印机的打印速度不匹配的问题。这时主机就要停 下来等待打印机。显然，这样会降低主机的使用效 率。为此人们设想了一种办法：为打印机设置一个 打印数据缓冲区，当主机需要打印数据时，先将数 据依次写入这个缓冲区，写满后主机转去做其他的 事情，而打印机就从缓冲区中按照先进先出的原则 依次读取数据并打印，这样做即保证了打印数据的 正确性，又提高了主机的使用效率。由此可见，打 印机缓冲区实际上就是一个队列结构。
算符优先关系表
+ > > > > < > < > > > > < > < * < < > > < > < / < < > > < > < （ < < < < < ） > > > > = > # > > > > > =
<
算法思想： 设立：s1----操作数栈,存放暂不运算的数和中间结果 s2----算符栈,存放暂不运算的算符 s1 1.置s1,s2为空栈；开始符#进s2； 2.重复： { 2.1 从表达式读取“单词”w----操作数/算符 2.2 若w为操作数，则w进s1； 2.3 若w为算符，则： 2.3.1 若w>s2的顶算符，则w进s2； 2.3.2 若w=s2的顶算符，且w=“)”，则pop(s2)； 2.3.3 若w<s2的顶算符，则： { 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 ) # s1 s2
→
4Leabharlann Baidu
#
栈s1最后的顶(底)元素为表达式的值
迷 宫 求 解
迷宫求解
求解思想：回溯法
从入口出发，按某一方向向未走过的前方探索
若能走通，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点， 换下一个方向再继续试探 直到所有可能的通路都探索到，或找到一条通路， 或无路可走又返回到入口点。
（ / 12 10
s1
5
s2
（
s1
s2
（ /
s1
s2
（
7
12 10
/
# 12 10
2
12 10
/
#
#
#
a=5；b=7；0p=“-”；c=7-5=2；
s1
2 12 10
s2
/ #
s1
s2
s1
s2
s1
s2
10 #
6 10
# #
a=2；b=12；0p=“/”；c=12/2=6； a=6；b=10；c=10-6=4；
1 1 1 1 3 3 4 4 10 10 15 15 5 5 6 6 1 1 1 1 1 1 1 1
杨辉三角形元素入队顺序
0
F
1
1
R
0
1
1
0
F
1
2
1
R
0
F
1
1
R
0
F
1
1
0
R
0
1
F
1
0
1
R
0
1
1
F
0
1
2
R
0
1
1
0
F
1
2
1
R
s2
例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) #
s1
s2
s1
2
s2
+
s1
3
s2
* +
s1
s2
+
2
4
4
#
4
#
#
4
#
a=3；b=2；op=*；c=2*3=6；
s1
6
s2
+ #
s1
s2
s1
s2
s1
12
s2
/
#
4
#
10
#
10
a=6；b=4；op=+；c=4+6=10；
例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # s1 s2
{ { ( { (
(3)“{”进栈 (4)“{”退栈, “}”与“{”匹配
3.判定刮号不匹配的方法 例. ( ...{ ...{ ...}...] ↑ ↑ ↑ ↑ ↑ (1) (2) (3) (4) (5)
(
(5)“{”退栈，“]”与“{”不匹配
行编辑程序 例. data stru**cture
↑ 栈底 ↑ 栈顶