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

◆ 博主名称： 小此方-CSDN博客

大家好，欢迎来到小此方的博客。

⭐️个人专栏：《C语言》_小此方的博客-CSDN博客

算法_小此方的博客-CSDN博客

⭐️踏破千山志未空，拨开云雾见晴虹。 人生何必叹萧瑟，心在凌霄第一峰。

我们为什么需要环形缓冲（循环队列）？实际上，我们不妨先审视普通数组队列的局限性。正是这些缺陷，催生了环形缓冲这一高效、紧凑的数据结构。

一，普通队列的劣势

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

●在普通线性队列中，元素从队头（front）出队后，其占用的空间无法被复用。即使数组整体仍有大量空位，只要队尾（rear）到达数组末尾，系统就会误判为“已满”，导致明明有空间却无法继续入队——这种现象称为“假溢出”。

示例：容量为 10 的队列，先入队 8 个元素，再出队 6 个。此时仅剩 2 个有效元素（位于索引 6 和 7），但队尾在 8。若再尝试入队第 3 个元素，队尾将越界至 11，系统被迫认为“满”，尽管前 6 个位置完全空闲。

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

• 为解决空间浪费问题，有些实现会在每次出队后将所有剩余元素向前移动，以保持队头始终在数组起始位置。
• 这种做法导致出队操作的时间复杂度变为 O(n)，效率低下。

3. 扩容成本高

• 当队列满时，需要：
  • 申请一块更大的内存（通常是原大小的 1.5 倍或 2 倍）；
  • 将所有有效元素从旧数组复制到新数组；
  • 释放旧内存。
• 这个过程的时间复杂度是 O(n)，且可能触发内存分配延迟，在实时系统或高频场景中不可接受。

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

• 在普通线性队列中，即使数组总容量未满，只要队尾到达数组末尾，就会认为“满了”，从而触发不必要的扩容。
• 例如：容量为 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 缓冲区）： 使用固定大小的环形缓冲存储最近的日志，旧日志自动覆盖，避免内存耗尽。

总结

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