C / C++ / 系统课时
用数组实现循环队列
用数组实现循环队列
直接用数组保存队列时,如果 front 和 rear 只向右移动,数组前部即使已经空出来,也可能因为 rear 到达末尾而无法继续入队。循环队列通过取模让下标回到数组开头,从而重复利用这些空闲位置。
学习目标
- 使用
front、rear和取模运算维护循环队列 - 理解预留一个数组位置时空队列与满队列的判断条件
- 能实现并验证循环队列的入队、出队和下标回绕
普通数组队列为什么会假溢出
假设数组长度为 5,元素不断从队尾写入,rear 最终会走到数组末端。与此同时,多次出队可能已经让数组前面的槽位变为空闲。如果实现只允许 rear 继续向右移动,这些空位就无法再次使用,看起来像“数组已满”,实际上仍存在可用空间,这就是常说的假溢出。
循环队列不搬动已有元素,而是把数组下标视为首尾相接。当下标到达最后一个槽位后,再前进一步就回到 0。

用取模完成下标回绕
设数组容量为 CAPACITY,每次移动下标都使用 (index + 1) % CAPACITY。当 index 尚未到末尾时结果等于普通的加一;当 index 等于 CAPACITY - 1 时,加一后取模得到 0,于是下标重新回到数组开头。
为了让空和满能够只通过两个下标判断,这里采用一个常见约定:front 指向队头元素,rear 指向下一次入队要写入的位置,并永久预留一个数组槽位。因此数组长度为 5 时,最多实际保存 4 个元素。
空队列条件是 front == rear,满队列条件是 (rear + 1) % CAPACITY == front。预留一个槽位后,这两个状态不会产生歧义。
完整实现
下面的 C 程序实现整数循环队列,并特意执行“先出队、再继续入队”,以验证数组前部的槽位确实能够被重新使用。
#include <stdbool.h>
#include <stdio.h>
#define CAPACITY 5
typedef struct {
int data[CAPACITY];
size_t front;
size_t rear;
} Queue;
bool queue_is_empty(const Queue *queue) {
return queue->front == queue->rear;
}
bool queue_is_full(const Queue *queue) {
return (queue->rear + 1) % CAPACITY == queue->front;
}
bool enqueue(Queue *queue, int value) {
if (queue_is_full(queue)) {
return false;
}
queue->data[queue->rear] = value;
queue->rear = (queue->rear + 1) % CAPACITY;
return true;
}
bool dequeue(Queue *queue, int *value) {
if (queue_is_empty(queue)) {
return false;
}
*value = queue->data[queue->front];
queue->front = (queue->front + 1) % CAPACITY;
return true;
}
int main(void) {
Queue queue = {0};
int value;
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
dequeue(&queue, &value);
printf("dequeue: %d\n", value);
dequeue(&queue, &value);
printf("dequeue: %d\n", value);
// rear 会从数组末端回绕到开头,复用已经空出的槽位。
enqueue(&queue, 40);
enqueue(&queue, 50);
enqueue(&queue, 60);
printf("front=%zu rear=%zu\n", queue.front, queue.rear);
while (dequeue(&queue, &value)) {
printf("%d ", value);
}
printf("\n");
return 0;
}预期输出
dequeue: 10
dequeue: 20
front=2 rear=1
30 40 50 60这里的 rear=1 并不意味着队尾跑到了队头前面,而是说明数组下标已经发生回绕。逻辑上的队列顺序仍然是 30、40、50、60,读取顺序由 front 开始并按取模规则继续。
验证满队列与空队列
在上述约定中,rear 永远指向下一个可写位置。入队前必须先检查满队列,否则新元素可能覆盖尚未出队的数据;出队前必须检查空队列,否则就会读取一个并不存在的队头元素。
循环队列解决了什么问题
循环队列的关键不是把数组真的变成圆形,而是让逻辑位置能够循环使用固定数组空间。入队和出队都只修改一个下标,不需要为了回收前部空位而整体搬移元素,因此两种操作都可以保持常数级开销。
只要实现时统一 front、rear 的含义,并让所有下标移动都遵守同一种取模规则,就可以避免普通顺序数组队列的假溢出,同时保持队列先进先出的访问顺序。