循环队列

2026 大纲 三（二）栈和队列的顺序存储结构 · 队列部分（栈的部分见《顺序栈》《共享栈》）。

先有假溢出，才有循环队列

队列用数组实现时，front 和 rear 都只增不减——入队 rear 往后走，出队 front 往后走，两个指针一路向右爬。于是很快就会撞上一件怪事：

设 MaxSize = 6，入队 6 个、出队 3 个、再入队 1 个。

时刻	front	rear	数组占用	说明
初始	0	0	[_ _ _ _ _ _]	空
入队 6 个	0	6	[a b c d e f]	rear 已越过数组末端
出队 3 个	3	6	[_ _ _ d e f]	前 3 格空出来了
再入队 1 个	3	7？	—	data[6] 根本不存在

明明还剩 3 个空单元，却已经写不进去——这叫假溢出：不是空间不够，而是空间在数组的另一头、指针够不着。

分清真假：真溢出是元素个数确实达到了容量；假溢出是元素个数没到容量、但 rear 撞上了数组边界。假溢出是顺序存储 + 单向移动指针这个组合的必然产物，与队列本身无关——栈不会有这个问题，因为栈的两个操作都在同一端，指针会来回移动。

解决办法是把数组首尾相接看成一个环：下标 MaxSize-1 的下一个就是 0。指针移动因此改写成取模：

$$\text{front}=(\text{front}+1)mod\text{MaxSize},\text{rear}=(\text{rear}+1)mod\text{MaxSize}$$

% MaxSize 干了两件事：把下标压进 0..MaxSize-1，以及实现绕回。它等价于 rear++; if (rear == MaxSize) rear = 0;——但只在步长为 1 时等价，跨度大于 1 时那个 if 会漏判。

⚠️ 指针后退必须写成 (x - 1 + MaxSize) % MaxSize。 C 语言的 % 对负被除数返回负余数（-1 % 8 得到 -1，不是 7），直接写 (x-1) % MaxSize 会算出非法下标。

绕回带来的新麻烦：front == rear 到底是空还是满

成环之后立刻冒出一个歧义。设 MaxSize = 8：

• 队空：入队 4 个再出队 4 个，front = rear = 4；
• 队满：从空开始连续入队 8 个，rear 走一圈回到 0，而 front 也是 0，front = rear = 0。

两种完全相反的状态，指针值一模一样。教材的原话是："对于循环队列不能以头、尾指针的值是否相同来判别队列空间是'满'还是'空'。"

出路只有一条：引入额外信息。三种做法：

方案	判空	判满	最多存
一 牺牲一个单元	front == rear	(rear + 1) % MaxSize == front	MaxSize - 1
二 增设 size	size == 0	size == MaxSize	MaxSize
三 增设 tag	front == rear && tag == 0	front == rear && tag == 1	MaxSize

方案一是消除歧义（永远留一个空位，让 front == rear 只可能是空）；方案二三是保留歧义 + 额外信息裁决。

🔴 方案一不是"更省空间"。 三者占的数组都是 MaxSize 个单元。方案一省的是变量（不用多存 size 或 tag），付出的是容量（少存一个元素）。

先看一眼

加载可视化中...

一直入队直到它拒绝，数数里面到底存了几个——按方案一的口径，答案是 MaxSize - 1，有一格永远空着。再出队几个、入队几个，看两个指针怎么绕圈。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.20 循环队列的插入与删除，p116

这张图最值得看的是最后一格：rear 绕回到 0、front 停在 1，两个指针相邻，数组里有 7 个元素、1 个空位——这正是方案一要保留的那个空位。

代码（方案一：牺牲一个存储单元）

默认口径是：front 指队头元素，rear 指下一个入队位置，初始 front = rear = 0。

#define MaxSize 10

typedef struct {
    int data[MaxSize];
    int front, rear;   // rear 指向"下一个入队位置"
} SqQueue;

void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; }

bool QueueEmpty(SqQueue Q) { return Q.front == Q.rear; }

bool QueueFull(SqQueue Q)  { return (Q.rear + 1) % MaxSize == Q.front; }

bool EnQueue(SqQueue *Q, int x) {
    if ((Q->rear + 1) % MaxSize == Q->front)
        return false;                        // 队满，留下的那一格不许用
    Q->data[Q->rear] = x;                    // 先写入 rear 指的空位
    Q->rear = (Q->rear + 1) % MaxSize;       // 再让 rear 前进
    return true;
}

bool DeQueue(SqQueue *Q, int *x) {
    if (Q->front == Q->rear)
        return false;                        // 队空
    *x = Q->data[Q->front];                  // 先取队头元素
    Q->front = (Q->front + 1) % MaxSize;     // 再让 front 前进
    return true;
}

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

