05 - 队列：排队叫号

栈是「后进先出」，队列正好相反，是「先进先出」。它对应的是我们生活里最熟悉的场景——排队。

队列是什么：一头进，另一头出

队列（Queue） 是一种从一头进、从另一头出的结构：

• 进：只能从队尾加入（叫入队 / enqueue）。
• 出：只能从队头离开（叫出队 / dequeue）。

核心规则是 先进先出（FIFO，First In First Out）：先来的先被处理。

就是食堂排队打饭：

   出队 ◀─┌────┬────┬────┬────┐◀─ 入队
  (队头)  │ 张三│ 李四│ 王五│ 赵六│  (队尾)
          └────┴────┴────┴────┘
       先来的张三先打到饭走人，新来的赵六排最后

先排队的先打到饭，新来的乖乖排到最后。绝对公平，谁也别想插队。

• 入队、出队都是 O(1)：只在两头操作，很快。

队列擅长解决什么：需要「按顺序、公平处理」的场景

只要一个问题有「先来的先服务、按顺序处理、不能乱」的特征，队列就特别合适。

场景 1：任务排队处理

服务器同时收到一堆请求，处理不过来，就把它们排进一个队列，按到达顺序一个个处理。你在操作系统篇学的「消息队列」「打印任务队列」都是这个思想——先提交的先打印。

场景 2：广度优先搜索（BFS）

后面第 12 章讲图的时候会用到：一层层向外探索时，用队列记录「接下来要访问谁」，保证先发现的先处理，从而实现「由近及远」一圈圈扩散。（这是队列在算法里最重要的用途，先记个印象。）

场景 3：缓冲区

两个速度不一样的部件之间（比如 CPU 很快、打印机很慢），用队列当「缓冲」：快的一方把任务先扔进队列，慢的一方按顺序慢慢取。这样快的不用干等慢的。

几个有用的变种

队列这个基本思想，衍生出几个常见变种，理解概念即可：

循环队列

如果用一个固定长度的数组实现队列，出队后前面会空出位置浪费掉。循环队列让队尾「绕回」数组开头，把空出来的位置重新利用起来，像首尾相接的环。常用于固定大小的缓冲区。

双端队列（Deque）

两头都能进、都能出。更灵活，既能当队列用，也能当栈用。

优先级队列

这个最特别：它不完全按到达顺序，而是按「优先级」出队——谁优先级最高谁先出，不管来得早晚。

就像医院急诊：不是谁先挂号谁先看，而是病情最重的先看。这就打破了纯粹的「先进先出」。

优先级队列非常常用（比如任务调度里「紧急任务插队」），而它底层通常用一种叫「堆」的结构来高效实现——这正是第 10 章的主角，到时候会呼应回来。

栈 vs 队列：一对好记的对照

小结

• 队列从队尾进、队头出，规则是先进先出（FIFO），像食堂排队，公平不插队。
• 核心操作：入队 enqueue、出队 dequeue，都是 O(1)。
• 擅长「按顺序、公平处理」的场景：任务排队、BFS 图遍历、快慢部件间的缓冲区。
• 重要变种：循环队列（省空间）、双端队列（两头进出）、优先级队列（按优先级出队，常用堆实现）。
• 和栈对照记：栈=后进先出=一摞盘子；队列=先进先出=排队。

下一章 → 06 - 哈希表：为什么查东西能「秒查」 ｜ 回到 README 目录