C语言循环队列

林峰
C语言进阶
7小时前
16热度
0评论

循环队列（Circular Queue / Ring Buffer）

1. 定义

循环队列是基于定长数组实现的队列。其核心思想是将数组视为首尾相接的环形空间，通过让 front / rear 用 % N 循环移动复用存储单元。

在嵌入式系统中，循环队列常称为 Ring Buffer（环形缓冲区），常用于：UART 接收缓冲、按键事件、日志缓存。。

2. 为什么需要循环队列

顺序队列若采用数组实现，出队后数组前部会产生空闲单元。
这些空闲单元虽然可以通过整体搬移数据重新利用，但该方法会引入额外的数据移动开销，难以保持入队、出队操作的稳定 O(1) 复杂度。

循环队列的目的，是在不搬移数据的前提下复用已释放的数组空间。

3. 基本表示

设数组长度为 N。

front：指向当前队头元素
rear：指向下一个可写入位置

下标前进采用模运算（下标到达数组末尾后重新回到下标 0）：

rear  = (rear + 1) % N;
front = (front + 1) % N;

4. 判空与判满

循环队列必须解决一个核心问题：如何区分“空”和“满”。

原因在于，若仅使用 front 和 rear 两个下标，则在某些实现中：

front == rear

既可能表示队列为空，也可能表示队列已满。

因此，循环队列在实现时必须额外规定一种判满策略，从而消除歧义。

4.1 几种常见判定方案对比

方案	额外状态	判空条件	判满条件	是否可用满全部空间	特点
牺牲一个存储单元	无	`front == rear`	`(rear + 1) % CQ_SIZE == front`	否	实现最简单，最常用
`count` 计数法	`count`	`count == 0`	`count == CQ_SIZE`	是	语义直观，但需维护计数
`full` 标志位法	`full`	`front == rear && full == false`	`front == rear && full == true`	是	可用满空间，但状态维护较复杂

4.2 牺牲一个存储单元（最常用）

该方案不引入额外状态变量，而是约定：当 rear 再前进一步就会追上 front 时，判定队列已满。

之所以称为“牺牲一个存储单元”，是因为为了让“空”和“满”能够被区分，必须始终预留一个位置不用。也就是说，长度为 CQ_SIZE 的数组，最大只能存储 CQ_SIZE - 1 个元素。

判空函数：

int cq_is_empty(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return 1;
    }

    return pQueue->front == pQueue->rear;
}

判满函数：

int cq_is_full(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return 0;
    }

    return (pQueue->rear + 1) % CQ_SIZE == pQueue->front;
}

4.3 `count` 计数法

该方法在结构体中额外增加一个计数器 count：

#define CQ_SIZE 8

typedef int CQDataType;

typedef struct
{
    CQDataType buf[CQ_SIZE];
    int front;
    int rear;
    int count;
} CircularQueue;

判空：count == 0
判满：count == CQ_SIZE

优点是可用满全部空间；缺点是每次入队、出队都需要同步维护 count。

4.4 `full` 标志位法

该方法在结构体中额外增加一个标志位 full：

#include <stdbool.h>

#define CQ_SIZE 8

typedef int CQDataType;

typedef struct
{
    CQDataType buf[CQ_SIZE];
    int        front;
    int        rear;
    bool       full;
} CircularQueue;

空：front == rear && full == false
满：front == rear && full == true

该方案也可用满全部空间，但状态维护相对更复杂。

5. 标准实现

以下采用“牺牲一个存储单元”方案。为便于与实际工程代码对应，下面给出与头文件 / 源文件风格一致的一组实现。

#define CQ_SIZE 8

typedef int CQDataType;

typedef struct
{
    CQDataType buf[CQ_SIZE];
    int front;   // 队头元素位置
    int rear;    // 下一个可写位置
} CircularQueue;

void cq_init(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return;
    }

    pQueue->front = 0;
    pQueue->rear = 0;
}

int cq_is_empty(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return 1;
    }

    return pQueue->front == pQueue->rear;
}

int cq_is_full(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return 0;
    }

    return (pQueue->rear + 1) % CQ_SIZE == pQueue->front;
}

int cq_enqueue(CircularQueue *pQueue, CQDataType data)
{
    if (pQueue == 0 || cq_is_full(pQueue)) {
        return 0;
    }

    pQueue->buf[pQueue->rear] = data;
    pQueue->rear = (pQueue->rear + 1) % CQ_SIZE;
    return 1;
}

int cq_dequeue(CircularQueue *pQueue, CQDataType *pData)
{
    if (pQueue == 0 || pData == 0 || cq_is_empty(pQueue)) {
        return 0;
    }

    *pData = pQueue->buf[pQueue->front];
    pQueue->front = (pQueue->front + 1) % CQ_SIZE;
    return 1;
}

6. 长度计算

对于“牺牲一个存储单元”的实现，当前元素个数为：

int cq_size(CircularQueue *pQueue)
{
    if (pQueue == 0) {
        return 0;
    }

    return (pQueue->rear + CQ_SIZE - pQueue->front) % CQ_SIZE;
}

其中先加上 CQ_SIZE，是为了避免 rear < front 时出现负值。

7. 逻辑顺序与物理顺序

循环队列中，数组的物理存储顺序与队列的逻辑顺序可能不同。

例如：

数组下标: 0 1 2 3 4 5
front = 4, rear = 1

则逻辑上的队列顺序为：

4 -> 5 -> 0

因此，遍历循环队列时应从 front 出发，按逻辑顺序访问，而不能直接按数组下标线性理解。

8. 时间复杂度

在不考虑扩容的前提下：

入队：O(1)
出队：O(1)
取队头：O(1)

这也是循环队列相比“搬移数组数据”的主要优势。

9. 嵌入式中的典型应用

循环队列特别适合以下场景：

串口接收缓冲区
日志缓存
按键事件队列
生产者-消费者模型
流式数据缓存

典型用法：

中断服务程序写入数据
主循环读取并处理数据

因此，很多 UART 驱动的接收缓存本质上就是循环队列。

10. 注意点

下标移动必须使用模运算，例如：pQueue->rear = (pQueue->rear + 1) % CQ_SIZE;
本文约定：front 指向队头元素，rear 指向下一个可写位置；若定义改变，相关公式也要随之调整。
若采用“牺牲一个存储单元”方案，则长度为 N 的数组最多只能存储 N - 1 个元素。
循环队列可能发生回绕，访问顺序应从 front 出发按逻辑顺序理解，而不是按数组物理下标顺序理解。

11. 字节缓冲区模板

#include <stdint.h>

#define RB_SIZE 64

typedef struct
{
    uint8_t           buf[RB_SIZE];
    volatile uint16_t front;
    volatile uint16_t rear;
} RingBuffer;

若该缓冲区同时被中断和主循环访问，还需进一步考虑：