12、循环队列：循环队列的设计思想、循环队列的入队与出队、循环队列的判空与判满
队列这东西，说白了就是个「先来后到」的排队机制。你想想看，食堂打饭、银行取号，谁先来谁先走，这就是队列。
但有个问题——如果用数组实现普通队列，你会发现一个尴尬的现象：队头出队后，前面的位置就空着了，后面的元素不断往后挪，最后数组尾部满了，前面却空着一大片。嗯，这就是「假溢出」。
我早年做嵌入式项目时就被这个坑过。一个数据采集模块，跑着跑着就报队列满了，一查才发现前面空着几十个位置没用上。后来我改用循环队列，问题就解决了。
循环队列的设计思想
循环队列的核心思想很简单：把数组的头尾连起来，形成一个环。队头出队时，头指针往前走；队尾入队时，尾指针也往前走。走到数组末尾了怎么办？绕回到开头继续走。
就像操场上的环形跑道，没有终点，只有一圈又一圈。
具体实现时，我们维护两个指针：
- front：指向队头元素的位置
- rear：指向队尾元素的下一个位置（也就是下一个要入队的位置）
入队时，rear 往前走一步；出队时，front 往前走一步。两个指针都在数组范围内循环移动。
关键公式：
指针前进：(rear + 1) % MAX_SIZE
指针前进：(front + 1) % MAX_SIZE
取模运算保证了指针在 0 ~ MAX_SIZE-1 之间循环。
我个人习惯把 MAX_SIZE 定义为 2 的幂次方，比如 64、128、256。这样取模运算可以用位运算替代，效率更高——嵌入式设备上，少一条指令就是少一个时钟周期。
循环队列的入队与出队
先看入队操作。入队前要判断队列是否已满，没满才能往里放。
// 循环队列入队
int enqueue(CircularQueue *q, int data) {
// 判满：下一个位置就是 front，说明满了
if ((q->rear + 1) % MAX_SIZE == q->front) {
return -1; // 队列已满
}
q->buffer[q->rear] = data;
q->rear = (q->rear + 1) % MAX_SIZE;
return 0; // 入队成功
}出队操作类似，先判空，再取数据。
// 循环队列出队
int dequeue(CircularQueue *q, int *data) {
// 判空：front == rear 表示空
if (q->front == q->rear) {
return -1; // 队列为空
}
*data = q->buffer[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return 0; // 出队成功
}这里有个细节：入队时 rear 指向的是下一个空位，出队时 front 指向的是当前队头。我刚开始学的时候总搞混，后来画了几次图就记住了。
小技巧：如果你觉得取模运算看着别扭，可以这样理解——每次指针加 1 后，如果等于 MAX_SIZE，就重置为 0。用 if 判断也行，但取模更简洁。
循环队列的判空与判满
这是循环队列最微妙的地方。因为 front 和 rear 都在循环移动，怎么区分「空」和「满」？
你看，如果队列为空，front == rear。如果队列满了，rear 再往前走一步就追上 front 了，也就是 (rear + 1) % MAX_SIZE == front。
但问题来了——空和满的时候，front 和 rear 都指向同一个位置吗？不是的。空的时候 front == rear，满的时候 rear 在 front 的前一个位置（循环意义上的前一个）。
所以循环队列实际上浪费了一个存储空间，用来区分空和满。MAX_SIZE 的数组，最多只能存 MAX_SIZE - 1 个元素。
判空条件：front == rear
判满条件：(rear + 1) % MAX_SIZE == front
元素个数：(rear - front + MAX_SIZE) % MAX_SIZE
我曾经在一个通信协议栈里用过循环队列，当时 MAX_SIZE 设的是 256，实际只能存 255 个包。有人问我为什么不设成 257？嗯，因为 256 是 2 的 8 次方，取模可以用 & 0xFF 替代，快很多。
// 用位运算替代取模（MAX_SIZE 必须是 2 的幂次方）
#define MAX_SIZE 256
#define MASK (MAX_SIZE - 1)
// 入队
q->buffer[q->rear] = data;
q->rear = (q->rear + 1) & MASK;
// 出队
*data = q->buffer[q->front];
q->front = (q->front + 1) & MASK;
// 判满
if (((q->rear + 1) & MASK) == q->front) {
// 队列已满
}注意：位运算技巧只适用于 MAX_SIZE 是 2 的幂次方的情况。如果你用 100、200 这种数字，老老实实用取模 % 吧，别乱用位运算，否则 bug 找都找不到。
还有一种实现方式是不浪费空间，加一个 count 变量记录元素个数。判空看 count == 0，判满看 count == MAX_SIZE。这样空间利用率 100%，但多了一个变量需要维护。
| 实现方式 | 空间利用率 | 判空/判满速度 | 适用场景 |
|---|---|---|---|
| 浪费一个空间 | (MAX_SIZE-1)/MAX_SIZE | 极快（一次比较） | 嵌入式、实时系统 |
| 加 count 变量 | 100% | 快（一次比较） | 通用场景 |
我个人更倾向于浪费一个空间的做法。为什么？因为嵌入式系统里，多一个变量就多一份出错的可能。而且 256 个元素用 255 个，损失可以忽略不计。
好了，循环队列的核心就这些。设计思想是「化直为环」，入队出队就是指针转圈，判空判满靠 front 和 rear 的关系。你写代码的时候，记得把边界条件想清楚——尤其是队列满的时候，千万别把数据覆盖了。