Appearance
循环队列
为什么需要循环队列
普通顺序队列用数组实现时，随着反复入队、出队，front 和 rear 指针不断后移，即使数组前端已有空闲位置也无法再利用，产生假溢出现象：
已出队（浪费） 有效元素 rear 已到末尾 → 报满
[ ][ ] [a3][a4][a5]
↑front ↑rear循环队列的思路：把数组在逻辑上首尾相连，形成一个"环"。当指针到达数组末尾时，通过取模运算让它回到数组开头，从而复用前端空闲空间，彻底解决假溢出问题。
核心思想
循环队列使用长度为 MaxSize 的数组 data，维护两个指针：
front：指向队头元素rear：指向队尾元素的下一个位置（即下一个入队位置）
指针移动的核心公式（取模实现"循环"）：
front = (front + 1) % MaxSize // 出队后 front 前进
rear = (rear + 1) % MaxSize // 入队后 rear 前进初始状态：front = rear = 0。
基本结构定义：
c
#define MaxSize 10
typedef struct {
int data[MaxSize];
int front, rear;
} SqQueue;交互可视化
通过下方的交互动画，你可以逐步观察循环队列的执行过程：
操作详解
入队操作
将新元素放入 rear 指向的位置，然后 rear 后移一位（取模）。
关键步骤：
- 判断队列是否已满
- 将元素存入
data[rear] rear = (rear + 1) % MaxSize
c
bool EnQueue(SqQueue *Q, int x) {
if ((Q->rear + 1) % MaxSize == Q->front)
return false; // 队满
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MaxSize;
return true;
}出队操作
取出 front 指向的元素，然后 front 后移一位（取模）。
关键步骤：
- 判断队列是否为空
- 取出
data[front]的值 front = (front + 1) % MaxSize
c
bool DeQueue(SqQueue *Q, int *x) {
if (Q->front == Q->rear)
return false; // 队空
*x = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
return true;
}判满与判空
循环队列中 front == rear 时可能是队空也可能是队满，必须加以区分。408 常考以下三种方案：
方案一：牺牲一个存储单元（最常用） ⭐
约定 rear 的下一个位置是 front 时为满，即始终保留一个空位不存数据。
| 条件 | 表达式 |
|---|---|
| 队空 | front == rear |
| 队满 | (rear + 1) % MaxSize == front |
| 元素个数 | (rear - front + MaxSize) % MaxSize |
此时队列最多存放 MaxSize - 1 个元素。
方案二：增设 size 计数器
额外维护一个 size 变量，入队 size++，出队 size--。
| 条件 | 表达式 |
|---|---|
| 队空 | size == 0 |
| 队满 | size == MaxSize |
| 元素个数 | size |
此时队列可用满全部 MaxSize 个位置。
方案三：增设 tag 标志位
用 tag 记录最近一次操作类型：入队置 tag = 1，出队置 tag = 0。
| 条件 | 表达式 |
|---|---|
| 队空 | front == rear && tag == 0 |
| 队满 | front == rear && tag == 1 |
逻辑：只有连续入队才可能导致满，只有连续出队才可能导致空。
⭐ 元素个数公式（三种方案通用）：
(rear - front + MaxSize) % MaxSize。当采用方案二/三使队列存满时，该公式结果为 0 需特判，因此考试中最常搭配方案一使用。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 入队 | O(1) | 直接在 rear 位置写入 |
| 出队 | O(1) | 直接取 front 位置元素 |
| 获取队头 | O(1) | 访问 data[front] |
| 判空/判满 | O(1) | 指针比较或计数器判断 |
空间复杂度：O(1)，所有操作只需常数级辅助空间。
考研高频考点
- ⭐ 判满判空三种方案的区别与表达式（选择题/简答题高频）
- ⭐ 元素个数公式
(rear - front + MaxSize) % MaxSize（填空题必考） - ⭐ 给定 front、rear、MaxSize，求队列长度或判断状态（计算题）
- ⭐ 循环队列解决假溢出的原理（概念题）
- 入队/出队操作的代码填空（算法填空题）
rear和front的含义约定（指向队尾元素 vs 队尾下一个位置，不同教材有差异）