🎢

队列与循环队列

买冰凌排队：先来的人先买到——"先进先出"。

💡 打个比方

想象排队买冰凌：新来的只能站到队尾（入队 enqueue），卖冰凌的只服务队头那个人（出队 dequeue），服务完他就离开——先来先走，这叫先进先出（FIFO，First In First Out）。上一课的栈是"一摞便当盒"（后放先走、只有一个口）；队列是"一条队"（先放先走、两个口：队尾进、队头出）。

术语：队头 front（最先来、即将被服务的那个）；队尾 rear（最后来、刚加入的那个）；入队 enqueue（队尾加入）；出队 dequeue（队头离开）；队空 empty（队里没人）。

🖼️ 大图看明白

🧩 子任务 1：FIFO——预测"谁先被服务"

🎯 小目标：区分栈（LIFO）和队列（FIFO），能预测一串入队/出队操作的结果。

规则：dequeue 永远弹出队头（最先入队、还没出队的那个人）。跟着操作推演：

// 初始：队空
enqueue A
enqueue B
enqueue C
dequeue  // → ?
dequeue  // → ?
dequeue  // → ?

✅ 小检查：三次 dequeue 依次输出什么？和"同样操作打在栈上"的输出（3、2、1）对比，顺序差在哪？

看看答案

依次输出 A、B、C——和入队顺序一模一样（先进先出）。同样的操作打在栈上，输出是 C、B、A（后进先出）。一句话对比：队列像排队，顺序原样输出；栈像便当盒，顺序倒过来输出。

🧩 子任务 2：普通数组队列的"假死"问题

🎯 小目标：看懂为什么只用一个数组、front 只往前挪的队列会"假死"。

普通数组队列的做法：入队 rear 往后挪，出队 front 往后挪，谁也不回头。跟着下面这组操作走一遍（容量 5，数组 a[0..4]）：

// 容量 5：a[0] a[1] a[2] a[3] a[4]
enqueue 小明   // front=0 rear=0
enqueue 小红   // rear=1
enqueue 小强   // rear=2
enqueue 小磊   // rear=3
enqueue 小兰   // rear=4，队满（5 人）
dequeue 小明   // front=1
dequeue 小红   // front=2
enqueue 小刚   // ？

走到最后一步：队里其实只剩 3 个人（小强、小磊、小兰），a[0]、a[1] 都空着；但 rear 已经顶到 a[4]，右边没有格子了——按"rear+1 越界 = 队满"的判断，小刚进不来！这就是假死：看着满了，其实还有空位，只是空位在"前面"，用不上。

两条出路：

办法①：搬——把剩下的元素整体左移到 a[0] 开头。能用，但一次要搬 n 个，O(n)，人多了就慢。
办法②：绕圈——让 rear 走到末尾后绕回 a[0] 继续用，这就是循环队列（下一节）。

✅ 小检查：最后一步时队里有几个人？几个空格子？不搬家的话小刚能入队吗？"搬"的代价是多大？

看看答案

队里 3 个人，2 个空格子（a[0]、a[1]）。不搬家小刚进不来（rear+1 = 5 越界，误判队满）。"搬"要把 3 个元素逐个左移 2 格，代价 O(n)——每次都要搬，太浪费。

🧩 子任务 3：循环队列——% 绕回队头

🎯 小目标：掌握循环队列的三条规则（取模绕圈、入队、出队）和满/空判断。

核心思想：下标 +1 之后如果到达容量 n，就用 (i+1) % n 绕回 0——像过山车🎢的环形轨道，跑完最后一格回到第一格。规则（容量 n，front = 队头下标，rear = 队尾下标，front = -1 表示队空）：

入队：若 (rear+1) % n == front → 队满（下一格就是队头，再放会撞上）；否则 rear = (rear+1) % n，a[rear] = x；若 front == -1 则 front = rear。
出队：x = a[front]；若 front == rear（只剩这一个）→ front = rear = -1（变空）；否则 front = (front+1) % n。
队空：front == -1；队满：(rear+1) % n == front。

完整走一遍（容量 6）：入队 1、2、3，出队、出队，再入队 4、5、6、7、8：

// n = 6，front = rear = -1（空）
enqueue 1  // (rear+1)%6=0 != -1 → rear=0, a[0]=1, front=0
enqueue 2  // rear=1, a[1]=2
enqueue 3  // rear=2, a[2]=3
dequeue    // 弹出 a[0]=1，front=1
dequeue    // 弹出 a[1]=2，front=2（队里只剩 3）
enqueue 4  // (2+1)%6=3 != 2 → rear=3, a[3]=4
enqueue 5  // rear=4, a[4]=5
enqueue 6  // rear=5, a[5]=6
enqueue 7  // (5+1)%6=0 != 2 → rear=0，a[0]=7 ← 绕回队头！
enqueue 8  // (0+1)%6=1 != 2 → rear=1，a[1]=8

