队列这个数据结构我估计每一位接触过编程的人都被它“折磨”过但这又说不上痛苦因为它背后的逻辑非常朴素先进先出。排队打饭、排队取号、打印机任务排队全是一个道理。但真要落到代码上很多人会卡在“顺序存储队列”和“链式存储队列”的具体实现上尤其是循环队列的边界条件、链式队列的指针更新稍不注意就是一堆奇怪的bug。这篇文章就围绕两种存储结构的完整代码实现展开。我会把为什么这么写、代码背后的设计逻辑、以及实际写代码时容易踩的坑都梳理一遍。非常适合正在学数据结构、准备课程实验或者面试前想快速复盘队列实现的朋友。1. 搞懂队列的本质再写代码顺序存储和链式存储到底差在哪1.1 先弄明白队列到底是个什么结构队列的全名叫“先进先出线性表”它本质上是一种操作受限的线性表。线性表意味着数据元素之间存在一对一的线性关系但队列额外限定了操作位置只能在队尾插入在队头删除。这个约束让它天然适合处理“先到先服务”的场景。比如操作系统里的进程调度多个进程排队等待CPU就是典型的FIFO逻辑。再比如淘宝秒杀活动里的请求队列也是把大量请求先放入队列再由服务端按顺序处理。队列这种结构本身不复杂但它的实现方式直接决定了队伍能排多长、插入和删除的效率高不高以及内存占用是否可控。从存储物理结构上队列可以分成两大类一类是顺序存储用一段连续的数组内存来存放数据另一类是链式存储用动态分配的、物理上可能零散的内存块通过指针串联起来。这两种实现方式各有利弊没有绝对的最优只有最适合场景的那一个。1.2 两种存储结构的本质差异连续内存和离散内存顺序存储队列说白了就是“数组里面画个圈”。它申请一段连续空间然后用两个变量分别记录队头和队尾的位置。入队就是往数组里写入一个元素顺便把队尾指针往后挪出队就是把队头位置的元素取出来再把队头指针往后挪。整个过程中不需要申请和释放内存效率非常稳定。链式存储队列就不一样了。它的每一个元素都是动态malloc出来的节点节点里除了保存数据还要存一个指向下一个节点的指针。队列里只保留两个指针变量一个指向队头节点一个指向队尾节点。入队时创建一个新节点挂到链尾出队时摘掉链头的节点并释放内存。这种方式的优点是不需要预先分配大量内存缺点是有malloc和free的开销。这两种结构在面试和实际开发里都很常见。理解它们的核心差异是写对代码的前提。下面我分别把两套完整实现讲透。2. 顺序存储队列完整实现数组、循环和取模三件套2.1 为什么顺序存储一定要用循环队列很多初学者第一次写顺序存储队列时会这样想用数组加两个下标变量入队时rear写入出队时front取出这样不就完了吗确实这个逻辑在最基础层面没有问题。但你要是真的在实现了之后多入队、出队几次很快就会碰到一个尴尬的情况——假溢出。假溢出的意思是数组尾部的空间已经用完了rear已经指向了最后一个位置但数组头部还有大把空闲位置却仍然无法入队。因为rear再往后走就越界了而出队操作只会让front往后走不会自动把前面空出来的位置回收给rear继续使用。这就导致数组明明没有装满却已经“排不下”任何新元素了。解决思路也很直接把数组逻辑上首尾相接当成一个顺时针环来用。rear移动到数组末尾后如果数组头部还有空间就让rear重新回到下标0的位置。要实现这个“绕圈”效果最常用的手段就是取模运算(rear 1) % MAXSIZE只要数组长度MAXSIZE事先定好运算完下标自然就在合法的整数范围内循环了。2.2 结构体设计与初始化顺序存储队列的结构体设计核心是两个下标变量加上一个容量足够的数组。这里我用C语言实现因为数据结构课程和考研算法刷题基本都用C来写底层逻辑清楚能直接体现指针和内存操作。#define MAXSIZE 5 typedef int QElemType; typedef struct { QElemType data[MAXSIZE]; int front; int rear; } SqQueue;front的含义要统一我这里约定front指向队头元素所在的位置rear指向队尾元素的下一个位置。也就是说队头元素是data[front]队尾元素是data[rear - 1]最后一个有效元素之后的位置才是rear指向的地方。这个约定非常重要因为后面所有的判空判满和长度计算都依赖这个定义。初始化时队列为空front和rear都从0开始即可不需要区分任何位置直接置零。void InitQueue(SqQueue *Q) { Q-front 0; Q-rear 0; }这里有一个容易忽略的点初始化函数的参数必须传结构体指针而不是结构体本身。因为我们需要在函数内部修改调用者传进来的变量如果直接传SqQueue Q那只是拷贝了一份函数内改完不会影响外面的队列。这是C语言入门时最容易犯的错写队列代码时更是高发。2.3 判空判满条件那一个被牺牲的存储单元有了循环队列紧接着的问题就是怎么判断队列是空还是满用现实中的环形蓄水池来类比如果水池里水满了和空池子的“水位”标识在同一个位置那你无法通过水位判断池子的状态。在循环队列里如果规定front指向队头元素rear指向队尾元素的下一个位置那么队空条件是front rear这很自然。但队满条件呢如果让队列真真正正装满即数组每个下标都存了数据那么rear经过取模运算绕一圈之后也会等于front。这样一来队满和队空就无法区分了。所以最经典、使用最多的方案是牺牲一个存储单元。也就是队列中最多只存放MAXSIZE - 1个元素留出一个空位用于区分状态。这样队满条件就变成了(rear 1) % MAXSIZE front。int QueueEmpty(SqQueue Q) { return Q.front Q.rear; } int QueueFull(SqQueue Q) { return (Q.rear 1) % MAXSIZE Q.front; }这个牺牲是值得的。多留一个空位换来的是O(1)的判满判断不需要额外维护计数器也不需要在每次入队出队时更新额外的标志位。而且在实际项目中队列的容量通常不是那种“一个位置都不能浪费”的资源紧张场景一个空位带来的损耗几乎可以忽略。2.4 入队出队完整代码实现与测试入队操作的完整逻辑是先判断队列是否已满如果满了直接返回失败如果没满把元素写入rear指向的位置然后让rear往后移动一位移动时用取模运算处理“绕圈”的逻辑。int EnQueue(SqQueue *Q, QElemType e) { if ((Q-rear 1) % MAXSIZE Q-front) { return 0; } Q-data[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return 1; }出队操作则要反过来先判断队列是否为空如果为空直接失败如果不为空从front指向的位置取元素然后让front也向后移动一位。int DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear) { return 0; } *e Q-data[Q-front]; Q-front (Q-front 1) % MAXSIZE; return 1; }注意这里的出队函数我们通过指针参数e把弹出的元素带出去。这个设计是为了让函数返回值专门用于表示操作成功或失败的状态而不是既返回状态又返回数据。这种“状态和值分离”的思想在C语言接口设计里非常实用后续写复杂代码时会经常用到。除此外还有一个经常用来验证队列操作正确性的辅助函数返回队列中当前元素的个数。计算公式是(rear - front MAXSIZE) % MAXSIZE。int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; }为什么这个公式是对的当rear在前大于front时两者相减直接就是长度当rear因为循环绕到了front后面时相减是负数加上MAXSIZE后取模就把负值修正过来了。感兴趣的读者可以用一个具体的MAXSIZE和不同front、rear组合手动推演一遍这个过程对理解循环队列帮助极大。2.5 区分队空队满的另两种思路牺牲一个存储单元不是唯一的方案。另外还有两种比较常见的做法第一种方案是额外加一个size字段每次入队时size加1出队时size减1。判空条件是size 0判满条件是size MAXSIZE。这样数组可以塞满MAXSIZE个元素不浪费任何空间但代价是每次入队出队都要多维护一个size变量。第二种方案是额外加一个tag字段初始为0。一次成功的入队操作会把tag置为1一次成功的出队操作会把tag置为0。当front和rear相等时如果tag为1说明最后一次操作是入队因此队列是满的如果tag为0说明最后一次操作是出队因此队列是空的。在实际工程里这两种方案都能见到。但如果追求简洁的代码和零额外状态的维护牺牲一个存储单元依然是我最推荐的做法。它虽然让数组最大存储量从MAXSIZE减少到MAXSIZE-1但逻辑最简单也最不容易出错。3. 链式存储队列完整实现头结点、尾指针和动态内存3.1 为什么用头结点链式存储队列的核心思想是用链表的节点来存数据队列本身只保留队头指针front和队尾指针rear两个节点指针。这里有一个设计选择要不要为队列单独创建一个头结点。我的建议是带头结点原因有两点。第一带头结点之后空队列的判断变得极其统一front和rear都指向头结点。第二出队时无须单独处理“队列中只剩一个元素”的复杂分支。如果不带头结点那么当队列为空时front和rear都是NULL。第一次入队时你不仅要创建新节点还得同时修改front和rear的指向这就在入队函数里引入了一个“如果队列为空则需要特殊处理”的分支。带头结点后空队列的front和rear都指向头结点普通入队操作永远只是修改链尾节点的next和rear的指向完全不需要判断队列是不是第一次入队。这就让代码的清晰度上了一个档次。3.2 结构体设计与初始化链式队列需要两种类型的结构体。第一种是节点结构体包含数据域和指针域。第二种是队列结构体里面只有两个节点指针。typedef int QElemType; typedef struct QNode { QElemType data; struct QNode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue;初始化时方法如下申请一个头结点让front和rear都指向它然后把头结点的next置为空。void InitQueue(LinkQueue *Q) { Q-front Q-rear (QNode *)malloc(sizeof(QNode)); if (!Q-front) { exit(EXIT_FAILURE); } Q-front-next NULL; }malloc之后一定要检查返回值这样能防止内存分配失败时继续对NULL指针操作而导致的崩溃。很多刚学C的同学在写链表相关代码时最容易忽略这一步但一旦遇到资源紧张场景野指针的代价就是直接段错误。3.3 入队出队销毁的完整代码实现链式入队的基本逻辑非常直观申请一个新节点把数据写进新节点把新节点挂到当前链尾节点之后然后更新rear指针指向新节点。新节点一定没有后继所以next置为NULL。void EnQueue(LinkQueue *Q, QElemType e) { QNode *s (QNode *)malloc(sizeof(QNode)); if (!s) { exit(EXIT_FAILURE); } s-data e; s-next NULL; Q-rear-next s; Q-rear s; }出队的流程就需要格外谨慎了。先判断队列是否为空这里的判断逻辑和顺序队列不同带头结点的链式队列为空时front和rear都指向同一个头结点。接着取出的是front-next这个节点也就是第一个实际存放数据的节点。取完数据后让front-next指向它的下一个节点。最后释放这个节点。这一系列操作里有个隐藏细节如果被删除的节点是队列最后一个数据节点rear还指向它必须在释放前将rear指回头结点。int DeQueue(LinkQueue *Q, QElemType *e) { QNode *p; if (Q-front Q-rear) { return 0; } p Q-front-next; *e p-data; Q-front-next p-next; if (Q-rear p) { Q-rear Q-front; } free(p); return 1; }这段代码的精髓在最后三行先判断当前删除的节点是不是队尾节点如果是则要把rear回收到头结点的位置。这是因为rear原本指向的节点即将被free如果不让rear指回头结点那么删除完后rear就变成了一个指向已释放内存的悬空指针再想使用队列时就会出现严重的内存错误。销毁队列的函数也很重要。队列作为一个整体被销毁时需要从头到尾释放每一个节点包括头结点。用循环逐步拿取下一个节点并free当前节点即可。void DestroyQueue(LinkQueue *Q) { QNode *p Q-front; while (p) { Q-front p-next; free(p); p Q-front; } }销毁完成后最好把front和rear都置为NULL以免留下悬空指针。这部分虽然看起来只是代码的收尾工作但它直接关系到程序的健壮性尤其是在大型项目中内存泄漏和悬空指针的问题往往就出在这些不起眼的细节上。3.4 出队时尾指针更新这个隐蔽细节链式队列里最容易写错的就是尾指针更新。前面说过当删除最后一个节点时必须让rear等于front。很多初学者写出的出队代码只有前几行即取出节点、修改front-next、free节点而没有做尾指针回收。我们来推演一下这个错误会带来什么后果。队列里有且仅有一个数据节点Afront指向头结点rear指向节点A。执行出队操作后如果只执行front-next p-next那么front-next就被置为节点A的next而A的next原本是NULL。接着free掉A。这时候front-next就是NULL从链表的角度来看队列确实空了。但是rear仍然指向已经被释放的A。下一次入队时Q-rear-next s这一行会尝试往一个已经释放的内存块里写指针这就是经典的use-after-free错误程序大概率直接崩溃。所以请记住一条铁律链式队列出队时只要删除的是队尾节点就必须重置rear。4. 顺序存储和链式存储的核心对比与选型参考4.1 十个维度的对比表写到这一步两种实现的代码都已经完整落地了。接下来把它们放在一起做个横向对比方便实际使用时快速决策。对比维度顺序存储队列链式存储队列底层存储连续数组静态分配动态节点链式连接空间上限受限于数组大小MAXSIZE受限于可用堆内存空间利用率最多用MAXSIZE-1个位置可能有空位每个元素一次malloc无结构浪费入队时间复杂度O(1)直接写数组O(1)只需修改指针出队时间复杂度O(1)直接读数组O(1)只需修改指针扩容难度困难需要整体迁移数据简单随时动态申请节点内存管理复杂度无动态分配无需手动释放涉及malloc和free隐患较多缓存友好性极高连续内存命中率高较差节点内存通常不连续判空判满方式需要处理循环边界只需要比较front和rear是否相等实际应用消息缓冲、任务队列、消息循环网络包缓存、日志队列、灵活长度的等待队列4.2 实际场景中怎么选如果是队列长度基本确定、且对读写性能有极高要求的场景顺序存储队列绝对优先。比如操作系统内核里的环形缓冲区、嵌入式环境下的消息队列它们的队列长度在设计时就已经定死使用数组实现还避免了频繁malloc带来的不确定时延。如果是队列长度波动剧烈、无法预估上限、或者每个任务的需求内存不一的场景链式存储队列更合适。比如某后台服务接收客户端上传的任务任务数量可能从0暴增到数十万用固定数组很容易浪费空间或造成无法扩容的困境而链式队列可以按需申请内存即使队列很长也只需要承担相应的节点内存占用。还有一种折中方案也值得了解一下动态数组队列。即底层数组不够用时重新申请更大的数组并迁移数据逻辑上保留了顺序存储的高效性同时具备一定的动态扩容能力。很多高级语言标准库里的队列就是这么实现的。5. 写队列代码最常见的坑与排查实录5.1 循环队列的边界条件三连错如果在写顺序存储队列时入队正常但队列永远显示“已满”大概率问题出在判满条件上。实际项目里常犯的三个典型错误忘记用取模导致rear指向数组末尾后再加1就越界取模时误写成MAXSIZE - 1以及执行完出队时忘记同步更新队列长度变量。我一个一个说。第一个错误代码写的是Q-rear 1 Q-front这在rear未绕回时有效但一旦rear走到数组尾部下一次入队就会越界。第二个错误有些人会下意识想“数组下标从0到MAXSIZE-1所以取模应该用MAXSIZE-1”但循环队列的周期就是MAXSIZE下标绕一圈需要正好回到0必须用MAXSIZE取模。第三个错误比较隐蔽一般出现在额外维护了size的队列里忘记更新size会导致判空判满全盘崩溃。排查这类问题有一个很有效的办法借助一个固定的MAXSIZE比如5手动列出所有可能的front和rear组合逐一核验QueueLength的计算结果是否符合预期。纸上推演一遍比看半天代码更快。5.2 链式队列的内存泄漏和野指针链式队列的内存问题主要集中在三处。第一处是入队后忘记设置新节点的next为NULL。如果不设置这个新节点被挂到链尾时它的next可能是一个随机值从而让队列的链表结构变得混乱。第二次遍历或者销毁队列时程序很可能遍历到一个非法地址导致崩溃。第二处是出队时忘记free节点。这个错误在功能上往往不会立刻暴露因为你只是把节点从队列中“摘”了出来队列逻辑还是对的。但如果频繁入队出队内存就持续增长到最后系统内存被耗尽程序才以一种极其诡异的方式挂掉。排查方法是用valgrind或者AddressSanitizer运行一遍内存泄漏一目了然。第三处是销毁队列后没有把front和rear置为NULL。销毁函数执行完后队列本身还存在于栈上如果还有代码继续调用入队出队函数就会操作一块已经被释放的内存产生非常难排查的野指针问题。正确的做法是在释放完所有节点后手动添加Q-front NULL; Q-rear NULL;。5.3 一个经典错误的完整复盘删除最后一个节点后尾指针没更新这个场景我在不同项目里见过很多次几乎每隔一段时间就会有人来问“为什么链式队列删除最后一个元素后再入队就崩溃”。我把完整的错误流程复盘在这里。假设队列中有且只有一个元素A节点A的数据为100。执行两次连续出队。第一次出队时队列判断非空p指向节点A取出的数据是100front-next置为NULL此时rear依然指向节点A然后free(A)。第一次出队调用的返回值是1从外部看队列已经变空执行得很顺利。第二次出队时front和rear并不相等因为我们根本没有让rear回收到头结点所以这时真正的问题已经埋下。再出队时p等于front-next而front-next已经是NULL解引用NULL指针就会直接段错误。也就是说第一次出队其实已经破坏了队列结构但程序没有立刻暴露问题直到第二次出队或者某次入队才突然崩溃。这种“延迟暴露”的Bug最难缠因为出问题的地方往往离真正出错的位置很远。正确的做法你一定已经牢牢记住了删除节点前先判断Q-rear p如果成立就先把rear指回头结点。写一遍代码用了不到三个字符的判断却是整个链式队列里最值钱的三个字符。6. 写在最后我的实操体会代码写到这个份上两种队列的实现思路已经非常清晰了。我个人在实际项目中常用的原则是凡是队列长度稳定且追求极致性能的场景优先选顺序存储凡是队列长度波动大、需要动态伸缩的场景优先选链式存储。不要为了“显得高级”而给简单问题增加复杂度。另外一个小建议无论用哪一种存储结构写完代码后都一定要回头检查边界条件。顺序队列检查满、空、长度为0、长度为MAXSIZE-1这四种状态链式队列检查空队列出队、单节点出队、连续入队出队混用这三个关键动作。把这些边界测一遍队列代码的可靠性基本就有保证了。
