小探险家学算法

Appearance

7. 排队叫号（队列） ​

知识点：队列（queue）—— 先进先出

项目：叫号机 + 队伍管理

故事开场：打印店的"滴——" ​

学校旁边的打印店生意可好了。同学们都要去复印作业，可是柜台只有一个阿姨。 老板发明了一个办法：进门先拿号，然后坐着等，柜台叫到你的号，你就去。

"滴——请 3 号到柜台。"

这个叫号机太方便了。老师说："我们用程序做一个吧！"

规则是这样的：

  • 拿号：新来的同学领一个新号码，站到队伍最后面
  • 叫号：老师喊的，永远是队伍最前面那位同学的号码

你马上想到了上一章的栈：放上去、拿下来……等等，不对！

栈是"后进先出"——最后来的最先走。可叫号机明明是先来的先办啊？ 要是用栈来叫号，后拿号的同学反而先被叫到，打印店门口非得打起来不可。

笨办法先行：shift 的烦恼 ​

那用数组试试？队伍就是数组，拿号 = push 到末尾。 叫号 = 把队首的人拿出去——数组有没有"从前面拿"的方法？

有！就是 shift：

ts
const queue: number[] = []

queue.push(1)     // 1 号拿号，排队
queue.push(2)     // 2 号拿号，排在 1 号后面
queue.push(3)     // 3 号拿号，排在最后

const first = queue.shift()   // 叫号：拿走队首
console.log(first)            // 1

能跑！可是……你注意到一个问题没有？

shift 把第 0 个元素拿走之后，后面的所有元素都要往前挪一位：

原来：  [1, 2, 3, 4, 5]
拿走 1：[2, 3, 4, 5]

2 挪到 0 号位，3 挪到 1 号位，4 挪到 2 号位……每一个都要挪。 队伍 5 个人还好，要是全校 3000 人来复印，每次叫号都要挪 3000 次， 一天叫号几百次，几百万次挪动——打印店都关门了，还在挪呢。

咦，等等，这听起来像不像第 1 章学过的什么？挪 n 个元素，要做 n 步—— 这是 O(n)。而"拿一个号、叫一个号"，本该是一步的事啊（O(1)）！

引出知识点：队列——"先进先出"的一排人 ​

计算机里，专门有一种结构管"排队"这件事，它叫队列（queue）。

队列的规则和栈正好相反：先进先出（FIFO，First In First Out）—— 先来的先办事，后来的排队等。

生活中的队列到处都是：

  • 排队买奶茶：先来的先拿到奶茶
  • 打印机：你先发的打印任务先打出来，后发的排队等
  • 食堂打饭：按顺序来，不能插队
  • 网络视频：你点开视频，数据按顺序一小块一小块来， 先来的数据块先播放（所以视频不会从中间开始放）

队列的动作也只有两个：

动作名字干什么
push入队排到队伍最后面
shift出队拿走队伍最前面的

发现了吗？push 和栈一样，但出队用的是 shift（从前面拿）， 而不是 pop（从后面拿）——这是队列和栈唯一的区别，也是最关键的区别。

栈：push + pop，从同一头进出（后进先出） 队列：push + shift，一头进一头出（先进先出）

动手实现：叫号机 ​

来，把叫号机写出来：

ts
const queue: number[] = []   // 队伍

// 拿号：新号码排到队伍最后
function takeTicket(): void {
  const number = queue.length === 0 ? 1 : queue[queue.length - 1] + 1
  queue.push(number)
  console.log(number + " 号同学拿号")
}

// 叫号：拿走队伍最前面的
function callNext(): void {
  const next = queue.shift()
  if (next === undefined) {
    console.log("没有人排队了")
    return
  }
  console.log("请 " + next + " 号同学到柜台")
}

// 看看现在队伍里都有谁
function showQueue(): void {
  let line = "队伍："
  for (let i = 0; i < queue.length; i++) {
    line = line + queue[i] + " 号  "
  }
  console.log(line)
}

takeTicket()
takeTicket()
takeTicket()
showQueue()
callNext()
showQueue()
callNext()
callNext()
showQueue()
callNext()

输出：

1 号同学拿号
2 号同学拿号
3 号同学拿号
队伍：1 号  2 号  3 号  
请 1 号同学到柜台
队伍：2 号  3 号  
请 2 号同学到柜台
请 3 号同学到柜台
队伍：
没有人排队了

看！先拿号的先被叫到——1 号、2 号、3 号，顺序整整齐齐。 而且你看 takeTicket 里的一行：queue[queue.length - 1] + 1， 新号码永远是最新那个号 + 1，不用去数现在有几个人。

（(a ? b : c) 是"如果 a 成立就取 b，否则取 c"的三元写法—— 这里用来处理"队伍是空的，就从头号开始"。）

