队列Queue大概是数据结构里最贴近日常生活的模型食堂打饭、银行叫号、外卖订单排队处理全是同一套规则——先来的先办后来的后等。但“懂规则”和“会实现”是两码事尤其当你用C语言这种几乎没有封装、一切内存操作都暴露在眼前、一切错误都可能直接导致段错误或内存泄漏的语言去动手时才能真正理解这条FIFO规则在计算机里是怎么一点点落地运行的。这篇文章是我用C语言完整实现队列的一次记录顺序队列、环形队列、链式队列都会写到每一步都给可运行的代码和设计理由适合正在学数据结构的学生、备战笔试面试的自学者以及想回头巩固指针和内存管理细节的开发者参考。队列这个结构本身不复杂但越简单的东西越容易在细节上翻车。我见过不少人背了一堆队列的接口定义真到白纸上手写时要么把环形队列的判空判满条件写反要么链式队列里 free 了节点还在读数据。所以这篇不只是贴代码更重要的是把为什么这样设计讲清楚——为什么顺序队列必须用环形为什么链式队列建议带头结点为什么判满要牺牲一个存储格。搞清楚这些你才算真正掌握了队列而不是只是见过队列。1. 队列的本质与实现路线选择1.1 先想清楚队列在逻辑上解决什么问题队列的抽象规则就两条数据只能从队尾加入只能从队头取出即先进先出FIFOFirst In First Out。这个“先进先出”特性使它成为计算机里最基础的“缓冲”结构。你可以把队列想象成一根单头进单头出的水管或者超市收银台前的队伍第一个到的人先结账走人后来的人只能排在队尾。为什么需要这种结构因为计算机里大量场景天然就是“排队处理”的——任务不能同时执行只能按到达顺序轮流处理网络数据包到达顺序混乱需要队列缓冲后再按序处理程序里两个模块一个产生数据、一个消费数据中间必须有一个“蓄水池”来解耦这个蓄水池最常见的实现就是队列。所以队列真正解决的问题是在“生产”与“消费”速度不一致的场景下保持数据的相对顺序不变同时提供一个暂时存储的空间。这个视角很重要因为很多人在学队列时只背了“队尾插入、队头删除”的操作却忽略了它在系统设计里承担的缓冲、削峰、解耦角色导致一旦遇到实际项目就不知道什么时候该用队列。1.2 为什么必须用C语言来实现一遍高级语言里队列已经是现成的容器Java有java.util.QueueC有std::queuePython有collections.deque你调个接口就完事。但这样你永远看不到背后的东西数据存在哪、内存怎么申请和释放、队头队尾指针到底指向哪里、空间满了怎么办。C语言实现队列的价值在于没有中间商赚差价。数组的下标、指针的指向、malloc 申请的内存在哪、free 释放有没有遗漏全部暴露在你眼前。你写的每一个数据结构都要自己管好内存生命周期错误没有运行时保护踩到没分配的内存就直接段错误。这是一个非常磨人的过程但一旦在C里把队列写对写稳你对指针、数组、内存布局的理解会明显上一个台阶后面学树、图、哈希表都会顺畅很多。1.3 两条实现路线顺序存储与链式存储队列的底层存储无外乎两种顺序存储用一段连续内存数组来存数据。实现简单访问效率高但容量固定且普通顺序队列存在“假溢出”问题。链式存储用节点通过指针串成链。容量动态扩展不受预估限制但每个节点要额外存一个指针且 malloc/free 有调用开销。我这里特意提到“普通顺序队列”的假溢出问题这是很多新手第一次写队列时最容易掉进去的坑。所谓假溢出是指数组前段明明已经空出来了但因为队头指针永远只往后移、不回退导致队尾指针到达数组末尾后明明有剩余空间却无法再入队。这个问题直接催生了环形队列的经典设计后面会展开讲。实际项目中两种路线都有大量应用已知最大数据量、追求极速响应的场景环形队列是首选数据量动态变化、无法预估峰值的场景链式队列更合适。具体怎么权衡我放到后面专门开一节对比。2. 环形顺序队列用数组把空间真正用满2.1 为什么顺序队列必须升级成环形先看一个直接体现问题的例子。假设数组容量是5你连续入队5个元素front指向下标0rear指向下标5也就是刚好越过最后一个元素指向“下一个可写位置”。这时如果连续出队3个元素front向右移到下标3数组下标0、1、2就空出来了。按普通顺序队列的写法rear在5的位置你想再入队发现 rear 5 capacity判定“队满”拒绝入队——可是数组明明还有3个空位这就是“假溢出”。解决办法很朴素既然数组前面的空间空出来了就让 rear 绕回数组开头继续写。怎么绕取模运算。入队时rear (rear 1) % capacity出队时front (front 1) % capacity。类比钟表12点之后回到1点下标到达数组末尾之后回到数组开头形成一个“环形”的循环结构。斐波那契、约瑟夫环这类问题里经常能看到“绕回”的思想但队列这里用得最自然。2.2 环形队列的核心结构体设计#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; // 动态数组存放队列元素 int front; // 队头下标指向队头元素 int rear; // 队尾下标指向下一个可写位置 int capacity; // 数组最大容量 } Queue;关键点有两个。第一front和rear的语义front指向当前队头元素rear指向下一个可以写入的位置而不是最后一个元素。这样一个队列初始时front rear 0逻辑统一入队先写入再移动出队先取出再移动不用额外判断“第一个元素”这种边界情况。第二为什么用动态数组而不是静态数组因为实际使用中队列的规模往往无法预先确定动态分配可以在初始化时传入容量必要时还能扩展到更大的数组。这只是实现层面的灵活性核心逻辑不受影响。2.3 判空、判满、元素个数三个最容易写错的判断环形队列有三个核心判断必须一次性想清楚判空front rear判满(rear 1) % capacity front元素个数(rear - front capacity) % capacity判空好理解两个指针重合说明队列里没有元素。判满是重点——它要求数组中永远至少空出一个格子也就是 “队尾指针的下一个位置如果碰到队头就认为队列已满”。为什么要牺牲这一个格子因为如果不牺牲队列为空时front rear队列满时也会出现front rear两个指针绕一圈后重逢空和满就分不出来了。有人会问那我用另一个变量size记录元素个数不就不用浪费一个格子了确实可以这也是教科书里提到过的另一种实现方案。但多数场景下为了省一个单元格多维护一个size变量每次入队出队都要同步更新代码复杂度和出错概率都上来了不太划算。而且这个“牺牲一格”的思路一旦习惯写代码时对边界的警觉性会高很多算是一个训练价值。元素个数公式里的 capacity是为了防止rear - front出现负数。比如 front 在3rear在1此时1 - 3 -2加上 capacity 取模后就是真实个数不会出现歧义。2.4 入队、出队、销毁完整可运行的环形队列代码#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; int front; int rear; int capacity; } Queue; // 初始化队列容量由调用者指定 void queue_init(Queue *q, int capacity) { q-data (int *)malloc(sizeof(int) * capacity); if (q-data NULL) { fprintf(stderr, malloc failed\n); exit(1); } q-front 0; q-rear 0; q-capacity capacity; } bool queue_empty(Queue *q) { return q-front q-rear; } bool queue_full(Queue *q) { return (q-rear 1) % q-capacity q-front; } int queue_size(Queue *q) { return (q-rear - q-front q-capacity) % q-capacity; } // 入队先判满再写入最后移动 rear bool enqueue(Queue *q, int value) { if (queue_full(q)) { printf(队列已满无法入队 %d\n, value); return false; } q-data[q-rear] value; q-rear (q-rear 1) % q-capacity; return true; } // 出队先判空再取出最后移动 front bool dequeue(Queue *q, int *value) { if (queue_empty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front (q-front 1) % q-capacity; return true; } // 只取队头元素不弹出 bool queue_front(Queue *q, int *value) { if (queue_empty(q)) { printf(队列为空无队头元素\n); return false; } *value q-data[q-front]; return true; } // 销毁队列释放动态数组 void queue_destroy(Queue *q) { free(q-data); q-data NULL; q-front q-rear 0; q-capacity 0; } int main(void) { Queue q; queue_init(q, 5); enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); enqueue(q, 40); enqueue(q, 50); enqueue(q, 60); // 会提示队列已满 int val; dequeue(q, val); // 10 printf(出队: %d\n, val); dequeue(q, val); // 20 printf(出队: %d\n, val); // front 已经移动数组前两格空出这里再次入队验证环形复用 enqueue(q, 60); enqueue(q, 70); while (!queue_empty(q)) { dequeue(q, val); printf(%d , val); } printf(\n); queue_destroy(q); return 0; }运行结果里有两个值得注意的细节第一次enqueue(q, 60)提示队列已满因为此时 rear 已到下标4(41)%5 0 front判满成立。而连续出队两个元素后front 移到下标2空出了0和1两个位置再入队60和70时rear 从4绕回0、再写到1输出去重时也能正常按30 40 50 60 70顺序弹出。这就是环形队列的核心价值数组前部空间被重复利用不再出现假溢出。提示入队操作里rear移动使用的是(rear 1) % capacity出队里front同理这个取模逻辑一旦不一致就会出现下标越界或数据错位。我在自查的时候习惯把两个%操作列为重点排查对象。2.5 初始化容量和扩展的思量入队前需要预估容量。已知业务峰值且稳定直接初始化一个够用的数组最稳不折腾。但如果你无法预估峰值又不想用链式实现就得考虑扩容申请一块更大的数组、把旧数据按front到rear的顺序整体迁移、释放旧数组、更新 capacity。扩容本身不算难但要注意迁移逻辑不能直接memcpy整个数组因为环形结构下元素在内存中可能首尾相接必须先按队列逻辑顺序取出元素再写入新数组。没有这一步扩容后队列里元素的相对顺序就乱了。这也是我在实际编码中用“先出队再入队”的思路来写扩容函数的原因简单且不容易错。3. 链式队列让容量真正不受限制3.1 为什么链式队列建议带头结点链式队列的存储单元是节点每个节点包含数据域和指针域。与环形队列不同它没有固定容量内存按需申请所以特别适合数据量动态变化、难以预估上线的场景。但链式队列有个隐藏的分支设计头结点到底要不要存在所谓头结点是一个不存储有效数据的哨兵节点它位于真正的队头节点之前。有了头结点队列结构体里可以始终保存两个指针front指向头结点rear指向队尾节点。如果不带头结点空队列时front NULL且rear NULL入队时如果队列为空要同时修改front和rear两个指针出队时如果队列只剩一个节点又要同时处理front和rear。每次操作都要多套一层“是否为空”的 if 分支代码重复且容易漏。而有了头结点空队列时front-next NULL入队永远统一在rear-next后面挂新节点出队永远统一删除front-next逻辑清爽很多。3.2 节点结构与接口设计#include stdio.h #include stdlib.h #include stdbool.h typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *front; // 指向头结点 Node *rear; // 指向最后一个节点 } LinkQueue;入队、出队、销毁的核心步骤每一步都要防着指针别丢、内存别漏入队void enqueue(LinkQueue *q, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) { fprintf(stderr, malloc failed\n); exit(1); } newNode-data value; newNode-next NULL; q-rear-next newNode; q-rear newNode; }出队bool dequeue(LinkQueue *q, int *value) { if (q-front-next NULL) { printf(队列为空无法出队\n); return false; } Node *temp q-front-next; *value temp-data; q-front-next temp-next; if (q-rear temp) { q-rear q-front; // 被删的是唯一数据节点rear 要回退到 head } free(temp); return true; }出队这里有一行极其关键的边界处理if (q-rear temp) q-rear q-front;。当队列只有一个数据节点时temp既是队头也是队尾front的 next 直接指向 NULL 后如果不重置rear它仍然指向已释放的temp后续入队时q-rear-next newNode就是写野指针程序直接崩溃。这个坑我自己踩过一次排查的时候花了不少时间因为它只在队列长度恰好为1时触发平时测试数据稍多就看不出问题。销毁队列void destroy_queue(LinkQueue *q) { Node *cur q-front; while (cur ! NULL) { Node *temp cur; cur cur-next; free(temp); } q-front q-rear NULL; }销毁和出队的本质是一样的每释放一个节点先用一个临时指针保存下一个节点地址再 free 当前节点。很多人写销毁时先 free 了当前节点再访问cur-next这就变成了典型的“释放后使用”属于内存错误的教科书案例。3.3 链式队列完整测试代码int main(void) { LinkQueue q; // 初始化创建头结点 q.front (Node *)malloc(sizeof(Node)); if (q.front NULL) return 1; q.front-next NULL; q.rear q.front; for (int i 1; i 8; i) { enqueue(q, i * 100); } int val; for (int i 0; i 3; i) { dequeue(q, val); printf(出队: %d\n, val); } enqueue(q, 999); while (!queue_empty(q)) { dequeue(q, val); printf(%d , val); } printf(\n); destroy_queue(q); return 0; }注意链式队列入队后如果忘记更新rear下一次入队会覆盖同一个节点表现为“队列永远只有一个元素”。这种问题调试起来很迷惑因为单步执行时每一步看着都对数据却不对。我的经验是盯住rear指针在入队前后是否真的前移了用调试器查看指针地址非常直观。4. 两种实现的硬核对比与现实选型4.1 一句话记住各自特点对比维度环形顺序队列链式队列底层存储连续数组非连续节点堆容量固定或需扩容迁移按需申请不受上限约束入队/出队时间O(1)无动态分配O(1)但含 malloc/free 调用开销空间占用数组两个下标无额外指针开销每个节点多一个 next 指针空满判断有“牺牲一格”的约束无只要内存够都能入队适用场景性能敏感、规模可预估、高频操作规模不确定、需要频繁创建销毁队列最核心的取舍在于环形队列是“事先划好一块地盘自己管边界”链式队列是“随时去堆里要内存用完马上还回去”。前者省掉了动态分配的时间但承担了容量预估错误的风险后者灵活但没有上限地申请内存如果忘了释放程序跑得越久泄漏越严重。4.2 多个真实场景应该选谁这里举三个最典型的应用场景第一广度优先搜索BFS。图的 BFS 天生依赖队列逐层扩展节点。搜索时通常先估算状态空间规模再用一个足够大的环形队列或直接申请数组空间。因为 BFS 过程中的入队出队次数非常多如果每个节点都走一次 malloc性能会明显下降。这类场景链式队列不是不行而是没必要。第二嵌入式串口缓冲区。单片机里接收串口数据如果数据到达速度偶尔高于处理速度需要临时缓冲。嵌入式环境内存极其有限几乎不可能用链式结构去动态申请内存固定容量的环形缓冲区是绝对的主流选择。我见过很多协议解析模块底层就是一个环形队列满了之后要么丢弃最老数据要么直接丢弃新数据策略不同但结构相通。第三线程池任务队列。线程池里任务数量不可预估一个任务发布者不断提交任务多个工作线程不断取任务执行。此时链式队列天然合适因为任务数量就是内存分配的数量任务处理完节点释放队列长度自适应业务压力。如果强行用环形队列任务峰值一旦超过容量要么阻塞发布者要么丢任务体验都差。4.3 我自己的选型经验我的习惯是凡是能估算最大量的场景一律优先环形队列凡是量级不确定、且对入队出队性能不那么苛刻的场景才用链式队列。实际操作里还有一个折中方案——动态扩容的环形队列初始一个小容量数组满了之后按 1.5 或 2 倍扩容既保住连续内存的访问性能又规避容量预估风险。代价是扩容那一瞬间有 O(n) 的搬移但均摊下来依然很快。这种设计在很多语言的标准库里都能看到影子C 语言里自己实现一遍也完全不复杂。5. 实战问题排查与避坑清单5.1 典型错误一入队忘记取模数组越界写入// 错误示例 void enqueue_bad(Queue *q, int value) { if (queue_full(q)) return; q-data[q-rear] value; q-rear; // 忘了取模 }当 rear 到达 capacity-1 之后继续入队q-data[rear]会写到数组边界之外。C 语言不检查数组越界这块未定义行为可能不会立刻崩溃而是悄悄污染相邻内存等你发现时数据已经乱得没法查。排查这种问题最直接的手段是用-fsanitizeaddress重新编译越界访问当场就会报错。5.2 典型错误二判空判满条件混用有些同学记不住“牺牲一格”的思路把容量为 N 的环形队列当成了 N 个格子都能用于是判满写成rear front。结果队列刚满的时候和队列为空时的判断一模一样程序要么把满队列当成空队列读出一个脏数据要么入队时把队头元素覆盖掉丢数据。这类 bug 的隐蔽性在于只有当入队到刚好填满 N 个元素时才会触发用少量数据测试往往测不出来。修复方法就是我上面讲的容量是 N 的数组实际最多只能放 N-1 个元素判满必须写成(rear 1) % capacity front。5.3 典型错误三链式队列 free 后继续使用// 错误示例 bool dequeue_bad(LinkQueue *q, int *value) { Node *temp q-front-next; *value temp-data; q-front-next temp-next; // 这里 ok free(temp); return true; }这段代码在队列只有一个数据节点时q-rear还指向已释放的temp下一次入队执行q-rear-next newNode就是写已释放内存程序大概率崩溃。修复前面已经给出更新 front 后检查 rear 是否指的就是被删节点若是则把 rear 重置为 front。5.4 典型错误四扩容或销毁时内存泄漏链式队列每 malloc 一个节点就必须有一个对应的 free。销毁队列的循环里如果只 free 当前节点而不先保存 next或者循环条件写错导致一半节点无从访问就产生泄漏或者段错误。排查内存问题的实用工具链我一般这么用Linux 下用valgrind跑一遍能看到每个泄漏点在哪一行申请的配合 AddressSanitizer 一起用越界和释放后使用都能精准定位。我自己的习惯是写完队列代码就先跑一遍这两个工具而不是等出现肉眼可见的 bug 才回头查。5.5 队列代码自查清单写完队列代码后逐条过一遍这些问题空队列时调用dequeue和front程序是否能安全返回 false 而不是崩溃满队列时调用enqueue是否能安全拒绝而不是覆盖数据环形队列的所有下标移动是否都是(当前下标 1) % capacity有没有一处漏了%链式队列出队删除唯一节点后rear是否已经重置每个malloc都有对应的free吗环形队列初始化后、链式队列销毁后指针是否都已置空避免二次释放这六条是我自己写数据结构代码时的必查项分享出来直接当模板抄即可。队列本身难度不大真正拉开差距的从来不是“写出来”而是“写对、写稳、知道为什么这样写”。这份实战记录如果能帮你在面试或项目中少踩几个坑那它就起到作用了。