判满为什么是 (rear+1) % MaxSize == front：若 rear 的下一格正是队头，说明空闲的只剩 rear 这一格，按约定它不许使用，所以判为满。

⚠️ 队尾元素不在 rear。 rear 指的是空位，队尾元素在 (rear - 1 + MaxSize) % MaxSize。问"队尾元素是哪个"时别顺手答 data[rear]。

元素个数公式也是推出来的。队列占用的下标是 $\text{front},\text{front}+1,\dots ,\text{rear}-1(\mathrm{mod}\text{MaxSize})$，个数就是 $\text{rear}-\text{front}$；但绕回后这个差是负数（MaxSize=8、front=6、rear=2 时差为 $-4$，实际有 4 个），而在环上"负 4"和"正 4"是同一件事，模一下归一化即可：

$$\text{Length}=(\text{rear}-\text{front}+\text{MaxSize})mod\text{MaxSize}$$

代入验证：$(2-6+8)mod8=4$ ✓。这个公式在方案一下恒成立（因为 rear == front 只能是空）；方案二直接读 size；方案三在满队时 rear == front，公式算出 0，必须由 tag 特判。

方案二 size 与方案三 tag 的完整代码（题面要求用满 MaxSize 时展开）

方案二：增设 size 计数器。

typedef struct {
    int data[MaxSize];
    int front, rear;   // rear 仍指向"下一个入队位置"
    int size;          // 当前元素个数
} SqQueue2;

void InitQueue2(SqQueue2 *Q) { Q->front = Q->rear = 0; Q->size = 0; }

bool QueueEmpty2(SqQueue2 Q) { return Q.size == 0; }
bool QueueFull2 (SqQueue2 Q) { return Q.size == MaxSize; }

bool EnQueue2(SqQueue2 *Q, int x) {
    if (Q->size == MaxSize) return false;    // 判满改看 size，与指针无关
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    Q->size++;                               // ← 与方案一的唯一代码差异
    return true;
}

bool DeQueue2(SqQueue2 *Q, int *x) {
    if (Q->size == 0) return false;          // 判空改看 size
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    Q->size--;                               // ← 与方案一的唯一代码差异
    return true;
}

方案三：增设 tag 标志位。 用一位 tag 记录最近一次成功操作是入队还是出队： 入队后置 tag = 1，出队后置 tag = 0。推理依据是只有入队才可能把队列填满， 只有出队才可能把队列清空，所以 front == rear 时看最后一步是什么就能定性。

typedef struct {
    int data[MaxSize];
    int front, rear;
    int tag;           // 0 = 最近一次是出队，1 = 最近一次是入队
} SqQueue3;

void InitQueue3(SqQueue3 *Q) {
    Q->front = Q->rear = 0;
    Q->tag = 0;        // 初始视作"刚出过队"，于是初始状态被判为空
}

bool QueueEmpty3(SqQueue3 Q) { return Q.front == Q.rear && Q.tag == 0; }
bool QueueFull3 (SqQueue3 Q) { return Q.front == Q.rear && Q.tag == 1; }

bool EnQueue3(SqQueue3 *Q, int x) {
    if (Q->front == Q->rear && Q->tag == 1) return false;   // 队满
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    Q->tag = 1;                                             // ← 关键：入队置 1
    return true;
}

bool DeQueue3(SqQueue3 *Q, int *x) {
    if (Q->front == Q->rear && Q->tag == 0) return false;   // 队空
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    Q->tag = 0;                                             // ← 关键：出队置 0
    return true;
}

int QueueLength3(SqQueue3 Q) {
    if (Q.front != Q.rear)
        return (Q.rear - Q.front + MaxSize) % MaxSize;
    return Q.tag == 1 ? MaxSize : 0;                        // 指针相等时靠 tag 定性
}

初值 tag = 0 的理由：初始队列是空的，而判空要求 tag == 0，所以初值只能取 0。 如果初始化成 1，InitQueue 之后队列会被误判成"满"，第一次入队就直接失败—— 这是一个可以立刻自查的边界。

三种方案的指针移动语句完全相同，差别只在判定条件，以及收尾那一句 size++ / tag = 1。

🔴 tag 必须在每次成功操作后都更新，不能只在 front == rear 时才更新——判定发生在下一次操作之前，那时你无法回溯上一步是什么。这是 tag 方案代码题里最常漏写的一处。

换一套约定，公式全部要重推

上面所有公式的前提是"rear 指向下一个入队位置"。题目常把它改成"front 指队头元素，rear 指队尾元素"，此时结论一条都不能照搬。

推法只有一句：先写出"队列占用了哪些下标"，再数格子。 新约定下队列占用 $\text{front}\sim \text{rear}$（含两端），共 $(\text{rear}-\text{front}+1+\text{MaxSize})mod\text{MaxSize}$ 个。于是：

