从零开始打造高性能数据结构——手把手教你实现环形缓冲

在普通线性队列中，即使数组总容量未满，只要队尾到达数组末尾，就会认为“满了”，从而触发不必要的扩容。
例如：容量为 10 的队列，先入队 8 个元素，再出队 6 个，此时只有 2 个元素，但队头在索引 6，队尾在索引 8。
如果再入队 3 个元素，队尾会到索引 11（越界），于是系统认为“满”了，尽管前面有 6 个空位。
这种情况下，明明空间足够，却被迫扩容，浪费内存和性能。

因此，我们引出了环形缓冲——这一全新且高性能的结构来弥补一般队列的不足。

二，环形缓冲结构分析

事实上使用链表实现环形缓冲可行，但是效率较低并且代码繁琐。因此我们采用数组来实现这一命题。

1. “循环”取模实现指针回绕

循环队列的核心思想是：逻辑上将存储结构首尾相连形成环形，通过模运算（% capacity）实现指针回绕。

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

2.“循环”，轮流入座而不是排长队

● 解决了每次pop元素后前面减少一个元素。但是空间被闲置的问题。
● 解决了每次push一个元素需要malloc开辟空间，浪费时间的同时会导致内存碎片化的问题，从而提升缓存命中率。

每一次循环回到起始节点都会利用原本会因front向后移动而浪费掉的空间

即：从无限延申的队列模型到固定座位量的轮流入座。

类比：火车站候车室

想象一排固定数量的座椅：

张三（先入座）→ 李四 → 王二麻（后入座）；
座位满员后，赵五想入座，张三按 FIFO 原则离开；
刘六随后入座，李四离开……

无需增加座椅，只需让空出的位置被新来者复用——这正是环形队列的优势：空间循环利用，无浪费、无移动、无扩容。

三，实现环形缓冲

我们看题目

622. 设计循环队列

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。

1，`MyCircularQueue(k)`: 构造器

1，结构体搭建

typedef struct { int front; int end; int k; int *a; } MyCircularQueue;

● 首先我们需要根据循环队列的结构创建循环队列结构体；

● 我们需要一个front指向第一个数据，一个end指向最后一个数据的下一个结点。

● k表示整体最大容量，达到即满。

● 指针a用于维护开辟给循环队列的空间。

● 重命名结构体MyCircularQueue

2，初始化

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

● 这个结构体种维护的数据应该有地方存储，所有我们malloc一块空间用于存放他们，

● 我们为循环链表开辟一块k+1大小的空间（为什么是k+1而不是k？后面会讲）

● 初始化end和front指针为0；

● 初始化空间大小为k；

3，为什么选择k+1块空间而不是k块空间？

原因：区分“空”与“满”状态。

若数组大小为 k，则 front == end 既可能是空，也可能是满（队尾绕回队头）。
通过牺牲一个存储单元，规定最大容量为 k，数组实际大小为 k+1：
- 空：front == end
- 满：(end + 1) % (k+1) == front

`2，isFull()`: 检查循环队列是否已满。

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

如上图，如果end的下一个结点就是front，那么我们可以确定这个循环队列是满的。否则为非满

`3，isEmpty()`: 检查循环队列是否为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->front==obj->end) { return true; } else { return false; } }

如果front和end指向同一个位置，只有一种情况：空。

`4，enQueue(value)`: 插入数据

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if((obj->end+1)%(obj->k+1)==(obj->front)) { return false; } else { *(obj->a+obj->end)=value; obj->end=(obj->end+1)%(obj->k+1); return true; } }

首先，先判满，如果满了则无法插入数据，返回false。

如果没满插入数据后end向后移动一格。

取模回绕的数学原理：

● 模k+1是整个数组的大小。

● 我们可以将end的每一个数字看做是a+x*（k+1）（其中a∈[0，k]的形式。

● 取模就是去掉后面的x*（k+1），得到下标a。

`5，deQueue()`: 循环队列删除元素。

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

首先判空：如果队列为空，则韩慧false，否则执行删除并返回true。

front指针向后移动一格，注意不要忘记回绕的情况。

`6，Front`: 从队首获取元素。

int myCircularQueueFront(MyCircularQueue* obj) { if(obj->front==obj->end) { return -1; } else { return *(obj->a+obj->front); } }

从队首获取元素非常简单。判定是否为空，然后返回队头的值。

`7，Rear`: 获取队尾元素。

int myCircularQueueRear(MyCircularQueue* obj) { if(obj->front==obj->end) { return -1; } else { return *(obj->a+(obj->end+-1+obj->k+1)%(obj->k+1)); } }

从队尾获取元素较为复杂：因为end指针不指向队尾的元素。

简单，直接让end-1返回不就得了！错！必须考虑一种情况：当end指向的位置正好是队头，此时访问end-1会导致越界和未定义行为。

因此：需要一种回绕的方法不过这种回绕的方法（从前面绕到后面）和从后面绕到前面有所不同。

加上整个数组的长度k+1然后除以k+1。

这是一位牛人发明出来的方法

数学原理：(a mod n) ≡ (a + k n) mod n (对任意整数 k)

公式看不懂没关系，也就是在两个方面：

1，end在开头时：end-1向前移动一格，此时越界没关系，+k+1直接跳到最后。实现回绕。

2，end不在开头，end-1，+k+1会被取k+1模时抵消。end自然向前移动一格不受影响。

四，环形缓冲的应用

1. 进程间通信（IPC）

管道（Pipe）和 FIFO：
Linux 中的匿名管道底层常使用环形缓冲区，生产者写入、消费者读取，避免频繁内存分配。
消息队列：
内核级消息队列（如 POSIX mq）使用 ring buffer 存储待处理消息。

2. 中断与设备驱动

键盘/鼠标输入缓冲：
硬件中断将输入事件写入环形缓冲，用户态程序异步读取，防止丢失。
串口通信（UART）：
嵌入式系统中，串口接收数据通过 DMA 写入 ring buffer，主程序轮询或中断处理。

3. 日志系统

内核日志（如 printk 缓冲区）：
使用固定大小的环形缓冲存储最近的日志，旧日志自动覆盖，避免内存耗尽。

总结

环形缓冲是“在约束中追求极致效率”的典范。
它牺牲了动态性和灵活性，换来了确定性、高性能和资源可控性，因此成为系统底层、实时应用和高性能领域的“隐形支柱”。当你看到“流畅的视频通话”、“稳定的工业控制”、“毫秒级响应的游戏”，背后很可能都有一个默默工作的环形缓冲。

从零开始打造高性能数据结构——手把手教你实现环形缓冲

Ne0inhk

一，普通队列的劣势

1. 空间浪费严重（“假溢出”问题）

2. 需要频繁移动元素（若避免浪费）

3. 扩容成本高

4. 无法解决“假溢出”导致的提前扩容