你去商场里吃饭，门口有个牌子写着「当前叫到 23 号」。你拿的是 24 号。这意味着在你前面还有一个人。这就是一个队列。
先排队的人，先被叫到，先入座。后来的人乖乖等着。
这个逻辑太简单了，简单到我们从小就知道。但当我真正去看数据结构里的队列实现时，才发现这个「简单」的背面藏着一个困扰了我很久的问题——普通队列会「假溢出」，而循环队列就是来解决这个问题的。
说实话，这个问题我折腾了两天才彻底想明白。所以我把这篇写成自己被自己教一遍的样子，如果你也在这个地方卡住，希望对你有用。
队列是什么
先说清楚队列这个东西。
队列，Queue，就是一种「先进先出」的数据结构。你可以把它理解成一排人排队买东西，第一个人买完走了，第二个人补上去。
它支持两个核心操作：
- 入队（Enqueue）：从队尾加入一个元素
- 出队（Dequeue）：从队头取出一个元素
还有一个辅助操作叫判空，判断队列里还有没有东西。
这大概就是队列的全部了。三个操作，别想复杂。
在实际场景里，队列用得非常多。比如 CPU 调度任务、打印机任务排队、宽度优先搜索（BFS）遍历图、消息队列解耦系统——这些背后都是队列。但理解这些应用场景是之后的事，先把队列本身搞清楚。
普通顺序队列的问题
好，现在我用数组来实现一个队列。
数组是连续的内存空间。假设我开一个 MAXSIZE = 5 的数组，用两个指针来标记位置：
front指向队头（第一个元素所在位置）rear指向队尾（下一个可以入队的位置）
一开始，front = 0，rear = 0，队列是空的。
入队三个元素 A、B、C 之后，数组里是这样的：
下标: 0 1 2 3 4
数组: [ A ] [ B ] [ C ] [空] [空]
↑ ↑
front rear
现在出队一次，A 被取走了。通常的实现会怎么做呢？
不迁移数据，只是把 front 往前挪一位：
下标: 0 1 2 3 4
数组: [ A ] [ B ] [ C ] [空] [空]
↑ ↑
front rear
现在 B 和 C 在数组前面了，index=0 是空的，但 rear 已经指到 3 了。
继续入队 D、E：
下标: 0 1 2 3 4
数组: [空] [ B ] [ C ] [ D ] [ E ]
↑ ↑
front rear
再入队一个 F 呢？rear 要变成 5，但数组最大下标是 4——
溢出报警。但数组里明明还有位置（index=0 是空的）。
这就是「假溢出」。队列逻辑上还有空间，但物理上已经没有位置可用了，因为 rear 已经走到了数组尽头。这种情况在频繁入队出队的场景下会不断发生。
你可能会说，那就把所有数据往前搬移一下不就好了？
确实可以，但这就意味着每次出队都要 O(n) 的数据迁移。队列本来想做到 O(1) 的入队出队，这么一搞效率直接掉下去。不可行。
循环队列：首尾相接的思路
假溢出的根本原因是 rear 只能往前走，不能「回头」。
那如果我把数组的最后一个位置和第一个位置接起来呢？
就像一个甜甜圈，数据沿着环形走，走到末尾就绕回开头。这就是循环队列的核心思想。
怎么实现？用模运算。
rear = (rear + 1) % MAXSIZE;
(rear + 1) % MAXSIZE 这个式子保证了 rear 走到末尾之后，会绕回 0。
比如 MAXSIZE = 5，rear = 4 时执行这个操作：
(4 + 1) % 5 = 0，rear 就回到了开头位置。
同样 front 的移动也是这个公式：
front = (front + 1) % MAXSIZE;
循环队列里，数组变成了一个环。rear 可以一直往前走，走完了就从头再来。这样只要数组没真正满，就不会有假溢出。
但问题来了——
空和满，这是最烧脑的地方
循环队列里有一个设计难点，正是因为这个「环形 wrap around」的特性而产生的。
当我们把数组首尾相接之后，front 和 rear 都用「下一个可用的位置」来定义。这意味着初始化时，front == rear 表示空队列没有任何问题。
但当队列满了之后呢？
想象一下，数组长度 5，满员时存了 4 个元素（后面会解释为什么是 4 个不是 5 个）。此时 front 和 rear 会指向同一个位置——因为 rear 绕回来了，刚好和 front 重合。
所以在循环队列里，front == rear 既表示空，也表示满。
这就是循环队列最绕的地方。一种状态，两种含义，靠什么区分？
有三种主流方案。
方案一：牺牲一个存储空间
这是教科书最常见的做法。
核心思路：数组有 n 个位置，但实际只用 n-1 个。那个空出来的位置就是「满」的标志。
满的判断条件是：
(rear + 1) % n == front
空的判断条件还是：
front == rear
为什么这样设计？
数学上，n 个存储位置只能区分 n 种状态（每个位置可以是空或被占用，这是组合数问题）。但队列有 n+1 种状态（0 个元素、1 个元素、……、n 个元素）。n 种状态塞不下 n+1 种情况，所以必须牺牲一种。
牺牲哪一种呢？牺牲「存满 n 个元素」这个状态，只存最多 n-1 个。这样空和满就能明确区分了。
方案二：用一个计数器记录当前元素个数
这个更直观，我更推荐在实际代码里用。
结构体里加一个 size 字段：
typedef struct {
int data[MAXSIZE];
int front;
int rear;
int size; // 当前元素个数
} CircleQueue;
判空：size == 0
判满：size == MAXSIZE
这样 front 和 rear 相等时到底表示空还是满，完全由 size 来判断，不会混淆。而且数组的每个位置都能用上，容量是满的 n。
方案三：标志位 tag
每次入队把 tag 设成 1，每次出队把 tag 设成 0。
然后通过 front == rear 时的 tag 值来区分——如果 tag==0 说明刚出队导致的 front==rear，所以是空；tag==1 说明刚入队导致的，所以是满。
这个方案理论上可行，但用额外的变量增加了复杂度，面试提一下就行，实际代码不推荐。
完整代码实现
说了这么多，不如直接看代码。我用「方案二」（计数器法）写一个完整的循环队列，代码可以直接编译运行。
结构体定义
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
typedef struct {
int data[MAXSIZE];
int front; // 队头下标，指向第一个元素
int rear; // 队尾下标，指向最后一个元素的下一位置
int size; // 当前元素个数
} CircleQueue;
注意 rear 的语义——它指向「下一个可以入队的位置」，而不是最后一个元素本身。这个设计让入队操作 data[rear] = x; rear = (rear + 1) % n; 变得很自然。
初始化
CircleQueue* init() {
CircleQueue* q = (CircleQueue*)malloc(sizeof(CircleQueue));
q->front = 0;
q->rear = 0;
q->size = 0;
return q;
}
入队
int enqueue(CircleQueue* q, int x) {
if (q->size == MAXSIZE) {
printf("队满，无法入队 %d\n", x);
return -1;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % MAXSIZE; // 循环移动
q->size++;
return 0;
}
出队
int dequeue(CircleQueue* q, int* x) {
if (q->size == 0) {
printf("队空，无法出队\n");
return -1;
}
*x = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE; // 循环移动
q->size--;
return 0;
}
打印队列状态（调试用）
void printQueue(CircleQueue* q) {
printf("front=%d, rear=%d, size=%d | ", q->front, q->rear, q->size);
if (q->size == 0) {
printf("[空队列]\n");
return;
}
printf("内容: [");
int count = q->size;
int idx = q->front;
while (count > 0) {
printf("%d", q->data[idx]);
count--;
if (count > 0) printf(" -> ");
idx = (idx + 1) % MAXSIZE;
}
printf("]\n");
}
完整运行示例
int main() {
CircleQueue* q = init();
enqueue(q, 10); printQueue(q); // 入队 10
enqueue(q, 20); printQueue(q); // 入队 20
enqueue(q, 30); printQueue(q); // 入队 30
int x;
dequeue(q, &x); printQueue(q); // 出队一个
printf("出队的元素是: %d\n", x);
enqueue(q, 40); printQueue(q); // 入队 40
enqueue(q, 50); printQueue(q); // 入队 50
enqueue(q, 60); printQueue(q); // 入队 60（会失败，因为队满）
// 再继续入队出队，看循环效果
dequeue(q, &x);
enqueue(q, 70); printQueue(q);
dequeue(q, &x);
enqueue(q, 80); printQueue(q);
free(q);
return 0;
}
输出：
front=0, rear=1, size=1 | 内容: [10]
front=0, rear=2, size=2 | 内容: [10 -> 20]
front=0, rear=3, size=3 | 内容: [10 -> 20 -> 30]
front=1, rear=3, size=2 | 内容: [20 -> 30]
出队的元素是: 10
front=1, rear=4, size=3 | 内容: [20 -> 30 -> 40]
front=1, rear=0, size=4 | 内容: [20 -> 30 -> 40 -> 50]
队满，无法入队 60
front=2, rear=0, size=3 | 内容: [30 -> 40 -> 50]
front=2, rear=1, size=4 | 内容: [30 -> 40 -> 50 -> 70]
front=3, rear=1, size=3 | 内容: [40 -> 50 -> 70]
front=3, rear=2, size=4 | 内容: [40 -> 50 -> 70 -> 80]
注意看 rear 的移动。当 rear 从 4 再入队一个元素时，它绕回了 0，而不是溢出。这就是循环队列的核心价值——空间可以复用。
链表实现：另一种思路
数组实现的队列有容量限制。如果你需要动态扩容、不确定容量上限的场景，可以用链表来实现队列。
思路很简单：每个节点存数据和指向下一个节点的指针，维护 head 和 tail 两个指针。
入队就是在链表尾部插入，出队就是从链表头部删除。两个操作都是 O(1)，不需要循环移位。
但链表实现的代价是每个节点要额外存储一个指针，空间开销比数组大，而且每次入队要 malloc、出队要 free，有额外的系统调用开销。如果队列大小可以预估，循环队列是更高效的选择。
什么时候用什么
说了这么多，最后来一个简单的选择指南。
| 场景 | 推荐 | 原因 |
|---|---|---|
| 大小固定，数据量可预估 | 循环队列（数组） | 无需 malloc/free，运行效率高 |
| 大小不确定，可能很大 | 链式队列 | 按需分配，不浪费空间 |
| 频繁入队出队，实时系统 | 循环队列（数组） | 入队出队都是 O(1)，无内存碎片 |
| 需要遍历查看队列内容 | 循环队列（数组） | 随机访问，调试方便 |
| 需要严格的最大容量 | 循环队列（数组） | 容量固定，不会意外失控 |
其实大多数场景下，循环队列（数组实现）就是最优选。代码简单、效率高、没有内存碎片。只有在真正需要动态扩容时才考虑链表版本。
回到开头的场景
现在你再去商场吃饭，门口那个叫号牌是怎么工作的？
叫号系统维护一个「当前叫到的号码」和一个「下一个可分配的号码」，每次有人入座，当前号码就往前挪一位——这就是出队操作。系统里叫号系统和你的号码之间的排队关系就是一个队列。每新来一个人，就排到当前最大号的后面。
数据结构从来不是凭空发明的东西，它就是把生活中已经存在的逻辑，用精确的语言描述出来。
循环队列就是这样——把排队这个动作里「有人走了位置空出来，后面的人可以补上」的朴素想法，变成了一个可以跑在计算机里的数据结构。
理解了这一点，「假溢出」这个问题就再也困不住你了。