Appearance
循环队列
核心思想
循环队列使用长度为 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)，所有操作只需常数级辅助空间。
易错：循环队列区分队空和队满是核心考点。常见方案有三种：1)牺牲一个存储单元（队满条件
(rear+1)%MaxSize == front）；2)增加 size 变量；3)增加 tag 标志。408 默认用方案1，此时队列最多存 MaxSize-1 个元素。
易错：循环队列的元素个数公式：
(rear - front + MaxSize) % MaxSize。不要忘记加 MaxSize 再取模——直接rear - front可能得到负数。
考研高频考点
- ⭐ 判满判空三种方案的区别与表达式（选择题/简答题高频）
- ⭐ 元素个数公式
(rear - front + MaxSize) % MaxSize（填空题必考） - ⭐ 给定 front、rear、MaxSize，求队列长度或判断状态（计算题）
- ⭐ 循环队列解决假溢出的原理（概念题）
- 入队/出队操作的代码填空（算法填空题）
rear和front的含义约定（指向队尾元素 vs 队尾下一个位置，不同教材有差异）
相关知识
- 链式队列是队列的链式实现，不存在假溢出问题，但每个结点多一个指针开销
- 双端队列是队列的推广，两端都能进出；循环队列只是普通队列的顺序存储优化
- 循环队列的"首尾相连"思想与循环链表类似——都是通过逻辑上的环形结构复用空间
- 操作系统中的进程调度队列、打印缓冲区等场景通常用循环队列实现，因为容量可预估且不需要动态分配内存