项	rear 指向下一个空位（本篇默认）	rear 指向队尾元素
初始化	front = rear = 0	front = 0, rear = MaxSize - 1
入队	先 data[rear] = x，再 rear = (rear+1)%MaxSize	先 rear = (rear+1)%MaxSize，再 data[rear] = x
出队	先 x = data[front]，再 front 前进	同左
判空（牺牲一单元）	front == rear	(rear + 1) % MaxSize == front
判满（牺牲一单元）	(rear + 1) % MaxSize == front	(rear + 2) % MaxSize == front
元素个数	(rear - front + MaxSize) % MaxSize	(rear - front + 1 + MaxSize) % MaxSize

注意右列的入队是先移指针再写入，与左列相反——道理和顺序栈里"top 指元素就先移后写"完全一样：指针指向有效元素时，写入前必须先腾一格。这条规则还能反过来用：题目若要求"第一个入队的元素必须落在 data[0]"，那么在"rear 指队尾元素"的约定下，rear 的初值就只能是 MaxSize - 1——先 +1 绕回到 0，再写入。

现场做法：不要背右边这一列。看到题面改了约定，就在草稿纸上画一个 MaxSize = 5 的小环，手动入队两三个、出队一个，把"占用哪些下标"标出来，公式自然浮现。现场推一遍不到一分钟，比记四套公式可靠得多。

考点速记

三条会被反复调用的结论：

1. 方案一牺牲一格，换来"front == rear 只可能是空"：容量少 1，但不加字段，且长度公式恒成立。
2. 三种方案的指针移动语句完全一致，差别只在判定条件与收尾的 size++ / tag = 1。
3. 公式全部可推：% MaxSize 解决越界与绕回，+ MaxSize 解决 C 的负余数，都不是记忆项。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：几乎全是"题面自己定一套约定，问初值或判空判满条件"——正因如此，这一篇真正要会的是推导，不是那四条默认公式。

• 给定约定问指针初值：比如"front 与 rear 分别指向队头元素和队尾元素，要求第一个入队的元素存在 A[0]"。既然 rear 指元素，入队就是先移后写，要让首个元素落在下标 0，rear 初值必须是 n-1；front 初值取 0。
• 给定约定问判空判满：题面把两个指针改名（如 end1、end2）、说明各自指哪儿、给出容量上限，四个选项摆出不同的条件组合。做法固定：先写出"占用了哪些下标"，数出元素个数，再令它等于 0 与等于容量上限。
• 顺带留意题面里的"最多容纳 $M-1$ 个"：这句话等于告诉你它用的是牺牲一个单元的方案，判空就该是两指针相等。

易错：把队尾元素当成 data[rear]。 rear 指空位时，队尾元素在 (rear-1+MaxSize)%MaxSize。

易错：指针后退忘了 +MaxSize。 C 的负余数会给出非法下标。

易错：换约定后照搬默认公式。 判空判满、元素个数、入队的先后顺序会同时改变，必须整套重推。

易错：以为方案一比方案二三省空间。 三者的数组都是 MaxSize；方案一省的是变量，赔的是容量。

教材出处

• 队列的顺序存储表示与 front = rear = 0 的约定（非空队列中头指针指向队头元素、 尾指针指向队尾元素的下一个位置）：严蔚敏《数据结构（C 语言版）》（第 2 版）p70 「3.5.2 循环队列——队列的顺序表示和实现」
• 假溢出与"不能以头、尾指针是否相同判别队满队空"，以及两种处理方法 （少用一个元素空间、另设标志位）与队空 Q.front == Q.rear、 队满 (Q.rear + 1) % MAXQSIZE == Q.front：同书 p71
• 求循环队列长度算法 3.12 (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE、 入队算法 3.13、出队算法 3.14：同书 p72
• 若无法预估队列最大长度则宜采用链队：同书 p73
• 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图3.20 循环队列的插入与删除，p116

教材正文只给出两种处理方法（少用一个元素空间、另设标志位）， 本篇的"增设 size 计数器"是同一思路（补充额外信息以消歧）下的第三种常见做法， 在各类题目中同样出现，故并列讲解，但不挂在教材页码之下。

相关知识

栈和队列的基本概念（队列 ADT 与出队序列性质）｜ 链式队列（链式实现，天然没有假溢出）｜ 共享栈（同是"顺序存储怎么判满"，但指针相向移动，因而不必牺牲单元）｜ 双端队列（两端都能进出的推广）｜ 循环链表（靠真实指针接回去的"首尾相连"）｜ 广度优先搜索（队列最主要的使用者）

相关文章

• 栈和队列基本概念
• 顺序栈
• 共享栈
• 链栈
• 链式队列
• 双端队列
• 应用：括号匹配
• 应用：表达式求值
• 应用：栈在递归中的应用
• 多维数组的存储
• 特殊矩阵的压缩存储

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2011Q32分