一、引文渡口有一处奇景水面不直折成一圈。船从岸边出发绕行一周回到原点——首尾相衔无始无终。若是常过河的人会发现渡口从不清空上一趟船刚靠岸下一趟已等在老地方同一截水面周而复始地周转。程序员把这套把戏看穿了把它抽象成一条首尾相接的轨道给自己省内存、也省心思然后给它一个更不浪漫的名字——环形队列。下面把它拆开看。二、为什么需要它三个生活场景食堂排队窗口先来的人先打到饭后来的人自觉站在队尾没人能插到队首。你凭直觉就知道这是公平的——先到先得这也是队列最朴素的样子。打印店任务池打印机一次只处理一个文件。你点了打印它排在任务池里前面有几个人就得等几个人。屏幕上的队列越攒越长但顺序从未乱过。医院叫号机坐下来取一张号屏幕跳动叫到你的数字才起身。没被叫到的人并不消失只是在等待被消费。三个场景看着各不相干其实藏着同一件事数据只在队尾进来从队头出去中间的部分谁也别想插手。这种一端进、一端出的规矩有个学名叫 FIFO——First In, First Out。而环形队列就是把这条单行道首尾焊成一圈。三、原理拆得开四个动作就能描述它队列的所有行为拆到最细只有四个动作。这也是它能讲得这么干净的原因——复杂度全在约束上不在操作上。**enqueue**一个人站到队尾队列长度加一。**dequeue**队首那个人离场队列长度减一。这两个动作凭直觉就能懂。真正需要交代的是那两个指针它们是队列的眼睛决定你看得见什么。**front**指向下一个要走的人——也就是队首元素所在的位置。**rear**指向下一个来的人可以站的位置——也就是队尾的下一个空位。注意 rear 的措辞它指向的是空位不是最后一个人。这个区别此刻读起来只是个定义习惯像鸡毛蒜皮。但它是全文第一个坑先埋在这里。等到第七节你会看到前面列出的七成错误都源于对这个约定的误读。四、它和数组、普通队列的区别结构入队出队空间特点数组O(1)O(1)定长、连续普通队列O(1)O(n) 需前移尾部浪费环形队列O(1)O(1)定长、循环复用三行表差别只在出队那一列。1.数组的出队是 O(1)但代价是删掉的元素在逻辑上不存在了留下一个空洞要让空洞不出现就得把后面所有元素整体前移一格——于是每次出队都变成一次 O(n) 的搬运。2.普通队列继承了这个问题而且更糟队首的元素一个个走出去前面的位置空了后面的位置满了最终整条队列贴着右端左边一排空着右边再也塞不进任何人。空间还在但用不上。3.环形队列的办法是把下标超出数组长度的部分折回起点。走到尽头不是终点是重新出发。这个折在数学上由一个运算完成取模。当 rear 走到 4再加一是 5。5 除以 5 余 0——光点从 4 的位置跃回 0绕了完整一圈回到出发的位置。核心结论环形队列用取模运算把走到尽头折成绕回起点以此解决尾部的空间浪费。这格不是浪费。如果没有它队列满和队列空都会是 front rear程序将无法分辨这两种状态——而一个分不清空与满的队列毫无用处。五、意象落定一段有界却无终的岸把那圈水面落成代码就是一块固定大小的数组#defineQSIZE5intdata[QSIZE];// 环形石堤五格data 是石堤QSIZE 是堤长。它不生长也不断裂所有船只只能在它划定的范围内周转。而绕回起点的咒语只有一行rear(rear1)%QSIZE;rear 1 是往前走一步% QSIZE 是把溢出兜回来。当 rear 走到 4再加一是 55 除以 5 余 0——光点从 4 的位置跃回 0绕了一整圈回到原来的起点。这就是取模的全部作用也是环形队列全部的魔法。它没有新增任何能力只是给了溢出一个去处。六、代码逐段落地数组取模版完整可运行结构体与命名#defineQSIZE5// 队列容量实际能存 4 个元素typedefstruct{intdata[QSIZE];intfront;// 指向队首下一个要出队的元素intrear;// 指向队尾的下一个空位}Queue;为什么用 #define 而不是在代码里到处写 5因为 5 这个数字是魔数——它不解释自己。出现第二次时读代码的人不知道这两个 5 是不是同一件事哪天要改容量得靠搜索和运气。命名之后QSIZE 自带的语义是队列大小改动只发生在一处。初始化voidinit(Queue*q){q-front0;q-rear0;}两者都置为 0代表队列此刻为空也代表 rear 指向第一个可用位置。判空与判满intis_empty(Queue*q){returnq-frontq-rear;// 两个指针重合队列为空}intis_full(Queue*q){return(q-rear1)%QSIZEq-front;// 留一格作为满的标记}判空和判满看着对称实则不对称一个靠重合一个靠差一格。因为 rear 指向空位所以当 rear 绕一圈追上 front 的前一格时队列才算满。这一格是刻意让出去的它不是浪费它是区分空与满的凭据。入队与出队**intenqueue(Queue*q,intvalue){if(is_full(q)){printf([队列已满] 无法入队%d\n,value);return0;// 返回 0 表示失败与数据值绝不冲突}q-data[q-rear]value;q-rear(q-rear1)%QSIZE;return1;}intdequeue(Queue*q){if(is_empty(q)){printf([队列为空] 无可出队元素\n);return-1;// 约定队列为空时返回 -1}intvalueq-data[q-front];q-front(q-front1)%QSIZE;returnvalue;}**完整演示与预期输出intmain(void){Queue q;init(q);enqueue(q,10);enqueue(q,20);enqueue(q,30);printf(出队%d\n,dequeue(q));// 10printf(出队%d\n,dequeue(q));// 20enqueue(q,40);enqueue(q,50);enqueue(q,60);// 此时已满应提示失败while(!is_empty(q)){printf(出队%d\n,dequeue(q));}return0;}七、易错点系统梳理八、什么时候该自己写什么时候直接用***自己写。***​ 嵌入式环境里你根本没有标准库或者标准库的动态分配本身就是负担。内核缓冲区、固定容量的高并发日志收集、协议栈收发包这些地方要的是可预测的行为——你必须在编译期就知道这块内存有多大、什么时候被占用、什么时候被释放。环形队列在这里的价值从来不是队列是永不分配内存。***直接用标准库。***​ 业务层的普通需求任务调度、消息暂存、广度优先搜索的辅助结构。这些场景你真正在意的是交付速度而现代语言的标准库实现经过多年打磨边界情况处理得比你第一次写的更周全。重新造一个除了证明你写过通常不会更好。判断标准只有一条你是否需要控制内存的分配时机和生命周期。​ 需要就自己写不需要就别写。顺带提醒一个边界标准库里的队列多数是动态扩容的链表它不会浪费那一格也不会发生队满但代价是每次入队都可能触发一次内存分配。这一点在你的场景里如果不可接受标准库就不是选项——不是因为它不好是因为它的前提与你不同。九、收尾把代码折回人生普通队列像一条街走完就散了。环形队列像一圈转经筒把“先来后到”弯成了圆。出队的人被世界签收入队的人接住影子的尾。原来最稳的公平是转着圈也不偏袒谁。环形队列是时间最老实的圆。十、附录速查清单口诀1.rear 指空位2.加一要取模3.满空隔一格4.空满要分开动作动作写法易错点入队data[rear] v; rear (rear1) % QSIZE先写后移出队v data[front]; front (front1) % QSIZE空队返回值冲突判空front rear与判满必须不同判满(rear1) % QSIZE front漏写 1容量数组大小QSIZE可存元素QSIZE - 1留一格QSIZEsize 计数器下标范围0 ~ QSIZE - 1