外观
3.9 队列
银行取号
去银行办业务,先要取号。来一个人,取号机就吐出一张号码纸,号码一个比一个大。柜员那边有一个叫号器,按一下,就叫等着的人里最前面的那一个。
等着的号码排成一列。新取的号排在最后,叫号从最前面叫。
这样一列等着的号码,可以看成一个队列:从一头进,从另一头出。
学完这一节,你能判断什么样的东西可以看成队列,并用队列的五个操作,一步一步跟出它的样子。
今天开门时,还没有人在等。1号、2号先后取号。柜员叫了一次号。接着3号取号。柜员又叫了两次号。
柜员每叫一次号,都要知道叫到的是几号。叫号之前,还要知道有没有人在等。
本节问题三次叫号,叫到的依次是几号?叫完之后,还有人在等吗?
什么是队列
上一页说,这一列等着的号码可以看成一个队列。
队列是只能在一端插入、在另一端删除的线性表。
允许插入的一端叫队尾,允许删除的一端叫队头。取号排进来的那一头是队尾,叫号的那一头是队头。现在1号在队头,3号在队尾。
插入叫入队,删除叫出队。取号是入队,叫号是出队。一个元素都没有的时候,叫空队列。开门时没有人等,就是空队列。
这个定义有三个要点,逐条看。
线性表。等着的号码一个挨一个,排成一列:(1, 2, 3)。除了最前面和最后面的两个,每个号码前面恰好有一个,后面恰好有一个,一个接一个。所以它可以看成一个线性表。线性表在2.1节讲过。
只在队尾插入。新取的号只能排在最后。如果有人插到别人前面,这一列就不能再看成队列。
text
4号取号,排在最后: 1 2 3 4 是队列
4号插到1号前面: 4 1 2 3 不是队列只在队头删除。叫号只叫最前面的那个。栈也只动一端,可它进和出在同一端。队列进和出分在两端。
text
栈: 在同一端进出,先出来的是 3
队列:一端进,另一端出,先出来的是 1先进先出。每次只能删除队头,而队头总是还在队里的元素中最早入队的那一个。所以最先入队的,最先出队。这叫先进先出。栈是后进先出,队列正好相反。
银行里,先取号的先办,就是先进先出。
队列的五个操作
3.2节给栈定了五个操作。队列也是只能动两头的线性表,把栈的五个操作逐个改成队列的,就得到队列的五个操作。下面把队列记作Q。
InitQueue(Q):建立一个空队列。对应栈的InitStack,没有变。银行开门时,没有人在等。
QueueEmpty(Q):队列空返回1,不空返回0。对应栈的StackEmpty,也没有变。柜员叫号之前,先看有没有人在等,问的就是这个。
GetHead(Q, &x):取队头元素,用x带回。对应栈的GetTop。栈取栈顶,队列取队头。取完之后队列不变,就像叫号屏上提前显示"下一位:1号",1号还在等:
EnQueue(Q, x):把x放到队尾。对应栈的Push。Push放到栈顶,EnQueue放到队尾。4号取号,就是EnQueue(Q, 4):
DeQueue(Q, &x):删除队头元素,用x带回。对应栈的Pop。这一个变化最大:Pop删的是最后放进去的那一端,DeQueue删的是另一端。叫号叫到1号,就是DeQueue(Q, &x),x是1:
GetHead和DeQueue为什么用x带回,理由和3.2节一样:空队列时它们做不成,返回值要留着报告做成没做成。
五个操作和栈的对应如下:
| 栈 | 队列 | 含义 |
|---|---|---|
| InitStack(S) | InitQueue(Q) | 建立一个空队列 |
| StackEmpty(S) | QueueEmpty(Q) | 队列空返回1,不空返回0 |
| GetTop(S, &x) | GetHead(Q, &x) | 取队头元素,用x带回,队列不变 |
| Push(S, x) | EnQueue(Q, x) | 把x放到队尾 |
| Pop(S, &x) | DeQueue(Q, &x) | 删除队头元素,用x带回 |
队列的操作也都没有i:放总是放到队尾,取和删总是在队头。空队列没有队头,所以不能GetHead,也不能DeQueue。队列满了怎么办,是实现时的事。
队列的定义说的是它"是什么",这五个操作说的是它"能做什么"。两样合起来,就是队列的抽象数据类型。
例题:用五个操作回答柜员的问题
题目把等着的号码看成队列Q。开门时没有人在等。1号、2号先后取号,柜员叫一次号;3号取号,柜员又叫两次号。依次调用哪些操作?三次叫号,x依次是几?叫完之后,还有人在等吗?
分析。按发生的事,一件一件写。
- 开门:调用InitQueue(Q),Q是空队列。
- 1号、2号取号:调用EnQueue(Q, 1)、EnQueue(Q, 2)。队头是1,队尾是2。
- 第一次叫号:调用DeQueue(Q, &x),删掉队头,x是1。队里只剩2。
- 3号取号:调用EnQueue(Q, 3),3排在2后面。
- 第二次叫号:调用DeQueue(Q, &x),x是2。这时3刚刚入队,可它排在队尾,轮不到它。要是栈,出来的就是3了。
- 第三次叫号:调用DeQueue(Q, &x),x是3。
- 看还有没有人:调用QueueEmpty(Q),返回1,队列空了。
答案依次调用InitQueue(Q)、EnQueue(Q, 1)、EnQueue(Q, 2)、DeQueue(Q, &x)、EnQueue(Q, 3)、DeQueue(Q, &x)、DeQueue(Q, &x)、QueueEmpty(Q)。三次叫号,x依次是1、2、3。叫完之后,QueueEmpty返回1,没有人在等了。
验算一下:取号的顺序是1、2、3,叫号的顺序也是1、2、3,一个不差,这就是先进先出。
柜员的每一个动作都是五个操作之一,没有一步需要知道号码存在哪里。
练习1:哪些可以看成队列?
多选
下面哪些东西可以看成一个队列?
A
打印机的打印任务:新发来的任务排在最后,打印机按发来的顺序一个个打印
新任务只排在最后,打印只取最前面的,一端进,另一端出。
B
键盘缓冲区:按下的键先记下来,程序按按下的顺序一个个处理
新按的键记在最后,处理从最早的开始,先进先出。
C
浏览器的后退:每打开一个网页就记下来,按后退时回到最近记下的那一页
记和取在同一端,后进先出,是栈。
D
可以插队的排队:熟人可以插到朋友前面
能插到中间,不是只在队尾插入。
E
可以中途离开的排队:等不及的人可以从中间走掉
能从中间删除,不是只在队头删除。
判断的办法:是不是只从一头进,只从另一头出。
练习2:x依次是几?
填空
从空队列开始,依次调用:
EnQueue(Q, 5),EnQueue(Q, 8),DeQueue(Q, &x),EnQueue(Q, 6),GetHead(Q, &x),DeQueue(Q, &x)
- 第一次DeQueue之后,x是
- GetHead之后,x是
- 第二次DeQueue之后,x是
- 全部做完,队列里只剩
第一次DeQueue时队列里是5、8,队头是5。接着6入队,排在8后面,队头还是8。GetHead只看不拿,x是8,队列不变。所以第二次DeQueue删掉的还是8,只剩6。这和3.2节练习1是同一串调用,栈的答案是8、6、6、5,差别全出在删哪一头。
到这里你有了队列的定义:只能在一端插入、在另一端删除的线性表。队头、队尾、入队、出队、空队列这几个名词,由此推出的先进先出,以及队列的五个操作InitQueue、QueueEmpty、GetHead、EnQueue、DeQueue。下一步把队列放进内存。