跑起来：把"慢"找出来 ​

还记得笨办法里的担心吗？shift 要挪动后面的所有元素。 我们来亲眼看看，队伍大了之后它到底有多慢：

ts
// 先造一个 10 万人的大队伍
const bigQueue: number[] = []
for (let i = 1; i <= 100000; i++) {
  bigQueue.push(i)
}

console.time("叫号 1 万次")
for (let i = 0; i < 10000; i++) {
  bigQueue.shift()
}
console.timeEnd("叫号 1 万次")

在我这台电脑上，输出（你电脑上的数字可能不一样）：

叫号 1 万次: 224ms

10 万人里叫 1 万次号，每次平均要挪 5 万个元素，总共约 5 亿次移动， 结果花了 200 多毫秒——听起来好像也没多慢嘛。

（这是因为现代计算机挪内存很快，而且它有自己的优化。但记住： 挪动的次数是 O(n) 的——队伍大一倍，每次叫号的工作量就大一倍。 到了数据更大、操作更频繁的真程序里，这就会变成大问题。 以后学到"循环队列"和"链表"时，你会看到让 O(n) 变成 O(1) 的办法—— 第 9 章我们就会遇到链表！）

小挑战 ​

  1. 过山车队列：模拟游乐场过山车：5 个同学排队，一次可以上车 2 人， 上车的出队，直到队伍空了，打印每次谁上车了。
  2. 报数游戏（约瑟夫问题）：n 个同学围成一圈报数，报到 3 的同学出列， 然后从下一个人重新从 1 报起，直到只剩一个人。用队列模拟： 每次"报数"就是把队首的人移到队尾（他没报到 3，回去排队）， 报到 3 的人直接出队。试试 n = 7，最后剩几号？ （提示：push(shift()) 可以把队首的人送到队尾！）
  3. 队列 vs 栈：下面是生活中的场景，判断用栈还是队列： ① 洗碗池里洗完摞起来的碗 ② 食堂打饭的队伍 ③ 网页后退按钮 ④ 电梯里先到的人先出 ⑤ 消息列表（先发的消息先显示）。

课后练习 ​

第 1 题（动手题）：课间排队 ​

模拟课间操排队：5 个同学按 1~5 号排队，老师叫走 2 个， 又来 3 个同学排到队尾。每次变化后打印队伍，验证"先进先出"。

参考答案（点开查看）
ts
for (let i = 1; i <= 5; i++) takeTicket()   // 5 个同学拿号
callNext()   // 叫走 1 号
callNext()   // 叫走 2 号
takeTicket() // 新同学 4 号排队
takeTicket() // 新同学 5 号排队
takeTicket() // 新同学 6 号排队
showQueue()  // 应该显示 3 号、4 号、5 号、6 号

注意：新同学拿的号是接着最后一个号排的（3 号之后是 4、5、6）， 不会因为前面的人走了就重新编号——号码是"票"，队伍是"人"， 两回事！这就是拿号和叫号分开记录的原因。

第 2 题（思考题）：为什么 shift 慢？ ​

数组 shift 拿走第 0 个元素后，为什么后面的元素都要挪？ 画一画：[A, B, C, D] 拿走 A 之后，数组里发生了什么事？

参考答案（点开查看）

[A, B, C, D] 拿走 A 后，B 要挪到第 0 格、C 挪到第 1 格、D 挪到第 2 格， 变成 [B, C, D]。

因为数组在内存里是连续排列的一排格子：第 0 格空出来，后面必须 补上来，否则"第 2 个元素"就找不到位置了。补位要动 n 个元素， 所以 shift 是 O(n) 的。

（对比：pop 拿走最后一个，前面的格子纹丝不动，所以 pop 是 O(1)。 这也是为什么栈用 pop 很舒服、队列用 shift 却要心疼。）

第 3 题（思考题）：生活中的 FIFO / LIFO ​

再各举一个生活中的例子：一个"先进先出"的，一个"后进先出"的。 然后说说，为什么打印机（先发的先打）用的是队列而不是栈？

参考答案（点开查看）

示例：先进先出 = 排队进地铁站、医生叫号；后进先出 = 弹夹里的子弹、 一摞要批改的作业（最后交的先批？还是最下面的先批？由老师定）。

打印机必须用队列：如果先发的任务被后发的插队（后进先出）， 你辛辛苦苦排了半天，别人的文件却先打出来——那就乱套了。 打印机是"先来先服务"的机器，必须先进先出，所以用队列。

下一课预告：全班 50 人，老师说"小明，你的学号是几号？" 你用数组挨个找，50 人还好。可要是全校 5000 人，老师报出名字， 程序要"滴"一下马上答出来——挨个找就太慢了。有什么办法 一步就找到呢？