Lesson 35: 循环队列基础

练习任务

难度：易-中

实现环形队列的两个核心操作：

enqueue(val) — 入队：将 val 放入 queue[rear]，然后 rear = (rear + 1) % MAX（取模实现环绕）。
dequeue() — 出队：从 queue[front] 取出值，然后 front = (front + 1) % MAX（取模实现环绕），返回取出的值。

全局变量 queue[MAX]（数组）、front（队头）和 rear（队尾）以及 is_empty() 函数已由模板提供。main 读入一行数字，依次入队后再全部出队打印。

本课共有 3 组测试用例：

输入 "10 20 30"  → 输出 "10 20 30"
输入 "1 2"       → 输出 "1 2"
输入 "5"         → 输出 "5"

提示：环形队列的核心公式是 (ptr + 1) % MAX——让指针走到数组末尾时"绕回"开头，重用已被出队的空间。入队顺序是"先赋值再移动 rear"，出队顺序是"先取值，再移动 front"。将顺序颠倒会发生什么？用 MAX=4 的队列在纸上追踪一轮就明白了。

核心知识点

FIFO 语义 — 队列是先进先出（First In First Out），与栈的 LIFO 相对，适用于公平调度场景
线性队列的"假溢出" — 不取模导致 front 前的空间被浪费，rear 到数组末后无法入队
取模回绕 (ptr+1)%MAX — 环形结构的核心公式，实现指针在数组两端循环
"先放值后推进"顺序 — 入队 queue[rear]=val; rear=(rear+1)%MAX，先放后移才能正确使用 0 号槽
队空/队满判定 — 空 front==rear，满 (rear+1)%MAX==front（牺牲一个位置换取简洁区分）
count 变量替代方案 — 用 count 变量代替牺牲位置，满 count==MAX，空 count==0
2 的幂位与优化 — 当 MAX 为 2 的幂时，(ptr+1)&(MAX-1) 替代 %MAX，性能更佳
Linux kfifo — 工业级无锁环形缓冲，单生产者单消费者只需内存屏障，无需互斥锁
栈 vs 队列的分工 — 栈适合回溯/撤销/括号匹配，队列适合公平调度/BFS/缓冲削峰

代码框架

35_queue_base.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 64

int queue[MAX];
int front = 0, rear = 0; /* front == rear 表示队空 */

int is_empty(void) { return front == rear; }

/* 入队：把 val 存到 rear 位置，然后 rear 取模后移 */
void enqueue(int val)
{
    // 把 val 放进 queue[rear]

    // rear = (rear + 1) % MAX   — 取模实现环绕
    // 在这里实现 enqueue
}

/* 出队：从 front 位置取出值，然后 front 取模后移 */
int dequeue(void)
{
    // 从 queue[front] 取出值保存到 val

    // front = (front + 1) % MAX   — 取模实现环绕

    // 返回保存的值
    // 在这里实现 dequeue
}

