循环队列的判满和求长度 · 融合风（象牙 + Obsidian 入口）

速查

牺牲一个单元方案：队空 front == rear；队满 (rear+1) % MaxSize == front；长度 (rear-front+MaxSize) % MaxSize（加 MaxSize 防负数）。最多存 MaxSize-1 个。

核心概念 ▾

循环队列将顺序队列的逻辑上首尾相连，形成"环"，以解决假溢出问题。

为什么要用循环队列

普通顺序队列：入队时 rear 向后移动，出队时 front 向后移动；当 rear 到达数组末尾时，即使前面有空位也无法入队——这就是假溢出。

假溢出示例（MaxSize=6）：
┌───┬───┬───┬───┬───┬───┐
│   │   │ c │ d │   │   │
└───┴───┴───┴───┴───┴───┘
 0   1   2   3   4   5
         ↑f      ↑r
front=2, rear=4（rear 已到末尾，但 0,1,5 仍空着）

循环队列的实现

#define MaxSize 6
typedef struct {
    ElemType data[MaxSize];
    int front, rear;  // 队头和队尾指针
} SqQueue;

方案一 · 牺牲一个存储单元 ▾

约定：队尾指针的下一个位置是队头时，认为队满。rear 指向下一个空位置。

队空条件：$Q.front == Q.rear$
队满条件：$(Q.rear + 1) \% MaxSize == Q.front$
队列长度：$(Q.rear - Q.front + MaxSize) \% MaxSize$

队满示例（MaxSize=6，牺牲一个位置）：
┌───┬───┬───┬───┬───┬───┐
│ e │ f │ a │ b │ c │ d │
└───┴───┴───┴───┴───┴───┘
 0   1   2   3   4   5
     ↑r      ↑f
front=2, rear=1，(rear+1)%6 = 2 = front → 队满
实际存了 5 个，最多能存 MaxSize-1 = 5 个

方案二 · 增加 size 变量 ▾

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
    int size;  // 当前元素个数
} SqQueue2;

队空条件：$Q.size == 0$
队满条件：$Q.size == MaxSize$
队列长度：$Q.size$

方案三 · 增加 tag 变量 ▾

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
    int tag;  // 最近一次操作：0=删除，1=插入
} SqQueue3;

队空条件：$Q.front == Q.rear \&\& Q.tag == 0$
队满条件：$Q.front == Q.rear \&\& Q.tag == 1$

原理当 $front == rear$ 时，若最近一次是插入（$tag=1$），说明刚插满；若最近一次是删除（$tag=0$），说明刚删空。

关键性质 ▾

取模运算

入队：$Q.rear = (Q.rear + 1) \% MaxSize$
出队：$Q.front = (Q.front + 1) \% MaxSize$
求长度：$(Q.rear - Q.front + MaxSize) \% MaxSize$（加 MaxSize 防止负数）

方案	空间利用	额外开销	复杂度
牺牲一个单元	MaxSize-1	无	简单
增加 size	MaxSize	一个 int	简单
增加 tag	MaxSize	一个 int	略复杂

手算示例 ▾

示例一：判断队满和队空

$MaxSize=6$，当前 $front=2$，$rear=4$，牺牲一个单元方案：

当前长度：$(4 - 2 + 6) \% 6 = 2$
是否队满：$(4 + 1) \% 6 = 5 \neq 2$，未满
能否再入队：可以，入队后 rear 变为 5
再入队 2 次后：$rear=(5+1)\%6=0$，再三入 $rear=1$
此时判满：$(1+1)\%6=2=front$，队满

示例二：求队列长度

$MaxSize=8$，$front=5$，$rear=2$ → 长度 $(2 - 5 + 8) \% 8 = 5$。验证：位置 5,6,7,0,1 共 5 个元素 ✓

示例三：操作序列模拟

$MaxSize=6$，初始 $front=rear=0$，执行：入队 1,2,3 → 出队 → 入队 4,5 → 出队 → 入队 6

操作	front	rear	长度	队列内容
初始	0	0	0	空
入1	0	1	1	[1]
入2	0	2	2	[1,2]
入3	0	3	3	[1,2,3]
出队	1	3	2	[2,3]
入4	1	4	3	[2,3,4]
入5	1	5	4	[2,3,4,5]
出队	2	5	3	[3,4,5]
入6	2	0	4	[3,4,5,6]

判满：$(0+1)\%6=1 \neq 2$，未满。

常见考法 ▾

题型一已知 MaxSize、front、rear 求队列长度（公式 $(rear-front+MaxSize)\%MaxSize$）。

题型二给定条件判断是否队满、队空。

题型三执行一系列入队出队，画出最终状态。

题型四 · 容量牺牲一个单元方案中，MaxSize 为 n 的循环队列最多存 n-1 个元素。

易错点 ▾

易错清单

队满和队空条件容易混淆：队空 $front==rear$；队满 $(rear+1)\%MaxSize==front$。
求长度公式必须加 MaxSize：防止 $rear < front$ 时出现负数。
是 %MaxSize 不是 %(MaxSize-1)：数组下标范围是 0 到 MaxSize-1。
rear 指向空位置还是有数据：通常约定 rear 指向下一个空位置。
初始 front=rear=0：不是 $front=0, rear=-1$。

核心结论 ▾

条件	牺牲一个单元	增加 size	增加 tag
队空	$front==rear$	$size==0$	$front==rear$ 且 $tag==0$
队满	$(rear+1)\%M==front$	$size==MaxSize$	$front==rear$ 且 $tag==1$
长度	$(rear-front+M)\%M$	$size$	$(rear-front+M)\%M$

最重要公式长度 = $(rear - front + MaxSize) \% MaxSize$；判满 = $(rear + 1) \% MaxSize == front$（牺牲一个单元方案）。

记忆卡片 ▾

为什么会有"假溢出"？

普通顺序队列 rear 到末尾无法再入队，即使前面有空位。循环队列首尾相连解决。

牺牲一个单元的队空/队满？

队空 front==rear；队满 (rear+1)%MaxSize==front。

长度公式为何加 MaxSize？

防止 rear<front 时出现负数，保证结果为正。

tag 方案怎么区分？

front==rear 时看 tag：tag==0（删）队空，tag==1（插）队满。

交互动画 · 环形队列判满与求长 ▾

初始：front=0, rear=0，队列为空

点击「入队 6」把值放入 rear 指向位置并后移 rear；「判满」「求长度」即时计算

每次操作后 front、rear 沿环顺时针移动；牺牲一个单元：最多存 MaxSize-1=5 个。

核心概念 ▾

为什么要用循环队列

循环队列的实现

方案一 · 牺牲一个存储单元 ▾

方案二 · 增加 size 变量 ▾

方案三 · 增加 tag 变量 ▾

关键性质 ▾

取模运算

手算示例 ▾

示例一：判断队满和队空

示例二：求队列长度

示例三：操作序列模拟

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 环形队列判满与求长 ▾

相关知识点