博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub数据结构专栏路漫漫其修远兮吾将上下而求索文章目录前言一、普通数组实现队列问题1.假溢出2.数据搬移代价高昂3.扩容与提前扩容的连锁反应二、环形队列的核心思想三、头尾指针定义与关键约定约定牺牲一个存储单元四、代码实现1.结构搭建2.初始化3.检查缓冲器是否为空4.检查缓冲器是否已满5.入队6.出队7.获取队头元素8.获取队尾元素9.销毁环形缓冲器五、实际应用场景六、为何用数组而非链表实现七、总结八、练习前言为什么需要环形缓冲器环形队列——当我们使用普通数组来实现队列时会面临多个严重的问题而当使用链表实现时会有额外的空间开销并且缓存命中率低。先看队列概论队列Queue是一种常见的数据结构遵循先进先出FIFO 的原则——最早进入队列的元素将最先被移除。队列在计算机科学中有广泛的应用比如任务调度、网络流量控制、打印任务管理等记住这些定义我们将立刻解析使用数组实现队列的天然问题一、普通数组实现队列问题1.假溢出不移动元素实现的情况下以低下标位作为队头无法避免每次出队后队头指针后移导致指针前的数组空间被浪费的情况。以高下标位作为队头无法避免随着不断出队导致队尾指针前的数组空间被浪费的情况。⌈明明数组前面还有空闲空间却无法使用——这就是所谓的 “假溢出” 问题⌋2.数据搬移代价高昂一种直观的解决方案是每次出队后将后面的所有元素整体前移。但这意味着每次出队操作的时间复杂度都变成O(n)对于频繁操作来说是不可接受的性能将急剧下降。3.扩容与提前扩容的连锁反应如果队列真的满了我们可能需要扩容创建一个更大的数组并复制数据。但假溢出现象会导致提前扩容明明还有空闲空间却因为指针无法回绕而被迫扩容这进一步放大了性能开销和内存占用。试想一下一个网络数据包缓冲队列每秒处理数万个包如果每次出队都要搬移数据或频繁扩容系统性能将不堪重负。二、环形队列的核心思想将数组的尾部与首部连接起来形成一个逻辑上的环。 关键点数组在物理上仍然是线性的但通过取模运算modulo 在逻辑上实现了循环。当指针移动到数组末尾时通过取模运算让它“绕回”到数组开头从而复用之前释放的空间。三、头尾指针定义与关键约定实现环形队列需要明确两个指针的定义指针定义初始值front指向队列中的第一个有效元素0rear指向队列中最后一个有效元素的下一位0为什么要让 rear 指向队尾的下一位为区分判空与判满重叠的问题请继续阅读。约定牺牲一个存储单元当队列为空时判断条件为 front rear而当数组中存满元素rear 通过回绕最终会回到 front 的位置rear指向下一次入队位置此时同样满足条件若判满仍使用 front rear则会出现判断不明确的问题。环形缓冲器逻辑图例解决方式设数组申请了 n 个空间那我们最多存储 n - 1 个值刻意空出一个位置使判满条件变成 front rear 1注意此为逻辑层实际需取模。为什么判满条件为 front rear 1?答rear 指向最后一个有效元素的下一位当大小为 n 的数组中已有 n - 1 个值时还剩下一个空位此时队列已满不能再插入新元素若 rear 再加一就会追上 frontrear 指向那个空位因此能判满。环形缓冲器逻辑图例四、代码实现1.结构搭建typedefstruct{int*arr;#存储数据的数组intfront;#队头指针intrear;#队尾指针intk;#实际容量}MyCircularQueue;利用结构体实现环形缓冲器并在其中存储队列信息结构体命名方式利用了匿名结构体的特性直接改名为 MyCircularQueue。2.初始化MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*objmalloc(sizeof(MyCircularQueue));obj-arrmalloc(sizeof(int)*(k1));obj-frontobj-rear0;obj-kk;returnobj;}形参k为环形缓冲器中的实际存储量因此在开辟数组时多开一个单元将头尾指针初始化为0从数组开头循环并将k设置为实际存储量。注k也可初始化为数组的容量 n这里初始化为 n - 1。3.检查缓冲器是否为空boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-frontobj-rear;}按照之前的逻辑判断即可空返回 true非空返回 false。4.检查缓冲器是否已满boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-rear1)%(obj-k1)obj-front;}我们之前讨论过当前 rear 的位置加一如果是 front则已满取模原本数组的容量即为 k 1。注特殊情况需利用模运算保证指针的循环访问否则会越界。5.入队boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(myCircularQueueIsFull(obj))returnfalse;obj-arr[obj-rear]value;obj-rear(obj-rear1)%(obj-k1);returntrue;}先检查当前队列中是否已满如果已满返回 false 代表操作失败未满让新值入队在队尾并让 rear 1最后返回 true 代表操作成功。6.出队boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;obj-front(obj-front1)%(obj-k1);returntrue;}先检查当前队列中是否为空如果为空返回 false 代表操作失败未满从队头出队并让 front 1注意需取模避免越界最后返回 true 代表操作成功。7.获取队头元素intmyCircularQueueFront(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;returnobj-arr[obj-front];}直接利用 front 指针找到队头元素即可。当队列为空时返回任意一个不存在于规定的存储集合中的元素代表查找元素不存在。8.获取队尾元素intmyCircularQueueRear(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;returnobj-arr[(obj-rearobj-k)%(obj-k1)];}判断与返回值操作同上特殊情况为当 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.销毁环形缓冲器voidmyCircularQueueFree(MyCircularQueue*obj){free(obj-arr);obj-arrNULL;obj-frontobj-rearobj-k0;free(obj);}释放结构体内数组开辟的空间将指针与属性初始化后释放结构体本身开辟的空间。不做指针与属性初始化操作不影响功能但销毁顺序绝不能更改。五、实际应用场景操作系统中的键盘/鼠标输入缓冲当用户敲击键盘时按键事件被放入环形队列中断处理程序从队列中取出事件保证事件有序处理。串口通信UART 串口接收数据时硬件将数据写入环形缓冲区CPU从缓冲区读取避免数据覆盖。网络协议栈的接收/发送缓冲区例如网卡驱动中的环形描述符队列。音频/视频播放器播放器从网络或文件中读取数据填入环形缓冲区解码线程从中取出数据平滑播放。日志系统循环覆盖旧的日志条目保留最新的N条记录。线程池的任务队列工作线程从环形缓冲器中拉取任务生产线程负责往里放任务。六、为何用数组而非链表实现环形缓冲器也可以用链表实现但数组实现具有明显的优势缓存局部性数组在内存中连续存储CPU缓存命中率高访问速度快。链表的节点分散在堆中缓存不友好且每次访问需指针跳转。无内存碎片数组一次性分配固定大小不会产生内存碎片链表频繁增删节点容易导致碎片化。适合底层开发在嵌入式、操作系统内核等场景中数组实现的环形缓冲更可控可提前预分配内存避免运行时分配失败。链表实现的唯一优势是无需事先知道最大容量可以动态扩容。但在绝大多数场景中环形缓冲器的容量是可预知的例如缓冲区大小固定因此数组实现是更优的选择。七、总结环形队列通过 “取模回绕” 和 “指针约定” 巧妙地解决了普通数组队列的空间浪费和性能问题。1、核心机制front 和 rear 两个指针 %运算实现循环复用2、区分空/满牺牲一个存储单元或增设 size 字段3、时间复杂度入队和出队均为O(1)4、空间效率数组空间循环使用无“假溢出”5、实用价值在操作系统、网络通信、多媒体处理等场景中不可或缺八、练习推荐如下LeetCode题目622. 设计循环队列 链接: link.⚛️EL PSY CONGROO十分感谢你的阅读本期不确定要写使用链表实现环形缓冲器作为练习吗