名称：Doubletful的博客 💠数据结构专栏 签名：路漫漫其修远兮，吾将上下而求索

---

前言

为什么需要环形缓冲器（环形队列）？
——当我们使用普通数组来实现队列时，会面临多个严重的问题，而当使用链表实现时，会有额外的空间开销，并且缓存命中率低。
先看队列概论：
队列（Queue）是一种常见的数据结构，遵循先进先出（FIFO） 的原则——最早进入队列的元素将最先被移除。队列在计算机科学中有广泛的应用，比如任务调度、网络流量控制、打印任务管理等（记住这些定义，我们将立刻解析使用数组实现队列的天然问题）

一、普通数组实现队列问题

1.假溢出

不移动元素实现的情况下：
以低下标位作为队头，无法避免每次出队后队头指针后移导致指针前的数组空间被浪费的情况。以高下标位作为队头，无法避免随着不断出队，导致队尾指针前的数组空间被浪费的情况。
⌈明明数组前面还有空闲空间，却无法使用——这就是所谓的 “假溢出” 问题⌋

2.数据搬移代价高昂

一种直观的解决方案是：每次出队后，将后面的所有元素整体前移。但这意味着每次出队操作的时间复杂度都变成O(n)，对于频繁操作来说是不可接受的，性能将急剧下降。

3.扩容与提前扩容的连锁反应

如果队列真的满了，我们可能需要扩容（创建一个更大的数组并复制数据）。但假溢出现象会导致提前扩容：明明还有空闲空间，却因为指针无法回绕而被迫扩容，这进一步放大了性能开销和内存占用。
试想一下：一个网络数据包缓冲队列，每秒处理数万个包，如果每次出队都要搬移数据或频繁扩容，系统性能将不堪重负。

二、环形队列的核心思想

将数组的尾部与首部连接起来，形成一个逻辑上的环。
💡 关键点：数组在物理上仍然是线性的，但通过取模运算（modulo） 在逻辑上实现了循环。
🪄当指针移动到数组末尾时，通过取模运算让它“绕回”到数组开头，从而复用之前释放的空间。

三、头尾指针定义与关键约定

实现环形队列，需要明确两个指针的定义：

指针	定义	初始值
front	指向队列中的第一个有效元素	0
rear	指向队列中最后一个有效元素的下一位	0

为什么要让 rear 指向队尾的下一位？
为区分判空与判满重叠的问题，请继续阅读。

约定：牺牲一个存储单元

当队列为空时，判断条件为 front == rear，而当数组中存满元素，rear 通过回绕最终会回到 front 的位置（rear指向下一次入队位置），此时同样满足条件，若判满仍使用 front == rear，则会出现判断不明确的问题。
环形缓冲器逻辑图例：

解决方式：
设数组申请了 n 个空间，那我们最多存储 n - 1 个值，刻意空出一个位置，使判满条件变成 front == rear + 1（注意此为逻辑层，实际需取模）。
为什么判满条件为 front == rear + 1?
答：rear 指向最后一个有效元素的下一位，当大小为 n 的数组中已有 n - 1 个值时，还剩下一个空位，此时队列已满，不能再插入新元素，若 rear 再加一就会追上 front（rear 指向那个空位），因此能判满。
环形缓冲器逻辑图例：

四、代码实现

1.结构搭建

typedef struct {
	int* arr; #存储数据的数组
	int front; #队头指针
	int rear; #队尾指针
	int k; #实际容量
} MyCircularQueue;

利用结构体实现环形缓冲器，并在其中存储队列信息，结构体命名方式利用了匿名结构体的特性，直接改名为 MyCircularQueue。

2.初始化

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));
    obj->arr = malloc(sizeof(int) * (k + 1));
    obj->front = obj->rear = 0;
    obj->k = k;
    return obj;
}

形参k为环形缓冲器中的实际存储量，因此在开辟数组时多开一个单元，将头尾指针初始化为0，从数组开头循环，并将k设置为实际存储量。
注：k也可初始化为数组的容量 n，这里初始化为 n - 1。

3.检查缓冲器是否为空

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

按照之前的逻辑判断即可，空返回 true，非空返回 false。

4.检查缓冲器是否已满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->k + 1) == obj->front;
}

我们之前讨论过，当前 rear 的位置加一如果是 front，则已满，取模原本数组的容量，即为 k + 1。
注：特殊情况需利用模运算保证指针的循环访问，否则会越界。

