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 程序实现整数循环队列,并特意执行“先出队、再继续入队”,以验证数组前部的槽位确实能够被重新使用。

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;
}

预期输出

text
dequeue: 10
dequeue: 20
front=2 rear=1
30 40 50 60

这里的 rear=1 并不意味着队尾跑到了队头前面,而是说明数组下标已经发生回绕。逻辑上的队列顺序仍然是 30、40、50、60,读取顺序由 front 开始并按取模规则继续。

验证满队列与空队列

在上述约定中,rear 永远指向下一个可写位置。入队前必须先检查满队列,否则新元素可能覆盖尚未出队的数据;出队前必须检查空队列,否则就会读取一个并不存在的队头元素。

循环队列解决了什么问题

循环队列的关键不是把数组真的变成圆形,而是让逻辑位置能够循环使用固定数组空间。入队和出队都只修改一个下标,不需要为了回收前部空位而整体搬移元素,因此两种操作都可以保持常数级开销。

只要实现时统一 front、rear 的含义,并让所有下标移动都遵守同一种取模规则,就可以避免普通顺序数组队列的假溢出,同时保持队列先进先出的访问顺序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用数组实现循环队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通