p22（9 分钟）、p23（14.4 分钟）、p24（13.7 分钟）
基本介绍
队列 = 现实里的排队：FIFO（先进先出）。栈是 LIFO，插入和移除都在同一端，也就是栈顶。
术语约定
插入必须从一端进行 → 称「后端 / 尾部」（rear / tail）删除必须从另一端进行 → 称「前端 / 头部」（front / head）操作接口
| 操作 | 含义 | 返回 |
|---|---|---|
| enqueue | 插入（也有人叫 push） | void |
| dequeue | 删除（也有人叫 pop） | 通常返回被移除的元素 |
| front（peek） | 只返回前端元素，不删除任何东西 | 元素值 |
| isEmpty | 是否为空 | 布尔 |
| isFull | 队列大小有限时可用 | 布尔 |
命名上要留神：C++ 内置队列的插入函数叫 push，C 里叫 enqueue。
以上所有操作都必须花费恒定时间，时间复杂度 O(1)。
逻辑视图
队列：两边开口的容器（元素从一侧入、从另一侧出）栈： 单侧开口的容器演示
空队列enqueue 2 → front 和 rear 指向同一个元素enqueue 5 → 插到尾部enqueue 一个dequeue → 取出 2（返回整数 2）front → 得到 5（不删除）isEmpty → 返回布尔值（0 假 / 1 真）应用场景
共享资源一次只能服务一个请求时，把请求排队最合理，先到的先服务
例：网络共享打印机（一次只打印一份，忙碌时请求进队列）例：CPU / 处理器是共享资源，多个进程竞争处理器时间，进程被放进队列一般用于模拟各种等待情形数组实现
这一节的核心是「从线性到环形」的推导。
术语约定（线性数组版）
用数组 A（例：10 个整数）约定：从 front 索引到 rear 索引这一段属于队列，其余为空闲front 与 rear 初始都设为 -1空队列用 front == rear == -1 表示（-1 不是有效索引）哪一边是 front、哪一边是 rear 无关紧要，但元素必须总是从后端加入、从前端移除。
入队（线性版）
若 rear == 数组最大可用索引 → 队列已满（用 isFull 判断）→ 直接 return否则若队列为空 → 把 front 和 rear 都置为 0，再写入 A[rear] = x否则 → rear++，然后 A[rear] = x出队（线性版）
若队列为空 → 打印/抛错并 return（不能移除）否则若 front == rear（队列中只有一个元素）→ 把 front 和 rear 都设回 -1否则（正常情况）→ 只需 front++原来 front 指向的单元直接丢弃，值不必清理，因为入队时会覆盖。
空队列、单元素队列这两种边界得单独处理——大多数漏洞都出在这儿。
线性实现的致命问题
演示：连续入队直到 rear == 最大索引此时队列中还有两个未使用的空单元（在 front 左侧）但无法再入队，操作失败
随着不断出队，front 左边的所有单元格再也不会被使用，只会被浪费掉解决方案：环形数组
把数组想象成没有尽头：到最后一个索引后回到索引 0。这只是看待数组的一种逻辑方式。
取模公式：
下一个位置 = (i + 1) % N前一个位置 = (i + N - 1) % N （加 N 是为了保证括号内表达式始终为正）验证：对除 N-1 外的 i 取模无影响；当 i = N-1 时 (N-1+1) % N = 0（一个数除以自身的余数为 0）。
环形版三个关键条件
判满： (rear + 1) % N == front判空： front == rear == -1 （与线性版相同）入队： 队列为空 → front 和 rear 都设为 0；否则 rear = (rear + 1) % N 再写值出队： 空/单元素边界不变；否则 front = (front + 1) % N演示：当前 rear = 9、N = 10 → (9+1)%10 = 0 → 新 rear 为 0，在索引 0 处写入 15。
判满条件隐含一个后果：
始终保留一个空单元→ 数组容量 N，实际只能存 N-1 个元素这是环形队列的固有代价，不是 bug。
front 操作
直接返回 A[front] 处的元素；需要先检查队列是否为空，只有 front != -1 时才返回。
复杂度
以上所有函数都只做简单算术运算和赋值，没有循环，耗时与队列规模无关 → 全部 O(1)。
链表实现
数组实现的两个局限
① 数组大小固定。用尽时只有两条路： 拒绝插入（宣称队列已满），或新建更大数组并复制旧元素 —— 复制成本高，为 O(n)
② 可能「数组足够大但队列并未充分利用」，大量内存被浪费 （例：90% 内存未使用）现代机器上这点浪费不是真问题，但设计算法时应当分析并理解这些影响。
为什么要维护两个指针
关键：队列的两端操作必须在链表的两端，且两个操作都必须是 O(1)。
若选头部入队 → 出队必须在尾部若选尾部入队 → 出队必须在头部
单纯实现下，插入或删除必有一个是 O(n)（从头部插入/移除是 O(1)，从尾部插入/移除是 O(n)，因为要遍历到尾节点）解决办法：额外维护一个尾指针。
存头节点地址的变量叫 front始终存尾节点地址的变量叫 rear（也叫 tail）于是在尾部入队不必再遍历：直接改尾节点的地址域建立链接，再更新 rear。
最终入队从尾部、出队从头部，两者都是 O(1)。
任何插入或移除操作中都必须同时更新 front 和 rear。
代码
struct Node { int data; struct Node *next;};
struct Node *front = NULL; /* 不声明 head */struct Node *rear = NULL;
void enqueue(int x) { struct Node *temp = malloc(sizeof(struct Node)); temp->data = x; temp->next = NULL;
if (front == NULL && rear == NULL) { /* 队列为空 */ front = rear = temp; return; } rear->next = temp; /* 挂到尾部 */ rear = temp; /* 更新尾指针 */}
void dequeue() { struct Node *temp = front; /* 先保存当前前端地址 */
if (front == NULL && rear == NULL) { /* 队列为空 */ printf("Error: queue is empty\n"); return; } if (front == rear) { /* 只有一个元素 */ front = rear = NULL; } else { front = front->next; } free(temp); /* 必须释放 */}free(temp) 不能省。只让 front 前进是不够的，原前端节点仍留在动态内存中，而动态内存里的任何东西都必须被显式释放——这正是声明 temp 指针的原因。
演示
空队列 front/rear 都是 NULL（NULL 就是地址 0 的宏）enqueue 2 → 新节点地址 100，进入 if 分支，front = rear = 100 函数结束局部变量 temp 被清除enqueue 4 → 新节点地址 200，走 rear->next = temp; rear = temp;enqueue 6 → 地址 300dequeue → temp 保存原 front，front 前移，再 free复杂度
函数里全是简单语句、没有循环 → 入队和出队都是 O(1)。
结论
链表实现没有数组实现的那些局限：不会满、不会浪费未用内存。代价只是每个节点多用一个指针域存地址，除此之外没有其他重大缺点。
两种实现对比
| 数组实现 | 链表实现 | |
|---|---|---|
| 入队 | O(1) | O(1) |
| 出队 | O(1) | O(1) |
| 容量 | 固定（环形版实际 N−1） | 不固定 |
| 内存浪费 | 可能大量浪费 | 无（但每节点多一个指针） |
| 需要的指针/索引 | front / rear（初值 −1） | front / rear（初值 NULL） |
| 判空 | front == rear == −1 | front == NULL && rear == NULL |
| 判满 | (rear+1) % N == front | 不需要 |
坑
- 数组实现的 front / rear 初值都是 −1，判空是
front == rear == −1，不是front == rear。 - 环形判满是
(rear + 1) % N == front，不是rear + 1 == front；而且始终浪费一个单元，容量是 N−1。 - 单元素队列出队后要把 front 和 rear 都重置（数组版置 −1，链表版置 NULL）。
- 链表实现必须维护尾指针，否则尾部操作是 O(n)；dequeue 必须 free，只移动 front 会内存泄漏。
- 空队列和单元素队列必须单独处理。
请输入编辑凭据，只有站点所有者可以修改文章。