5.入队

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
        return false;
    obj->arr[obj->rear] = value;
    obj->rear = (obj->rear + 1) % (obj->k + 1);
    return true;
}

先检查当前队列中是否已满，如果已满返回 false 代表操作失败，未满让新值入队在队尾并让 rear + 1，最后返回 true 代表操作成功。

6.出队

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return false;
    obj->front = (obj->front + 1) % (obj->k + 1);
    return true;
}

先检查当前队列中是否为空，如果为空返回 false 代表操作失败，未满从队头出队并让 front + 1（注意需取模避免越界），最后返回 true 代表操作成功。

7.获取队头元素

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}

直接利用 front 指针找到队头元素即可。当队列为空时返回任意一个不存在于规定的存储集合中的元素，代表查找元素不存在。

8.获取队尾元素

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[(obj->rear + obj->k) % (obj->k + 1)];
}

判断与返回值操作同上，特殊情况为当 rear 指向 0 时，rear - 1 会越界访问，所以需做取模运算，使 rear 回转到数组末尾的位置（循环操作是双向的）。这段取模运算并不是很直观，解释如下：
拆解分析：先将原式省略的部分还原为——→(rear - 1 + k + 1) % (k + 1)，
rear - 1 为执行的原始操作，取模操作为 + k + 1) % (k + 1) 部分。
分为两种情况：
当 rear 等于 0 时，为特殊情况，化简后操作相当于 k % (k + 1)，其结果必然为 k，而 k 是实际存储量，亦为数组中的最后一个下标位。
当 rear 大于 0 时，为正常的减一找尾元素操作，化简为 (rear + k) % (k + 1)，相当于 rear 先加 k 再减 k + 1，刚好减一。

9.销毁环形缓冲器

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    obj->arr = NULL;
    obj->front = obj->rear = obj->k = 0;
    free(obj);
}

释放结构体内数组开辟的空间，将指针与属性初始化后，释放结构体本身开辟的空间。不做指针与属性初始化操作不影响功能，但销毁顺序绝不能更改。

五、实际应用场景

1. 操作系统中的键盘/鼠标输入缓冲：当用户敲击键盘时，按键事件被放入环形队列，中断处理程序从队列中取出事件，保证事件有序处理。
2. 串口通信（UART） ：串口接收数据时，硬件将数据写入环形缓冲区，CPU从缓冲区读取，避免数据覆盖。
3. 网络协议栈的接收/发送缓冲区：例如网卡驱动中的环形描述符队列。
4. 音频/视频播放器：播放器从网络或文件中读取数据填入环形缓冲区，解码线程从中取出数据，平滑播放。
5. 日志系统：循环覆盖旧的日志条目，保留最新的N条记录。
6. 线程池的任务队列：工作线程从环形缓冲器中拉取任务，生产线程负责往里放任务。

六、为何用数组而非链表实现

环形缓冲器也可以用链表实现，但数组实现具有明显的优势：

• 缓存局部性：数组在内存中连续存储，CPU缓存命中率高，访问速度快。链表的节点分散在堆中，缓存不友好，且每次访问需指针跳转。
• 无内存碎片：数组一次性分配固定大小，不会产生内存碎片，链表频繁增删节点容易导致碎片化。
• 适合底层开发：在嵌入式、操作系统内核等场景中，数组实现的环形缓冲更可控，可提前预分配内存，避免运行时分配失败。

链表实现的唯一优势是无需事先知道最大容量，可以动态扩容。但在绝大多数场景中，环形缓冲器的容量是可预知的（例如缓冲区大小固定），因此数组实现是更优的选择。

七、总结

环形队列通过 “取模回绕” 和 “指针约定” 巧妙地解决了普通数组队列的空间浪费和性能问题。
1、核心机制：front 和 rear 两个指针 + %运算实现循环复用
2、区分空/满：牺牲一个存储单元（或增设 size 字段）
3、时间复杂度：入队和出队均为O(1)
4、空间效率：数组空间循环使用，无“假溢出”
5、实用价值：在操作系统、网络通信、多媒体处理等场景中不可或缺

八、练习

推荐如下LeetCode题目
622. 设计循环队列 & 链接: link.

⚛️EL PSY CONGROO，十分感谢你的阅读

本期不确定：
要写使用链表实现环形缓冲器作为练习吗