int main(void)
{
    char line[256];
    fgets(line, sizeof(line), stdin);

    /* 解析数字入队 */
    char *tok = strtok(line, " \n");
    while (tok) {
        enqueue(atoi(tok));
        tok = strtok(NULL, " \n");
    }

    /* 全部出队并打印，空格分隔，最后换行 */
    // 在这里完成 main：循环 dequeue 直到队空
    // 注意控制空格格式

    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：入队是 rear++ 还是 (rear+1)%MAX？为什么？出队时 front 的初值从哪来？空格格式怎么控制？

TIP

先不要往下翻看参考解答。用 MAX=4 在纸上追踪入队 3 个元素、出队 2 个、再入队 2 个的完整过程。重点关注 rear 从 3 绕回 0 的那一步——这是环形队列的精髓。

深度讲解

1. 队列的基本概念——FIFO 的语义

1.1 什么是队列——排队的直觉

队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构。像排队买票——先到的人先服务，后来的人排在队尾。

入队顺序: A → B → C
出队顺序: A → B → C  (先进先出！)

队列的两个基本操作：

操作	英文名	含义	口诀
入队 / 加入	enqueue	将元素添加到队尾	尾进
出队 / 取出	dequeue	从队头取出元素	头出

1.2 环形队列的两个指针：front 与 rear

队列数据的排列:

  front (队头)                rear (队尾)
     ↓                          ↓
  ┌───┬───┬───┬───┬───┐
  │ A │ B │ C │ _ │ _ │ ...  ← queue[MAX]
  └───┴───┴───┴───┴───┘
     ↑          ↑
    取值位置    放值位置

  front: 指向下一个要出队的元素（队头）
  rear:  指向下一个要存放的空位（队尾）

  front == rear → 队空（没有元素）

指针的移动方向:

  front → ┐        ┌── rear
     ↓    │        │    ↓
  ┌───┬───┬───┬───┬───┐
  │ _ │ B │ C │ D │ _ │
  └───┴───┴───┴───┴───┘
         └─────────┘
          队列中的数据

  dequeue(): 取 front 位置的值(A已出队)，front 右移
  enqueue(): 把值放入 rear 位置，rear 右移

1.3 栈 vs 队列——一对"互补兄弟"

维度	栈 (Stack)	队列 (Queue)
原则	LIFO (后进先出)	FIFO (先进先出)
插入/删除	同一端（栈顶）	两端（尾进头出）
类比	一摞盘子	排队买票
指针	一个 top	两个 front + rear
经典应用	括号匹配、撤销操作、DFS	公平调度、BFS、消息缓冲
初始空态	`top == -1`	`front == rear == 0`

2. 为什么需要"环形"——线性队列的"假溢出"

2.1 问题：front 前面的空间被浪费了

如果不取模，仅让 front 和 rear 单调递增（线性队列），会出现一个尴尬的问题：

MAX = 5 的线性队列:

初始:    [_,_,_,_,_]  front=0, rear=0

入队 A:  [A,_,_,_,_]  front=0, rear=1
入队 B:  [A,B,_,_,_]  front=0, rear=2
入队 C:  [A,B,C,_,_]  front=0, rear=3
出队:    [_,B,C,_,_]  front=1, rear=3   ← A 出队
出队:    [_,_,C,_,_]  front=2, rear=3   ← B 出队
入队 D:  [_,_,C,D,_]  front=2, rear=4
入队 E:  [_,_,C,D,E]  front=2, rear=5

rear == MAX → "满了"！

但实际上 [0] 和 [1] 是空的！front 前面的空间完全被浪费。
这就是"假溢出"—数据没有满，但 rear 已走到数组尽头。

假溢出的视觉解读:

  front=2              rear=5(溢出!)
    ↓                    ↓
  ┌───┬───┬───┬───┬───┐
  │ _ │ _ │ C │ D │ E │   ← 前面两个槽空着，但 rear 无处可去
  └───┴───┴───┴───┴───┘
    ↑   ↑
   空着 空着      这些空间被永久浪费了！

2.2 解决方案：取模回绕

当指针走到数组末尾时，通过取模运算 % MAX 让它绕回数组开头，重用已被出队的空间。

把数组想象成一个环:

        ┌───┐
    ┌─→ │ 0 │ ──┐
    │   └───┘   │
    │   ┌───┐   │
    │   │ 1 │   │
    │   └───┘   │    在这个环上，front 和 rear 顺时针移动
    │   ┌───┐   │    (ptr + 1) % MAX 就是"向前一步"
    │   │ 2 │   │
    │   └───┘   │
    │   ┌───┐   │
    │   │...│   │
    │   └───┘   │
    │   ┌───   │
    └── │63 │ ←─┘
        └──┘

当 rear=63 时, (63+1) % 64 = 0 → 绕回位置 0！

核心公式：(ptr + 1) % MAX。这个公式是环形缓冲区的灵魂。

3. 核心操作——入队与出队的正确顺序

3.1 入队 enqueue：先赋值，再移动

enqueue_order.c

// ✅ 正确顺序：先放值，再移指针
queue[rear] = val;          // ① 把值放到 rear 指向的位置
rear = (rear + 1) % MAX;    // ② rear 绕环前移

为什么必须"先放值，再移动"？

初始状态: front=0, rear=0

方案 A（先移再放）:  rear = (0+1)%MAX = 1
                   queue[1] = val   ← 位置 0 被跳过了！永远不被使用 ✗

方案 B（先放再移）:  queue[0] = val  ← 位置 0 被正确使用 ✓
                   rear = (0+1)%MAX = 1

rear 在初始状态下指向 0——这是第一个可用位置。
如果先移动 rear，0 号槽就永久浪费了。

3.2 出队 dequeue：先取值，再移动

dequeue_order.c

// ✅ 正确顺序：先取值，再移指针
int val = queue[front];     // ① 从 front 位置取出值
front = (front + 1) % MAX;  // ② front 绕环前移
return val;

出队的移动逻辑同样简单——取出当前位置的值后，front 前移一步（取模回绕），指向下一个待出队元素。

IMPORTANT

之所以强调"先 X 后移"的顺序，是因为在初始状态下 front == rear == 0。如果顺序颠倒，初始槽位会被跳过或误用。这是环形队列中最容易被忽略的细节，也是"最小值最小细节处"（fencepost error）的典型案例。

4. 逐步跟踪：环绕过程的完整演示

以 MAX=4 的环形队列为例，完整展示入队和出队的全过程：

═══════════════════════════════════════════════════════
初始状态
═══════════════════════════════════════════════════════
 数组: [ _ ][ _ ][ _ ][ _ ]    索引: 0    1    2    3
 front=0, rear=0
 队空: front==rear → true ✓

═══════════════════════════════════════════════════════
操作 1: enqueue(10)
═══════════════════════════════════════════════════════
 queue[0] = 10                    // rear=0 位置放入 10
 rear = (0+1) % 4 = 1            // rear 前移

 数组: [ 10 ][ _ ][ _ ][ _ ]    索引: 0    1    2    3
 front=0, rear=1
 队空: front(0)==rear(1)? → false, 队列中有 1 个元素

═══════════════════════════════════════════════════════
操作 2: enqueue(20)
═══════════════════════════════════════════════════════
 queue[1] = 20                    // rear=1 位置放入 20
 rear = (1+1) % 4 = 2

 数组: [ 10 ][ 20 ][ _ ][ _ ]
 front=0, rear=2

═════════════════════════════════════════════════════════
操作 3: enqueue(30)
═══════════════════════════════════════════════════════
 queue[2] = 30
 rear = (2+1) % 4 = 3

 数组: [ 10 ][ 20 ][ 30 ][ _ ]
 front=0, rear=3
 队满?: (3+1)%4=0==front(0) → true, 满了!

═════════════════════════════════════════════════════════
操作 4: dequeue() → 应返回 10
═══════════════════════════════════════════════════════
 val = queue[0] = 10
 front = (0+1) % 4 = 1

 数组: [ _ ][ 20 ][ 30 ][ _ ]    // 位置0空出来了!
 front=1, rear=3

═══════════════════════════════════════════════════════
操作 5: dequeue() → 返回 20
═══════════════════════════════════════════════════════
 val = queue[1] = 20
 front = (1+1) % 4 = 2

 数组: [ _ ][ _ ][ 30 ][ _ ]
 front=2, rear=3

═══════════════════════════════════════════════════════
操作 6: enqueue(40) — 关键！rear 绕回
═══════════════════════════════════════════════════════
 queue[3] = 40
 rear = (3+1) % 4 = 0             // ← 取模让 rear 从 3 绕回到 0！

 数组: [ _ ][ _ ][ 30 ][ 40 ]
 front=2, rear=0
 注意: rear=0 < front=2 —— 这是环形队列的常态

═══════════════════════════════════════════════════════
操作 7: enqueue(50)
═══════════════════════════════════════════════════════
 queue[0] = 50                    // rear=0 现在指向位置0（已出队的空间被重用！）
 rear = (0+1) % 4 = 1

 数组: [ 50 ][ _ ][ 30 ][ 40 ]
 front=2, rear=1

═══════════════════════════════════════════════════════
操作 8: 连续出队
═══════════════════════════════════════════════════════
 dequeue(): val=queue[2]=30, front=(2+1)%4=3
 dequeue(): val=queue[3]=40, front=(3+1)%4=0
 dequeue(): val=queue[0]=50, front=(0+1)%4=1

 数组: [ _ ][ _ ][ _ ][ _ ]
 front=1, rear=1 → front==rear → 队空! ✓

关键观察：

rear 从 3 绕回 0（操作 6）——环形队列的"环形"就在这里
front 从 3 绕回 0（操作 8）——出队的指针同样可以绕回
最终 front == rear == 1——虽然是"空"但指针不一定回到 0——这就是环形队列的常态

5. 队空与队满——为什么必须牺牲一个位置？

5.1 核心矛盾：front==rear 一种状态，两种含义

问题: 如果允许存满 MAX 个元素，队满时会发生什么？

  全部入队 MAX 个元素后:  rear 走了一圈，追上 front
                         rear == front
  
  但同时: front == rear 在初始状态也表示队空！

  同一个条件，无法区分两种状态 → 语义歧义

5.2 约定：永远留一个空位

队空: front == rear
队满: (rear + 1) % MAX == front     ← rear 在 front 的"前一步"

  ┌───┬───┬───┬───┐
  │ A │ B │ C │ _ │   ← rear 停在 front 的前一个位置
  └───┴───┴───┴───┘   → 队满！实际容量 = MAX - 1 = 3
    ↑       ↑
   front   rear

  (rear+1) % MAX = (2+1) % 4 = 3
  front = 0
  → (rear+1) % MAX == front? 3 == 0? → false

  再入队一个:
  ┌───┬───┬───┬───┐
  │ A │ B │ C │ D │
  └───┴───┴───┴───┘
   ↑            ↑
  front      rear=3

  (3+1) % 4 == 0 == front → 队满! ✓

代价：容量从 MAX 降为 MAX - 1。对于 MAX=64 来说，损失 1/64 ≈ 1.6% 的空间——可以接受。

状态	条件	说明
队空	`front == rear`	初始状态，或全部出队后
队满	`(rear + 1) % MAX == front`	rear 即将追上 front
非空	`front != rear`	至少有一个元素

NOTE

本课练习不要求实现队满检查（题目保证输入不超 MAX）。但在生产代码中，队满检查是必须的——否则会发生静默的数据覆盖。

5.3 count 变量——另一种队满方案

如果不愿意牺牲一个位置，可以增加 count 变量：

count_approach.c

int count = 0;  // 当前队列中的元素数量

void enqueue(int val) {
    if (count == MAX) return;  // 队满
    queue[rear] = val;
    rear = (rear + 1) % MAX;
    count++;                   // 增加计数
}

int dequeue(void) {
    if (count == 0) return -1; // 队空
    int val = queue[front];
    front = (front + 1) % MAX;
    count--;                   // 减少计数
    return val;
}

// 现在:
//   队空: count == 0
//   队满: count == MAX
//   容量: MAX（不需要牺牲位置）

代价：多一个 int 变量（4 字节），每次入队/出队多一句 count++/count--。在实际工程中，这个开销可以忽略——count 方案在可读性和容量上都是优选，但增加了代码行数和出错点（需要保证 count 与 front/rear 的一致性）。

6. 性能优化与工程应用

6.1 取模 vs 位与——当 MAX 是 2 的幂

取模运算 % 在硬件上是除法指令，比加减和位运算慢得多。当 MAX 是 2 的幂（如 64=2^6, 128=2^7）时，可以用位与替代：

bitwise_optimization.c

#define MAX 64          // 64 = 2^6

// % 写法（慢）
rear = (rear + 1) % MAX;

// & 写法（快）——仅当 MAX 是 2 的幂时才等价
rear = (rear + 1) & (MAX - 1);   // & (64-1) = & 63

为什么 &(MAX-1) 等价于 %MAX（当 MAX 是 2 的幂）？

  MAX = 64 = 0b1000000
  MAX-1 = 63 = 0b0111111

  任何数 & 63 的效果 = 保留低 6 位，清零高位
  任何数 % 64 的效果 = 除以 64 的余数 = 低 6 位的值

  两者数学上等价 ✓

性能差异: 取模 ~20-80 CPU 周期, 位与 ~1 CPU 周期
在每秒百万次队列操作的网络栈中，这个差异非常可观。

TIP

这正是为什么 Linux 内核和其他高性能系统中，环形缓冲区的大小几乎总是 2 的幂（如 256、512、1024）。kfifo 的设计哲学之一是"用数据结构保证性能，而非寄希望于编译器优化"。

6.2 Linux kfifo——无锁环形缓冲的工业典范

Linux 内核的 kfifo 是一种无锁单生产者单消费者环形缓冲——不需要互斥锁，仅依赖内存屏障（memory barrier）：

kfifo_concept.c

// kfifo 的核心概念（伪代码，非真实内核代码）
// 使用 unsigned int 索引，依赖无符号整数的自然回绕

struct kfifo {
    unsigned int in;      // 生产者在此写入的位置（类比 rear）
    unsigned int out;     // 消费者在这里读取的位置（类比 front）
    unsigned int mask;    // 大小掩码 = size - 1（size 必须是 2 的幂）
    unsigned char *data;  // 数据缓冲区
};

// 入队：写入数据，更新 in
// 出队：读取数据，更新 out
// 关键：in 只由生产者写，out 只由消费者写
//       → 两个指针的更新无竞争 → 不需要锁！

kfifo 无锁的原理:

  生产者线程          消费者线程
     │                   │
     │ 读 in, out        │ 读 in, out
     │ 写入数据          │ 读取数据
     │ 写 in ← 独占      │ 写 out ← 独占
     │                   │
  两者没有共享写的变量 → 不需要互斥锁
  只需要内存屏障确保数据的可见性顺序

  这是高性能网络栈（DPDK、XDP）的核心组件，
  每秒可处理数千万到数亿次操作。

7. 常见错误与陷阱

错误	后果	正确做法
忘取模 `rear++` 代替 `(rear+1)%MAX`	数组越界	必须用取模实现环绕
入队先移 rear 再赋值	跳过 0 号槽	`queue[rear]=val; rear=(rear+1)%MAX;`
dequeue 忘取模	front 无限增长	`front=(front+1)%MAX`
混淆 front/rear 语义	逻辑完全错乱	front=队头, rear=队尾下一个空位
出队时不判断队空	读取已出队或无效数据	调用前检查 `is_empty()`

参考解答

练习: enqueue 和 dequeue 完整实现

solution_35_queue_base.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 64

int queue[MAX];
int front = 0, rear = 0; /* front == rear 表示队空 */

int is_empty(void) { return front == rear; }

/* 入队：先放值，再移动 rear */
void enqueue(int val)
{
    queue[rear] = val;
    rear = (rear + 1) % MAX;
}

/* 出队：先取值，再移动 front */
int dequeue(void)
{
    int val = queue[front];
    front = (front + 1) % MAX;
    return val;
}

int main(void)
{
    char line[256];
    fgets(line, sizeof(line), stdin);

    /* 解析数字并入队 */
    char *tok = strtok(line, " \n");
    while (tok) {
        enqueue(atoi(tok));
        tok = strtok(NULL, " \n");
    }

    /* 全部出队并打印，空格分隔，最后换行 */
    int first = 1;
    while (!is_empty()) {
        if (!first) printf(" ");
        printf("%d", dequeue());
        first = 0;
    }
    printf("\n");

    return 0;
}

核心逻辑解析：

入队顺序：queue[rear] = val 先放值，rear = (rear+1) % MAX 再移指针。先放后移保证初始时 0 号槽被正确使用。
出队顺序：val = queue[front] 先取值，front = (front+1) % MAX 再移指针。取值和移动的对应关系与入队一致。
取模回绕：(ptr+1) % MAX 在 ptr 到达 MAX-1 时绕回 0，实现"环形"语义。
FIFO 验证：入队顺序 10 20 30 → 出队顺序 10 20 30——先进先出，与测试用例完全一致。

对照检查：入队是先赋值再取模移动 rear 吗？出队是先取值再取模移动 front 吗？出队用 is_empty() 判断终止了吗？空格格式正确吗（最后没有多余空格）？

课堂讨论

如果入队顺序改为 rear = (rear+1)%MAX; queue[rear] = val;（先移再放），在初始状态下会发生什么？为什么 0 号槽被浪费？
为什么队空是 front == rear，队满要设为 (rear+1)%MAX == front？能不能让队满也等于 front == rear？如果不能，原因是什么？
如果想存满 MAX 个元素（不牺牲一个位置），有哪些方案？各自的代价是什么？
取模运算 % 在硬件上为什么比 + 和 - 慢？当 MAX=64 时，用什么位运算可以替代 %MAX？
队列（FIFO）和栈（LIFO）分别适合什么场景？如果在消息系统中，你想要"后到的消息先处理"，应该用哪个数据结构？

讨论答案

Q1: 先移再放为什么会浪费 0 号槽？

初始 rear=0，先执行 rear = (0+1)%MAX = 1，然后 queue[1] = val——0 号槽被跳过。

初始: front=0, rear=0

先移再放:
  enqueue(10): rear = (0+1)%MAX = 1  →  queue[1] = 10

  数组: [ _ ][ 10 ][ _ ][ ... ]
          ↑
    位置 0 永远不会被写到！整个队列生命周期中都是空的

先放再移:
  enqueue(10): queue[0] = 10  →  rear = (0+1)%MAX = 1

  数组: [ 10 ][ _ ][ _ ][ ... ]
          ↑
    位置 0 被正确使用 ✓

这是 fencepost error（栅栏错误）的一个典型案例——在初始状态下，指针已经指向正确位置，但不当的操作让它"提前移动"，导致第一个位置被跳过。

Q2: 队满为什么不能等于 front==rear？

因为 front == rear 已经用来表示队空了，同一个条件不能有两个含义。

问题: 如果不牺牲位置，当队列存满 MAX 个元素时:

  enqueue × MAX 次后:
  rear 绕了一圈，位置上追上了 front
  → rear == front

  但初始状态也是 front == rear == 0

  两种状态:
    初始状态 → front==rear → 队空
    存满状态 → front==rear = ?
    
  编译器无法区分这两种情况 → 必须有额外信息

解决方案 1（本题采用）：牺牲一个位置，队满定义为 (rear+1)%MAX == front，让队满时的 rear 和 front 不可能相等。

解决方案 2：增加 count 变量，队空 count==0，队满 count==MAX，front/rear 只负责定位。

选择哪种取决于优先级——牺牲一个位置减少一个变量，还是多一个变量换取多一个槽位。

Q3: 存满 MAX 的方案与代价

方案 1：count 变量

int count = 0;

void enqueue(int val) {
    if (count == MAX) return;  // 队满
    queue[rear] = val;
    rear = (rear + 1) % MAX;
    count++;
}

int dequeue(void) {
    if (count == 0) return -1;  // 队空
    int val = queue[front];
    front = (front + 1) % MAX;
    count--;
    return val;
}

代价：多 4 字节的 count 变量，每次入队/出队各多一次 ++ 操作。

方案 2：标记位

int is_full_flag = 0;

void enqueue(int val) {
    if (is_full_flag) return;
    queue[rear] = val;
    rear = (rear + 1) % MAX;
    if (rear == front) is_full_flag = 1;  // rear 追上 front 置标记
}

int dequeue(void) {
    if (front == rear && !is_full_flag) return -1;  // 真正的队空
    int val = queue[front];
    front = (front + 1) % MAX;
    is_full_flag = 0;  // 出队后肯定不满了
    return val;
}

代价：多一个 int 变量，额外判断逻辑。count 方案更简洁直观，标记位方案更省操作（不减计数）。

Q4: 取模为什么慢，位与如何替代

取模 % 在硬件上是除法指令（DIV/IDIV），需要数十个 CPU 周期。位与 & 是位操作指令，只需 1 个周期。

性能对比（x86-64）:
  ADD/SUB:  ~1 周期
  AND/OR:   ~1 周期
  DIV/IDIV: ~20-80 周期  ← 取模是用除法实现的！

用位与替代取模的前提:
  MAX 必须是 2 的幂（2^k）

  (ptr + 1) % MAX  →  (ptr + 1) & (MAX - 1)

  例: MAX = 64 = 0b1000000
      MAX-1 = 63 = 0b00111111
      
      (63 + 1) & 63 = 64 & 63 = 0  ✓  绕回 0
      (0 + 1) & 63 = 1 & 63 = 1    ✓  正常前进

这就是为什么 Linux kfifo 的大小永远是 2 的幂——它用 in & mask 而非 in % size，在高吞吐量下性能差异可达数十倍。

Q5: 栈 vs 队列——各自适合什么场景

场景	适合的数据结构	原因
函数调用/递归	栈	调用是嵌套的——最后调用的函数最先返回
撤销操作 (Undo)	栈	"最近的"操作应该最先撤销
DFS 深度优先搜索	栈	深入分支时，最近的节点最先处理
括号匹配	栈	最近的左括号与当前右括号配对
-----	-------	------
打印任务调度	队列	先提交的文档先打印——公平
BFS 广度优先搜索	队列	逐层扩展，同一层的节点按到达顺序处理
消息缓冲/削峰填谷	队列	生产者放、消费者取，缓冲速率差异
网络数据包缓冲	队列	数据包按到达顺序处理

关于消息系统的回答：如果"后到的消息先处理"，应该用栈。但绝大多数消息系统（Kafka、RabbitMQ）用队列——因为公平调度比"最新的先处理"更符合实际需求。栈适用于"优先级倒置"场景（如紧急中断处理）。

课后练习

实现 is_full() 函数：编写 int is_full(void)，返回 (rear+1)%MAX == front。在 enqueue 中调用它，入队前检查是否满。
知识点提示：is_full 的条件对称于 is_empty——is_empty: front == rear，is_full: (rear+1)%MAX == front。注意满时不能再入队，需返回错误。
参考解答
queue_with_is_full.c
c
```
int is_full(void) { return (rear + 1) % MAX == front; }

int enqueue_safe(int val) {
    if (is_full()) return -1;   /* 满，拒绝入队 */
    queue[rear] = val;
    rear = (rear + 1) % MAX;
    return 0;                    /* 成功 */
}
```
1
2
3
4
5
6
7
8
实现 queue_size() 函数：返回当前队列中的元素数量。提示：需要考虑 rear < front（rear 绕回到前面）的情况。
知识点提示：当 rear >= front 时，元素数 = rear - front；当 rear < front 时（rear 已绕回），元素数 = MAX - front + rear。统一公式：(rear - front + MAX) % MAX。
参考解答
queue_size.c
c
```
int queue_size(void) {
    return (rear - front + MAX) % MAX;
}

// 测试:
// front=0, rear=3 → (3-0+64)%64 = 3  ✓
// front=60,rear=2 → (2-60+64)%64 = 6 ✓ (绕回后有6个元素)
// front=5, rear=5 → (5-5+64)%64 = 0  ✓ (队空)
```
1
2
3
4
5
6
7
8

入队出队对调实验：故意将入队顺序改为"先移 rear 再赋值"，将出队顺序改为"先移 front 再取值"，然后用测试用例验证结果。记录哪些值被错误地移出队列，解释原因。

知识点提示：入队先移 → 位置 0 为空，最后一个元素溢出到位置 MAX（越界）。出队先移 → 第一个元素被跳过，取到的是下一个位置的值。这两者都会破坏 FIFO 的正确性。

参考解答

broken_queue.c

// ❌ 错误的入队：先移再放
void enqueue_broken(int val) {
    rear = (rear + 1) % MAX;
    queue[rear] = val;  // 位置0永远不会被写到！
}

// ❌ 错误的出队：先移再取
int dequeue_broken(void) {
    front = (front + 1) % MAX;
    return queue[front];  // 第一次调用时跳过 queue[0]！
}

// 测试: enqueue(10, 20, 30); then 全部 dequeue
// 预期: 10 20 30
// 实际: 0 20 30（enqueue先移跳过0号槽，queue[0]=0; 
//            dequeue先移跳过queue[0]，第一次取到queue[1]=20）
// 更糟: 如果队列存满导致 rear 绕回 writing over 0号槽...

环形缓冲区的生产-消费模拟：实现一个简单的生产者-消费者模拟程序：一个线程（或循环）持续入队随机数，另一个持续出队，统计处理速率。观察环形队列在高速率下的行为。
知识点提示：在 C 中可以用 pthread 或单线程"交错"模拟生产消费。通过 clock() 计时，观察吞吐量与队列大小的关系。不必实现真正的多线程——理解生产-消费模式中"缓冲削峰"的价值即可。

参考资料

Linux 内核源码 lib/kfifo.c — 工业级无锁环形缓冲区实现，内存屏障的经典用例
《数据结构与算法分析 — C 语言描述》队列章节 — Queue ADT 的完整定义与链表/数组两种实现
POSIX 消息队列 mq_open/mq_send — 操作系统的队列抽象，应用于进程间通信
DPDK 环形缓冲区 (rte_ring) — 高性能数据平面的无锁环形缓冲，每秒数亿次操作
K&R《C 程序设计语言》§5.4 — 取模运算在环形数组中的应用，包含简单的环形缓冲代码

"The difference between theory and practice is smaller in theory than it is in practice." — Anonymous

Lesson 35: 循环队列基础 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 队列的基本概念——FIFO 的语义 ​

1.1 什么是队列——排队的直觉 ​

1.2 环形队列的两个指针：front 与 rear ​

1.3 栈 vs 队列——一对"互补兄弟" ​

2. 为什么需要"环形"——线性队列的"假溢出" ​

2.1 问题：front 前面的空间被浪费了 ​

2.2 解决方案：取模回绕 ​

3. 核心操作——入队与出队的正确顺序 ​

3.1 入队 enqueue：先赋值，再移动 ​

3.2 出队 dequeue：先取值，再移动 ​

4. 逐步跟踪：环绕过程的完整演示 ​

5. 队空与队满——为什么必须牺牲一个位置？ ​

5.1 核心矛盾：front==rear 一种状态，两种含义 ​

5.2 约定：永远留一个空位 ​

5.3 count 变量——另一种队满方案 ​

6. 性能优化与工程应用 ​

6.1 取模 vs 位与——当 MAX 是 2 的幂 ​

6.2 Linux kfifo——无锁环形缓冲的工业典范 ​

7. 常见错误与陷阱 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 35: 循环队列基础

练习任务

核心知识点

代码框架

深度讲解

1. 队列的基本概念——FIFO 的语义

1.1 什么是队列——排队的直觉

1.2 环形队列的两个指针：front 与 rear

1.3 栈 vs 队列——一对"互补兄弟"

2. 为什么需要"环形"——线性队列的"假溢出"

2.1 问题：front 前面的空间被浪费了

2.2 解决方案：取模回绕

3. 核心操作——入队与出队的正确顺序

3.1 入队 enqueue：先赋值，再移动

3.2 出队 dequeue：先取值，再移动

4. 逐步跟踪：环绕过程的完整演示

5. 队空与队满——为什么必须牺牲一个位置？

5.1 核心矛盾：front==rear 一种状态，两种含义

5.2 约定：永远留一个空位

5.3 count 变量——另一种队满方案

6. 性能优化与工程应用

6.1 取模 vs 位与——当 MAX 是 2 的幂

6.2 Linux kfifo——无锁环形缓冲的工业典范

7. 常见错误与陷阱

参考解答

课堂讨论

讨论答案

课后练习

参考资料