队列这东西在数据结构里属于最基础、却也是实际工程里出场率极高的一批。写过几年 C 的人应该都有体会搞懂链表、栈、队列这三板斧再去碰操作系统、网络协议栈或者消息中间件很多抽象概念瞬间就有了落点。今天想结合我自己的实战经验把“队列Queue的C语言实现”这件事从头到尾捋一遍从最简单的数组模拟开始到环形队列、链式队列再到实际开发里容易踩的坑把这一个点彻底讲透。这篇文章适合正在学数据结构的同学、准备面试的开发者也适合工作中需要自己封装底层数据结构的嵌入式或后端工程师。不管你现在在哪个阶段只要能跟着敲一遍代码队列从理论到实践这一关就算过了。1. 队列是什么从生活场景到程序世界的先进先出队列的核心规则一句话就能说完先进先出First In First Out简称 FIFO。这和栈的先进后出正好相反。生活中最常见的例子就是排队买饭先到的人先打饭后到的人只能排在后面。在程序世界里队列做的事情和这个一模一样先进入队列的数据元素先被取出。1.1 队列的两个关键操作视角学习队列时很多人只记住了“入队”和“出队”两个词但真正理解队列必须从三个维度看队头front、队尾rear、以及数据元素的流动方向。入队enqueue只允许在队尾添加元素新元素永远排在最后面。出队dequeue只允许从队头移除元素最先进入的元素最先被处理。查看队头peek/front只读取队头元素但不移除这个操作在实际业务中非常常用比如消息队列里“看一眼下一条是什么”的场景。从这个设计能看出来队列天然就是一个“缓冲地带”。生产者把数据塞进队尾消费者从队头取数据两边互不干扰。这种解耦思路是队列在系统设计中价值最大的地方。1.2 两种存储结构顺序队列 vs 链式队列用 C 语言实现队列第一步要选存储结构。两条路线各有各的舞台。顺序队列底层是一块连续的内存空间通常用数组实现。优点是内存紧凑、缓存友好、随机访问快缺点是在普通数组实现下队头出队后留下的空间没法复用需要额外的取模运算或数据搬移设计才能绕过去。链式队列底层用链表节点每个节点包含数据域和指向下一个节点的指针。优点是可以无痛扩容不会出现“数组满了但队头还有空位”的尴尬缺点是多了一个指针开销并且每次入队要动态分配内存在实时性要求高的场景里可能造成性能抖动。实际工程里两种队列都很常见。嵌入式设备里常用环形数组队列因为内存是固定的不能随便 malloc而通用服务器程序里链式队列更灵活因为业务规模可能随时膨胀。没有绝对的好坏只有适不适合场景。2. 顺序队列的内存模型与初始实现顺序队列用数组实现需要关注的核心变量有四个存储元素的数组、容量、队头位置、队尾位置。很多教材给的代码是一个结构体包着五个成员看起来复杂其实拆开看就清楚了。2.1 数组模拟队列的基础版先写一个最朴素版本。这个版本的功能是完整的但存在严重缺陷后面会详细说。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标指向最后一个元素的下一个位置 } Queue; // 初始化队列 void initQueue(Queue *q) { q-front 0; q-rear 0; } // 判断队列是否为空 bool isEmpty(Queue *q) { return q-front q-rear; } // 判断队列是否已满 bool isFull(Queue *q) { return q-rear MAX_SIZE; } // 入队 bool enQueue(Queue *q, int value) { if (isFull(q)) { printf(队列已满无法入队\n); return false; } q-data[q-rear] value; q-rear; return true; } // 出队 bool deQueue(Queue *q, int *value) { if (isEmpty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front; return true; }这个版本用起来很方便front 指向队头元素rear 指向队尾元素的下一个空位入队时数据写到q-data[q-rear]然后 rear 自增出队时读取q-data[q-front]然后 front 自增。判空条件front rear这个条件在初始状态和所有元素出队后都成立逻辑上是自洽的。2.2 基础版的致命缺陷假溢出上面这个版本最大的问题就是“假溢出”。假设队列容量是 5你连续入队 5 个元素再出队 4 个元素此时排序上看起来队列里只剩下 1 个元素但 front 和 rear 的指针已经走到数组末尾rear MAX_SIZE成立再入队就会提示“队列已满”。看清楚这根本不是真的满了数组前面 4 个位置全是空的。这种现象就叫假溢出。假溢出的本质是我们只把数组当成了线性空间没有把首尾连接起来。解决思路也很经典把数组想象成一个环形跑道front 和 rear 的位置到了数组末尾后自动绕回开头继续走。这种实现就是环形队列也叫循环队列。3. 环形队列解决假溢出的经典方案环形队列是顺序队列在工程实践中的标准形态。它用取模运算实现下标绕回核心逻辑不复杂难就难在边界条件的处理上。写这块代码的时候我踩过不少坑这次直接把每个关键点都摊开讲。3.1 环形队列的核心思想环形队列依然是数组只是在指针移动时加了一层取模逻辑。队尾指针更新公式变为q-rear (q-rear 1) % MAX_SIZE;队头指针同理q-front (q-front 1) % MAX_SIZE;比如容量是 5rear 当前在 4入队后 rear 就变成(4 1) % 5 0绕回数组开头。下一个问题是判空和判满。判空仍然是front rear。但如果判满也写成front rear就会和判空发生冲突。考虑一个容量为 5 的环形队列从空开始不断入队当第 5 个元素入队后rear 移动了 5 次正好又回到 front 的位置此时front rear但队列实际是满的。这就导致“空”和“满”无法区分。解决这个矛盾的方案有三种牺牲一个存储单元当(rear 1) % MAX_SIZE front时认为队列满。这意味着队列最多只能存MAX_SIZE - 1个元素让 rear 永远不追上 front。增设计数器用 size 变量记录元素个数入队加一出队减一。空和满就看 size 是 0 还是 MAX_SIZE。增设标志位用 flag 变量区分是删除导致的相等还是插入导致的相等。教科书里最常用的是方案一因为它不浪费额外变量。实际工程里方案二更直观避免了空满边界思考。我这里先重点讲方案一因为它是理解整个环形队列的关键所在。3.2 完整实现结构体定义、初始化、判空判满这里给出一个完整的环形队列实现后面所有代码都是围绕这一版展开的。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 5 typedef struct { int data[MAX_SIZE]; int front; // 队头下标指向队头元素 int rear; // 队尾下标指向队尾元素的下一个位置 } CircularQueue; // 初始化 void initQueue(CircularQueue *q) { q-front 0; q-rear 0; } // 判空 bool isEmpty(CircularQueue *q) { return q-front q-rear; } // 判满牺牲一个存储单元 bool isFull(CircularQueue *q) { return (q-rear 1) % MAX_SIZE q-front; } // 获取当前队列元素个数 int queueSize(CircularQueue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }这里queueSize的计算公式需要重点理解。因为 rear 和 front 谁大谁小不确定所以不能直接用q-rear - q-front而是先加 MAX_SIZE 再取模保证结果落在 0 到 MAX_SIZE-1 之间。这是环形队列里最容易被写错的一行代码建议直接记下来。3.3 入队、出队、获取队头元素入队和出队的实现关键是操作顺序和取模运算。// 入队 bool enQueue(CircularQueue *q, int value) { if (isFull(q)) { printf(队满入队失败\n); return false; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return true; } // 出队 bool deQueue(CircularQueue *q, int *value) { if (isEmpty(q)) { printf(队空出队失败\n); return false; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return true; } // 获取队头元素 bool peekFront(CircularQueue *q, int *value) { if (isEmpty(q)) { printf(队空无法获取队头元素\n); return false; } *value q-data[q-front]; return true; }入队的过程拆开看就是三步先判断满再把数据写到 rear 位置最后让 rear 绕圈走一步。出队类似先判断空读取 front 位置数据再让 front 绕圈走一步。我在实际写代码时出队函数有一段小纠结到底是先读取数据再移动 front还是先移动 front 再读取数据答案必须选前者。如果先移动 front第二次出队时读到的就是后一个元素数据全乱了。这个顺序问题在链式队列里同样存在后面会再提到。3.4 关键边界条件为什么牺牲一个存储单元很多人刚接触环形队列时不理解“牺牲一个存储单元”这个操作总觉得浪费。我换个方式解释。想象一个圆桌桌上摆了 5 个座位但没有编号。两个人在玩一个游戏一个人只能往顺时针方向移动另一个人只能逆时针方向移动两个人不能在同一个位置。这两个人的位置如果相同就说明“追尾了”。front和rear就是这两个人。front 负责从队头消费位置rear 负责从队尾生产位置。当 rear 追上 front 时队列确实满了。但在环形结构里满和空都表现为两个指针重合如果不牺牲一格就无法判断到底是谁先占了那个位置。牺牲一格的意思是rear 永远不允许指向 front 的位置当(rear 1) % MAX_SIZE front时就强制停止入队。这样队列最多存储MAX_SIZE - 1个元素。以容量 5 为例最多存 4 个。多出的那一格就像一个“安全隔离带”把满和空这两个状态彻底分开了。如果不想牺牲这一格就用计数器方案。这个方案很直接typedef struct { int data[MAX_SIZE]; int front; int rear; int size; } CountQueue; bool isFull(CQueue *q) { return q-size MAX_SIZE; } bool isEmpty(CQueue *q) { return q-size 0; }入队时q-size出队时q-size--。不用再绕脑子理解取模边界了。工程里如果内存不是卡得特别死我反而更推荐这种方式因为团队协作时别人读你的代码不会迷路。4. 链式队列不固定容量的另一种选择环形队列的容量是写死的在嵌入式、操作系统内核这些内存受限场景里没问题。但如果你写的是一个通用服务业务高峰期和低峰的访问量可能相差几百倍固定容量就不好办了。这时候链式队列上场它不限制元素个数队列能长能短动态适应。4.1 链式队列的结构设计链式队列的每个节点是一个链表节点有两个指针一个指向队头一个指向队尾。这里有一个常见设计分歧队头用头结点还是直接指向第一个数据节点。二叉树的兄弟都知道链式队列空不空、入队出队时头尾指针怎么变化这问题如果不画图光靠脑子想很容易漏。标准做法是带头结点。头结点是哨兵不存数据只作为标记。这样做的最大好处是空队列和非空队列的入队操作可以统一处理不需要分支判断。结构体定义如下typedef struct Node { int data; struct Node *next; } LinkNode; typedef struct { LinkNode *front; // 队头指针指向头结点 LinkNode *rear; // 队尾指针指向最后一个节点 } LinkQueue;注意这里front和顺序队列里的 front 含义不同。顺序队列的 front 是一个下标链式队列的 front 是一个指向头结点的指针。头结点的 next 才指向真正的队头元素。4.2 完整实现初始化、入队、出队、释放初始化时创建头结点front 和 rear 都指向头结点。// 初始化链式队列 bool initLinkQueue(LinkQueue *q) { q-front (LinkNode *)malloc(sizeof(LinkNode)); if (q-front NULL) { return false; } q-front-next NULL; q-rear q-front; return true; }入队操作在队尾插入新节点。这里发现一个细节因为入队只动 rear所以尾插的代码非常短。如果要入队第一个元素rear 本来就指向头结点把新节点挂到 rear-next 上然后移动 rear照样成立。// 入队 bool enLinkQueue(LinkQueue *q, int value) { LinkNode *newNode (LinkNode *)malloc(sizeof(LinkNode)); if (newNode NULL) { printf(内存申请失败入队失败\n); return false; } newNode-data value; newNode-next NULL; q-rear-next newNode; q-rear newNode; return true; }出队要删除的是头结点之后的第一个节点。这里有一个很容易翻车的点如果要删除的节点恰好是队尾节点那么删除后 rear 指针就成了悬空指针。所以出队必须加一个判断如果出队后队列为空要把 rear 重新指向头结点。// 出队 bool deLinkQueue(LinkQueue *q, int *value) { if (q-front q-rear) { printf(队列为空出队失败\n); return false; } LinkNode *temp q-front-next; *value temp-data; q-front-next temp-next; if (q-rear temp) { q-rear q-front; } free(temp); return true; }释放整个队列时要从头结点往后逐个释放不能只释放头结点。这里我习惯用一个遍历指针循环来释放简单直接。// 销毁队列 void destroyLinkQueue(LinkQueue *q) { LinkNode *curr q-front; while (curr ! NULL) { LinkNode *next curr-next; free(curr); curr next; } q-front NULL; q-rear NULL; }链式队列的扩容过程完全依赖 malloc 和 free明显的好处是理论上没有容量上限只要内存够数据可以一直往里加。坏处是每个节点多了 8 字节64 位系统指针大小的额外开销而且频繁 malloc/free 会产生内存碎片。所以链式队列更适合节点数量不确定、波动大的场景。5. 队列的应用场景与面试常考变形队列远不只是教学用的实际工程中用到的队列比很多人想象中要多得多。写到这里我觉得有必要把“学了队列能干嘛”这件事说清楚。5.1 实际应用领域1. 任务调度与消息缓冲CPU 任务调度是操作系统教科书里第一个用到队列的地方。多个进程排队等待 CPU 时间片新来的进队列尾部当前执行完的进程决定是重新排队还是出队。消息中间件更典型生产者发的消息进队列消费者独立地从队列头取消息通过队列实现生产者消费者解耦。2. 广度优先搜索 BFS图算法里BFS 的实现必须用队列。从起点开始把相邻节点依次入队再从队头取节点继续扩展。这个过程天然就是 FIFO先发现的节点先被处理保证按层扩展。换个深度优先的话BFS 就变成 DFS 了。3. 缓冲区Buffer嵌入式开发里串口和网络数据的接收通常会用环形队列做缓冲区。比如传感器数据不断进来主循环抽空处理中间用队列存住。如果不用队列数据来了处理不了就会丢用了队列就有了缓冲时间。4. 线程池任务队列线程池实现里一般有一个任务队列新任务先入队空闲线程从队头取任务执行。这本质上就是一个多生产者多消费者的队列模型。5.2 双端队列和循环队列的变形面试时经常在队列基础上出变形题最常遇到的有两种双端队列deque两端都可以入队和出队。底层实现可以用带头尾指针的双向链表更极致的实现是用数组加头尾下标此时就是“循环双端队列”。LeetCode 上的“滑动窗口最大值”就是依托双端队列的经典题。用循环队列实现栈或其他结构这类问题考的是对两种结构本质的理解。以循环队列为底层实现一个类似栈的结构核心思路是入栈时在队尾插入出栈时把除队尾外的所有元素出队再重新入队最后队尾元素就是栈顶出队返回。空间换时间但逻辑上很有意思。面试时做这类题重点不是代码多炫而是能把空、满、边界条件表达清楚。对出队导致 rear 变化的情况如果能主动说明“这里要处理链表尾节点删除后指针修正”面试官就会知道你真正理解了。6. 常见问题与排查技巧实录前面讲的是原理和代码最后这部分我想把平时排查问题时积累的经验分享出来。这些问题我踩过也在帮别人 review 代码时见过太多次。6.1 问题速查表现象可能原因解决建议入队总是提示队满判满逻辑写错或数组容量太小检查是否用了(rear1)%MAX_SIZE打印 front/rear 定位出队数据错乱出队时先移动 front 再取数据改成先读取数据再移动指针队列实际还有空间却显示已满没有正确处理取模rear 越界检查所有 rear/front 更新是否带取模链式队列出队后访问出错删除队尾节点后 rear 悬空删除后判断rear 被删除节点修正 rear动态内存申请后没判断为空malloc 失败会返回 NULL每个 malloc 后立即检查返回值数组下标变成负数取模运算时用错了变量类型或符号统一改成(rear - front MAX_SIZE) % MAX_SIZE形式6.2 实战注意事项第一点不要用 size_t 存下标再参与取模。size_t 是无符号类型如果计算出现负数结果会变成很大的正数取模结果完全错误。我见过一个真实案例用for循环配合size_t遍历队列访问到负数下标后程序直接崩溃。如果你需要用下标做减法建议使用int类型或者先加 MAX_SIZE 再取模。第二点内存泄漏在链式队列里比顺序队列更隐蔽。链式队列销毁时如果只 free 头结点和尾节点中间的节点全部漏掉。我习惯用遍历法逐个释放并且释放后把指针置 NULL避免“悬空指针害死人”的经典事故。第三点接口设计要预留返回值。很多教科书示例里的入队函数是void没有返回值满了直接打印提示。这在教学环境可以工程里绝对不行。调用方的逻辑需要知道入队是否成功否则队列满了就把数据悄悄丢掉数据丢失会很难查。所有操作函数的建议签名都是返回 bool配合指针参数带出数据。最后分享一个小习惯我在写队列相关代码时不管逻辑多简单都有一个习惯写完后用一组边界测试数据自测。具体是这么测的先入队元素到满再出队到空再入队一个元素打印每一步的 front、rear 和数据。这组测试能一次性覆盖队满、队空、绕回、单元素等几乎所有边界情况。很多隐藏 bug 都是在“从满到空再来一个”的过程中暴露的。你要是也觉得队列代码简单到不用测可以试着跑一遍这个用例多半会有意外的收获。
队列这东西在数据结构里属于最基础、却也是实际工程里出场率极高的一批。写过几年 C 的人应该都有体会搞懂链表、栈、队列这三板斧再去碰操作系统、网络协议栈或者消息中间件很多抽象概念瞬间就有了落点。今天想结合我自己的实战经验把“队列Queue的C语言实现”这件事从头到尾捋一遍从最简单的数组模拟开始到环形队列、链式队列再到实际开发里容易踩的坑把这一个点彻底讲透。这篇文章适合正在学数据结构的同学、准备面试的开发者也适合工作中需要自己封装底层数据结构的嵌入式或后端工程师。不管你现在在哪个阶段只要能跟着敲一遍代码队列从理论到实践这一关就算过了。1. 队列是什么从生活场景到程序世界的先进先出队列的核心规则一句话就能说完先进先出First In First Out简称 FIFO。这和栈的先进后出正好相反。生活中最常见的例子就是排队买饭先到的人先打饭后到的人只能排在后面。在程序世界里队列做的事情和这个一模一样先进入队列的数据元素先被取出。1.1 队列的两个关键操作视角学习队列时很多人只记住了“入队”和“出队”两个词但真正理解队列必须从三个维度看队头front、队尾rear、以及数据元素的流动方向。入队enqueue只允许在队尾添加元素新元素永远排在最后面。出队dequeue只允许从队头移除元素最先进入的元素最先被处理。查看队头peek/front只读取队头元素但不移除这个操作在实际业务中非常常用比如消息队列里“看一眼下一条是什么”的场景。从这个设计能看出来队列天然就是一个“缓冲地带”。生产者把数据塞进队尾消费者从队头取数据两边互不干扰。这种解耦思路是队列在系统设计中价值最大的地方。1.2 两种存储结构顺序队列 vs 链式队列用 C 语言实现队列第一步要选存储结构。两条路线各有各的舞台。顺序队列底层是一块连续的内存空间通常用数组实现。优点是内存紧凑、缓存友好、随机访问快缺点是在普通数组实现下队头出队后留下的空间没法复用需要额外的取模运算或数据搬移设计才能绕过去。链式队列底层用链表节点每个节点包含数据域和指向下一个节点的指针。优点是可以无痛扩容不会出现“数组满了但队头还有空位”的尴尬缺点是多了一个指针开销并且每次入队要动态分配内存在实时性要求高的场景里可能造成性能抖动。实际工程里两种队列都很常见。嵌入式设备里常用环形数组队列因为内存是固定的不能随便 malloc而通用服务器程序里链式队列更灵活因为业务规模可能随时膨胀。没有绝对的好坏只有适不适合场景。2. 顺序队列的内存模型与初始实现顺序队列用数组实现需要关注的核心变量有四个存储元素的数组、容量、队头位置、队尾位置。很多教材给的代码是一个结构体包着五个成员看起来复杂其实拆开看就清楚了。2.1 数组模拟队列的基础版先写一个最朴素版本。这个版本的功能是完整的但存在严重缺陷后面会详细说。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标指向最后一个元素的下一个位置 } Queue; // 初始化队列 void initQueue(Queue *q) { q-front 0; q-rear 0; } // 判断队列是否为空 bool isEmpty(Queue *q) { return q-front q-rear; } // 判断队列是否已满 bool isFull(Queue *q) { return q-rear MAX_SIZE; } // 入队 bool enQueue(Queue *q, int value) { if (isFull(q)) { printf(队列已满无法入队\n); return false; } q-data[q-rear] value; q-rear; return true; } // 出队 bool deQueue(Queue *q, int *value) { if (isEmpty(q)) { printf(队列为空无法出队\n); return false; } *value q-data[q-front]; q-front; return true; }这个版本用起来很方便front 指向队头元素rear 指向队尾元素的下一个空位入队时数据写到q-data[q-rear]然后 rear 自增出队时读取q-data[q-front]然后 front 自增。判空条件front rear这个条件在初始状态和所有元素出队后都成立逻辑上是自洽的。2.2 基础版的致命缺陷假溢出上面这个版本最大的问题就是“假溢出”。假设队列容量是 5你连续入队 5 个元素再出队 4 个元素此时排序上看起来队列里只剩下 1 个元素但 front 和 rear 的指针已经走到数组末尾rear MAX_SIZE成立再入队就会提示“队列已满”。看清楚这根本不是真的满了数组前面 4 个位置全是空的。这种现象就叫假溢出。假溢出的本质是我们只把数组当成了线性空间没有把首尾连接起来。解决思路也很经典把数组想象成一个环形跑道front 和 rear 的位置到了数组末尾后自动绕回开头继续走。这种实现就是环形队列也叫循环队列。3. 环形队列解决假溢出的经典方案环形队列是顺序队列在工程实践中的标准形态。它用取模运算实现下标绕回核心逻辑不复杂难就难在边界条件的处理上。写这块代码的时候我踩过不少坑这次直接把每个关键点都摊开讲。3.1 环形队列的核心思想环形队列依然是数组只是在指针移动时加了一层取模逻辑。队尾指针更新公式变为q-rear (q-rear 1) % MAX_SIZE;队头指针同理q-front (q-front 1) % MAX_SIZE;比如容量是 5rear 当前在 4入队后 rear 就变成(4 1) % 5 0绕回数组开头。下一个问题是判空和判满。判空仍然是front rear。但如果判满也写成front rear就会和判空发生冲突。考虑一个容量为 5 的环形队列从空开始不断入队当第 5 个元素入队后rear 移动了 5 次正好又回到 front 的位置此时front rear但队列实际是满的。这就导致“空”和“满”无法区分。解决这个矛盾的方案有三种牺牲一个存储单元当(rear 1) % MAX_SIZE front时认为队列满。这意味着队列最多只能存MAX_SIZE - 1个元素让 rear 永远不追上 front。增设计数器用 size 变量记录元素个数入队加一出队减一。空和满就看 size 是 0 还是 MAX_SIZE。增设标志位用 flag 变量区分是删除导致的相等还是插入导致的相等。教科书里最常用的是方案一因为它不浪费额外变量。实际工程里方案二更直观避免了空满边界思考。我这里先重点讲方案一因为它是理解整个环形队列的关键所在。3.2 完整实现结构体定义、初始化、判空判满这里给出一个完整的环形队列实现后面所有代码都是围绕这一版展开的。#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 5 typedef struct { int data[MAX_SIZE]; int front; // 队头下标指向队头元素 int rear; // 队尾下标指向队尾元素的下一个位置 } CircularQueue; // 初始化 void initQueue(CircularQueue *q) { q-front 0; q-rear 0; } // 判空 bool isEmpty(CircularQueue *q) { return q-front q-rear; } // 判满牺牲一个存储单元 bool isFull(CircularQueue *q) { return (q-rear 1) % MAX_SIZE q-front; } // 获取当前队列元素个数 int queueSize(CircularQueue *q) { return (q-rear - q-front MAX_SIZE) % MAX_SIZE; }这里queueSize的计算公式需要重点理解。因为 rear 和 front 谁大谁小不确定所以不能直接用q-rear - q-front而是先加 MAX_SIZE 再取模保证结果落在 0 到 MAX_SIZE-1 之间。这是环形队列里最容易被写错的一行代码建议直接记下来。3.3 入队、出队、获取队头元素入队和出队的实现关键是操作顺序和取模运算。// 入队 bool enQueue(CircularQueue *q, int value) { if (isFull(q)) { printf(队满入队失败\n); return false; } q-data[q-rear] value; q-rear (q-rear 1) % MAX_SIZE; return true; } // 出队 bool deQueue(CircularQueue *q, int *value) { if (isEmpty(q)) { printf(队空出队失败\n); return false; } *value q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return true; } // 获取队头元素 bool peekFront(CircularQueue *q, int *value) { if (isEmpty(q)) { printf(队空无法获取队头元素\n); return false; } *value q-data[q-front]; return true; }入队的过程拆开看就是三步先判断满再把数据写到 rear 位置最后让 rear 绕圈走一步。出队类似先判断空读取 front 位置数据再让 front 绕圈走一步。我在实际写代码时出队函数有一段小纠结到底是先读取数据再移动 front还是先移动 front 再读取数据答案必须选前者。如果先移动 front第二次出队时读到的就是后一个元素数据全乱了。这个顺序问题在链式队列里同样存在后面会再提到。3.4 关键边界条件为什么牺牲一个存储单元很多人刚接触环形队列时不理解“牺牲一个存储单元”这个操作总觉得浪费。我换个方式解释。想象一个圆桌桌上摆了 5 个座位但没有编号。两个人在玩一个游戏一个人只能往顺时针方向移动另一个人只能逆时针方向移动两个人不能在同一个位置。这两个人的位置如果相同就说明“追尾了”。front和rear就是这两个人。front 负责从队头消费位置rear 负责从队尾生产位置。当 rear 追上 front 时队列确实满了。但在环形结构里满和空都表现为两个指针重合如果不牺牲一格就无法判断到底是谁先占了那个位置。牺牲一格的意思是rear 永远不允许指向 front 的位置当(rear 1) % MAX_SIZE front时就强制停止入队。这样队列最多存储MAX_SIZE - 1个元素。以容量 5 为例最多存 4 个。多出的那一格就像一个“安全隔离带”把满和空这两个状态彻底分开了。如果不想牺牲这一格就用计数器方案。这个方案很直接typedef struct { int data[MAX_SIZE]; int front; int rear; int size; } CountQueue; bool isFull(CQueue *q) { return q-size MAX_SIZE; } bool isEmpty(CQueue *q) { return q-size 0; }入队时q-size出队时q-size--。不用再绕脑子理解取模边界了。工程里如果内存不是卡得特别死我反而更推荐这种方式因为团队协作时别人读你的代码不会迷路。4. 链式队列不固定容量的另一种选择环形队列的容量是写死的在嵌入式、操作系统内核这些内存受限场景里没问题。但如果你写的是一个通用服务业务高峰期和低峰的访问量可能相差几百倍固定容量就不好办了。这时候链式队列上场它不限制元素个数队列能长能短动态适应。4.1 链式队列的结构设计链式队列的每个节点是一个链表节点有两个指针一个指向队头一个指向队尾。这里有一个常见设计分歧队头用头结点还是直接指向第一个数据节点。二叉树的兄弟都知道链式队列空不空、入队出队时头尾指针怎么变化这问题如果不画图光靠脑子想很容易漏。标准做法是带头结点。头结点是哨兵不存数据只作为标记。这样做的最大好处是空队列和非空队列的入队操作可以统一处理不需要分支判断。结构体定义如下typedef struct Node { int data; struct Node *next; } LinkNode; typedef struct { LinkNode *front; // 队头指针指向头结点 LinkNode *rear; // 队尾指针指向最后一个节点 } LinkQueue;注意这里front和顺序队列里的 front 含义不同。顺序队列的 front 是一个下标链式队列的 front 是一个指向头结点的指针。头结点的 next 才指向真正的队头元素。4.2 完整实现初始化、入队、出队、释放初始化时创建头结点front 和 rear 都指向头结点。// 初始化链式队列 bool initLinkQueue(LinkQueue *q) { q-front (LinkNode *)malloc(sizeof(LinkNode)); if (q-front NULL) { return false; } q-front-next NULL; q-rear q-front; return true; }入队操作在队尾插入新节点。这里发现一个细节因为入队只动 rear所以尾插的代码非常短。如果要入队第一个元素rear 本来就指向头结点把新节点挂到 rear-next 上然后移动 rear照样成立。// 入队 bool enLinkQueue(LinkQueue *q, int value) { LinkNode *newNode (LinkNode *)malloc(sizeof(LinkNode)); if (newNode NULL) { printf(内存申请失败入队失败\n); return false; } newNode-data value; newNode-next NULL; q-rear-next newNode; q-rear newNode; return true; }出队要删除的是头结点之后的第一个节点。这里有一个很容易翻车的点如果要删除的节点恰好是队尾节点那么删除后 rear 指针就成了悬空指针。所以出队必须加一个判断如果出队后队列为空要把 rear 重新指向头结点。// 出队 bool deLinkQueue(LinkQueue *q, int *value) { if (q-front q-rear) { printf(队列为空出队失败\n); return false; } LinkNode *temp q-front-next; *value temp-data; q-front-next temp-next; if (q-rear temp) { q-rear q-front; } free(temp); return true; }释放整个队列时要从头结点往后逐个释放不能只释放头结点。这里我习惯用一个遍历指针循环来释放简单直接。// 销毁队列 void destroyLinkQueue(LinkQueue *q) { LinkNode *curr q-front; while (curr ! NULL) { LinkNode *next curr-next; free(curr); curr next; } q-front NULL; q-rear NULL; }链式队列的扩容过程完全依赖 malloc 和 free明显的好处是理论上没有容量上限只要内存够数据可以一直往里加。坏处是每个节点多了 8 字节64 位系统指针大小的额外开销而且频繁 malloc/free 会产生内存碎片。所以链式队列更适合节点数量不确定、波动大的场景。5. 队列的应用场景与面试常考变形队列远不只是教学用的实际工程中用到的队列比很多人想象中要多得多。写到这里我觉得有必要把“学了队列能干嘛”这件事说清楚。5.1 实际应用领域1. 任务调度与消息缓冲CPU 任务调度是操作系统教科书里第一个用到队列的地方。多个进程排队等待 CPU 时间片新来的进队列尾部当前执行完的进程决定是重新排队还是出队。消息中间件更典型生产者发的消息进队列消费者独立地从队列头取消息通过队列实现生产者消费者解耦。2. 广度优先搜索 BFS图算法里BFS 的实现必须用队列。从起点开始把相邻节点依次入队再从队头取节点继续扩展。这个过程天然就是 FIFO先发现的节点先被处理保证按层扩展。换个深度优先的话BFS 就变成 DFS 了。3. 缓冲区Buffer嵌入式开发里串口和网络数据的接收通常会用环形队列做缓冲区。比如传感器数据不断进来主循环抽空处理中间用队列存住。如果不用队列数据来了处理不了就会丢用了队列就有了缓冲时间。4. 线程池任务队列线程池实现里一般有一个任务队列新任务先入队空闲线程从队头取任务执行。这本质上就是一个多生产者多消费者的队列模型。5.2 双端队列和循环队列的变形面试时经常在队列基础上出变形题最常遇到的有两种双端队列deque两端都可以入队和出队。底层实现可以用带头尾指针的双向链表更极致的实现是用数组加头尾下标此时就是“循环双端队列”。LeetCode 上的“滑动窗口最大值”就是依托双端队列的经典题。用循环队列实现栈或其他结构这类问题考的是对两种结构本质的理解。以循环队列为底层实现一个类似栈的结构核心思路是入栈时在队尾插入出栈时把除队尾外的所有元素出队再重新入队最后队尾元素就是栈顶出队返回。空间换时间但逻辑上很有意思。面试时做这类题重点不是代码多炫而是能把空、满、边界条件表达清楚。对出队导致 rear 变化的情况如果能主动说明“这里要处理链表尾节点删除后指针修正”面试官就会知道你真正理解了。6. 常见问题与排查技巧实录前面讲的是原理和代码最后这部分我想把平时排查问题时积累的经验分享出来。这些问题我踩过也在帮别人 review 代码时见过太多次。6.1 问题速查表现象可能原因解决建议入队总是提示队满判满逻辑写错或数组容量太小检查是否用了(rear1)%MAX_SIZE打印 front/rear 定位出队数据错乱出队时先移动 front 再取数据改成先读取数据再移动指针队列实际还有空间却显示已满没有正确处理取模rear 越界检查所有 rear/front 更新是否带取模链式队列出队后访问出错删除队尾节点后 rear 悬空删除后判断rear 被删除节点修正 rear动态内存申请后没判断为空malloc 失败会返回 NULL每个 malloc 后立即检查返回值数组下标变成负数取模运算时用错了变量类型或符号统一改成(rear - front MAX_SIZE) % MAX_SIZE形式6.2 实战注意事项第一点不要用 size_t 存下标再参与取模。size_t 是无符号类型如果计算出现负数结果会变成很大的正数取模结果完全错误。我见过一个真实案例用for循环配合size_t遍历队列访问到负数下标后程序直接崩溃。如果你需要用下标做减法建议使用int类型或者先加 MAX_SIZE 再取模。第二点内存泄漏在链式队列里比顺序队列更隐蔽。链式队列销毁时如果只 free 头结点和尾节点中间的节点全部漏掉。我习惯用遍历法逐个释放并且释放后把指针置 NULL避免“悬空指针害死人”的经典事故。第三点接口设计要预留返回值。很多教科书示例里的入队函数是void没有返回值满了直接打印提示。这在教学环境可以工程里绝对不行。调用方的逻辑需要知道入队是否成功否则队列满了就把数据悄悄丢掉数据丢失会很难查。所有操作函数的建议签名都是返回 bool配合指针参数带出数据。最后分享一个小习惯我在写队列相关代码时不管逻辑多简单都有一个习惯写完后用一组边界测试数据自测。具体是这么测的先入队元素到满再出队到空再入队一个元素打印每一步的 front、rear 和数据。这组测试能一次性覆盖队满、队空、绕回、单元素等几乎所有边界情况。很多隐藏 bug 都是在“从满到空再来一个”的过程中暴露的。你要是也觉得队列代码简单到不用测可以试着跑一遍这个用例多半会有意外的收获。