注意最后两步：rear 走到 a[5] 后，% 6 把它弹回了 a[0]，把当初"出队腾出来的"格子又用上了——不再需要搬家！

✅ 小检查：① 入队 7 之后 rear 等于几？② 入队 8 之后，队里从队头到队尾依次是谁？③ 此时还能入队 9 吗？为什么？

看看答案

① rear = 0（(5+1)%6 = 0，绕回第一格）。 ② 从队头到队尾：3、4、5、6、7、8（front=2 → a[2]=3, a[3]=4, a[4]=5, a[5]=6, a[0]=7, a[1]=8——在数组里"跨过末尾绕一圈"）。 ③ 不能：此时 (rear+1)%6 = (1+1)%6 = 2，正好 == front(2)，触发"队满"判断——6 格全占满，9 只能等有人出队。

易错：判断顺序！先判断满再入队，先判空再出队，否则 rear+1 或 a[front] 会访问到没用的格子。

🧩 子任务 4：应用——打印机任务缓冲

🎯 小目标：用循环队列模拟"多人共享打印机"：任务随时来、打印一次一份，谁先来谁先打。

场景：4 个同学的打印任务先后到达，打印机一次处理一份。处理完前 2 份后，又有 2 个新任务加入。处理顺序应该完全按到达顺序（先进先出），这正是队列的本行。用容量 6 的循环队列模拟：

入队：小明、小红、小强、小美
出队（打印）1 份
出队（打印）1 份
入队：小磊、小兰
把剩下的全部出队打印

✅ 小检查：6 份打印任务的输出顺序是什么？中间 rear / front 有没有"绕圈"？

看看答案

输出顺序：小明 → 小红 → 小强 → 小美 → 小磊 → 小兰（严格按到达顺序）。绕圈情况：入队 4 人后 front=0, rear=3；出队 2 份后 front=2；再入队小磊（rear=4）、小兰（rear=5）——本例 rear 没绕圈。若一开始就排了 6 人再出队 2 人，rear 继续入队时就会 (rear+1)%6 绕回 0。

为什么这里必须是队列而不是栈？如果用栈，最后提交的小兰会第一个被打印——共享设备"先来后到"的公平性就没了。

💻 完整代码：循环队列 + 打印机模拟

// 循环队列（容量 6）+ 打印机任务模拟
// 输出：小明 小红 小强 小美 小磊 小兰（按到达顺序打印）
#include <iostream>
#include <string>
using namespace std;

const int N = 6;
string a[N];
int front = -1, rear = -1;      // front = -1 表示队空

bool empty() { return front == -1; }
bool full()  { return (rear + 1) % N == front; }

void push(string x) {
    rear = (rear + 1) % N;      // % N 实现绕圈
    a[rear] = x;
    if (front == -1) front = rear;
}

string pop() {
    string x = a[front];
    if (front == rear) front = rear = -1;   // 最后一个出队 → 变空
    else front = (front + 1) % N;
    return x;
}

int main() {
    push("小明"); push("小红"); push("小强"); push("小美");
    cout << "打印：" << pop() << endl;
    cout << "打印：" << pop() << endl;
    push("小磊"); push("小兰");
    while (!empty()) cout << "打印：" << pop() << endl;
    return 0;
}

✋ 你来试试

第 1 题：容量 6 的循环队列，此刻 front = 2、rear = 1。队满吗？队里有几个元素？

队满，6 个元素。判断：(rear+1) % 6 = (1+1) % 6 = 2 == front(2)，触发满的条件——下一格正好是队头，6 格全被占。

第 2 题：enqueue A、enqueue B、enqueue C、dequeue、enqueue D、dequeue——两次 dequeue 的输出依次是什么？结束时队里是谁？

第 1 次 dequeue → A（队头）；入队 D 后队是 [B, C, D]；第 2 次 dequeue → B。结束时队里剩 C、D（C 在队头）。全程严格按先进先出。

第 3 题（加餐）：打印机的任务缓冲为什么用队列不用栈？浏览器的"后退"按钮更适合哪种结构？

打印机要"先来先打"的公平 → 队列（用栈的话最后提交的任务会抢先打印）。浏览器"后退"是"最后打开的页面先回退"，后进先出 → 栈。同一对概念，看场景选结构。

🎯 一句话记住：队列 = 买冰凌排队，先进先出（队尾进、队头出）；普通数组队列会"假死"，循环队列用 % n 绕回队头；空 = front == -1，满 = (rear+1) % n == front。

← 上一课：栈下一课：面向对象：类与封装 →