队列这个东西只要写过几年代码的人基本天天都在跟它打交道。线程池的任务排队、操作系统的消息缓冲、网络请求的流量削峰背后全是队列的变形应用。但很多朋友跟我说顺序队列、链式队列这种基础概念上课听的时候觉得懂了真到用的时候又模模糊糊尤其是碰上“假溢出”这种词直接一头雾水。这篇就把这两种最经典的队列实现掰开揉碎讲清楚从原理到代码从选型到避坑一篇到位。不管你是刚学数据结构的学生还是工作几年想回头补基础的后端开发或者做嵌入式、游戏逻辑时要自己管理任务队列的工程师这篇都值得你花十来分钟看完。理解了队列的本质后面看阻塞队列、消息中间件这些上层建筑会轻松很多。1. 队列到底解决什么问题队列的核心思想一句话就能讲完先进先出FIFOFirst In First Out。就像去银行柜台办事先取号的人先被叫到后到的老老实实排在后面。这个在生活里天经地义的规则放到计算机世界里恰恰是很多系统能正常运转的基石。1.1 三种典型的“屁股决定脑袋”场景排队等待类场景是所有队列应用里最直观的。打印机任务、CPU的任务调度、外卖平台的订单分配本质上都是把请求丢进一个队列然后按照到达顺序逐个处理。这类场景的核心诉求是公平先来后到不能乱。如果哪天打印机突然先打了后提交的文件你一定会觉得这系统有bug。生产者消费者解耦是另一个经典场景。系统的某一部分负责产生数据生产者另一部分负责处理数据消费者。两边的速度天然就不匹配可能是生产者瞬间爆发产生大量数据也可能是消费者处理一条数据需要耗时很久。没有队列做缓冲生产者就必须等消费者处理完才能产生下一条整个系统的吞吐量会被死死按住。有了队列生产者只管往里面塞消费者按自己的节奏取两边谁也不用等谁。广度优先遍历BFS是算法领域最依赖队列的场景。不管是走迷宫求最短路径、社交网络找几度人脉关系还是搜索引擎的网页爬取都需要先把当前层的所有节点处理完再去处理下一层。这种逐层扩散的顺序只有队列能天然契合。我用一个生活化的类比你往平静的水面丢一颗石子波纹是一圈一圈往外扩散的每一圈都完整地展开后才轮到下一圈这就是BFS而实现这个扩散过程的存储结构就是队列。1.2 队列的三个核心认知第一队列是一种操作受限的线性表。这意味着它不像数组那样支持按下标随机访问你不能说“帮我把队列里第3个元素改成5”它就是只能从尾部加入、从头部取出。这个限制不是缺陷而是队列存在的意义。第二队列的“长度”不是固定不变的。随着入队和出队的交替进行数据不断流入流出队列始终处于动态变化之中。这也是为什么后面讲实现时顺序队列会面临“假溢出”链式队列会更灵活的原因。第三队列只有两个主要操作入队enqueue和出队dequeue外加几个辅助操作判空、取队头但不删除。这世上不存在“队列的排序算法”、“队列的查找算法”因为队列压根不关心内部元素谁大谁小它只负责维护“顺序”这件事本身。2. 顺序队列基于数组的直观实现顺序队列就是用一块连续的内存空间数组来存储队列元素。前端时间面试不少候选人一说顺序队列就是“用数组存一下嘛”但真让他写一个能用的实现一半人会在“假溢出”这个坎上翻车。这块是重头戏。2.1 基本结构与头尾指针顺序队列需要三个关键字段存储元素的数组、指向队头的索引 front、指向队尾的索引 rear。初始状态下front 和 rear 都指向数组的起始位置通常为0。入队时把元素放入 rear 指向的位置然后 rear 加1出队时取出 front 指向的元素然后 front 加1。用代码写出来就是这个样子我习惯用 C 语言讲数据结构因为内存布局看得清清楚楚#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int front; // 队头下标 int rear; // 队尾下标 } SeqQueue; // 初始化 void initQueue(SeqQueue *q) { q-front 0; q-rear 0; }到此为止一切都挺顺理成章的。front 和 rear 都往一个方向移动元素存进来取出去逻辑上完全没问题。但这里藏着一个经典的坑。2.2 假溢出顺序队列最经典的设计缺陷假设数组长度为5你依次入队5个元素此时 rear 5数组满了。然后你出队3个元素front 3。现在的情况是数组的前3个位置空着rear 却已经指向了数组末尾。再进行入队操作时rear 1 就超过数组下标范围了会直接数组越界。但问题是明明数组前面还有3个空位啊数组没有真正满只是 rear 走到了尽头。这个现象就叫“假溢出”。我当年第一次学到这的时候觉得这个设计也太蠢了——空间明明没用完却因为指针只能单向移动导致无法继续使用。但仔细一想才发现这恰恰是顺序存储在“操作受限”这条路上的必然结果。数组的物理空间是固定的出队操作把头部空间释放出来了但 rear 指针并不知道“前面空了”它只知道自己的位置。解决假溢出的方案有两个方向。第一个是一旦发现 rear 到顶了就把所有元素整体前移把空位腾到后面来。这个方案简单粗暴但每触发一次就要搬动所有还在队列里的元素时间复杂度是 O(n)出队操作均摊下来就很慢了。第二个方案就是下面要讲的循环队列也是实际工作中真正会用的方案。2.3 循环队列用取模运算盘活整块内存循环队列的思路特别朴素把数组想象成一个首尾相接的圆环。rear 到顶之后如果数组头部有空位就让 rear 绕回下标0继续用。实现只需要一行关键代码rear (rear 1) % MAX_SIZE; front (front 1) % MAX_SIZE;不管 front 和 rear 走到哪只要超过数组边界就取模绕回起点。这样一来数组的每一个位置都可能被反复使用假溢出的问题就消解于无形了。但循环队列引入了一个新的问题怎么判断队列是空还是满因为空队列满足 front rear满队列也满足 front rear当数组完全被占满时rear 绕了一圈又等于 front。空和满成了一个条件这是不能接受的。业界有两种解法。第一种是牺牲一个存储单元。规定 rear 的下一个位置是 front 时即 (rear 1) % MAX_SIZE front就认为队列满也就是说数组中永远有一个位置是空闲的最多存 MAX_SIZE - 1 个元素。这是最常见的做法C STL 的 deque 底层用环形缓冲区时就采用了类似思路。判空条件仍然是 front rear判满条件是 (rear 1) % MAX_SIZE front。第二种是加一个 size 字段记录当前元素个数。入队时 size出队时 size--利用 size 区分空和满。这样能完整利用所有存储空间但多维护了一个变量逻辑稍多一点。我个人建议自己实现时用牺牲一个存储单元的方式逻辑干净也不容易出错。完整的循环队列入队出队代码长这样int enQueue(SeqQueue *q, int val) { if ((q-rear 1) % MAX_SIZE q-front) { printf(队列已满\n); return 0; } q-data[q-rear] val; q-rear (q-rear 1) % MAX_SIZE; return 1; } int deQueue(SeqQueue *q, int *val) { if (q-front q-rear) { printf(队列为空\n); return 0; } *val q-data[q-front]; q-front (q-front 1) % MAX_SIZE; return 1; }注意一个细节循环队列里 front 和 rear 的初始值不一定非得是0只要两者相等队列就是空的。如果你后续要做“队列元素个数”的计算公式是(rear - front MAX_SIZE) % MAX_SIZE。这里一定要加上 MAX_SIZE 再取模因为 rear 可能已经绕过一圈比 front 小直接相减会是负数。2.4 顺序队列的扩容问题固定大小的循环队列有一个天然短板容量写死了。如果 MAX_SIZE 设小了高峰期数据直接丢弃或拒绝入队如果设大了平时又白占内存。所以真正在工程里用顺序队列时往往需要支持动态扩容。扩容的做法是当队列满时申请一块更大的新数组比如原来的2倍然后把旧数组里的元素按正确的队列顺序搬到新数组里。这里有个必须注意的细节不能简单地把旧数组下标对应拷贝因为循环队列的元素物理位置可能是“断开的”front 到数组末尾是一段下标0到 rear 又是一段要把这两段按先后顺序拼起来放到新数组的头部。搬移代码的大致思路int *newData malloc(sizeof(int) * newCapacity); int count (q-rear - q-front oldCapacity) % oldCapacity; for (int i 0; i count; i) { newData[i] q-data[(q-front i) % oldCapacity]; } // 更新 front 0, rear count, 替换底层数组这段逻辑不难但很容易写错属于面试里基础中的基础但又能筛掉一批人的考点。3. 链式队列基于链表的动态实现顺序队列受限于固定容量链式队列就是为了解决这个问题而存在的。链式队列的逻辑和顺序队列非常相似但存储结构完全不同每个元素是一个节点通过指针串起来。3.1 节点设计与指针操作链式队列的每个节点包含数据域和指向下一个节点的指针 next。整个队列需要两个指针front 指向队头节点rear 指向队尾节点。入队在 rear 后面挂新节点出队从 front 取节点。节点定义typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *front; Node *rear; } LinkQueue;这里有一个非常重要的设计细节链式队列通常设置一个头结点。头结点不存储数据只是作为哨兵它的 next 才指向队列的第一个真实元素。为什么不直接让 front 指向第一个元素呢因为如果不带头结点当队列为空时front 和 rear 都要指向 NULL插入第一个元素后front 和 rear 都要指向这个新节点删除最后一个元素后又要把两者置为 NULL。每一种操作都要多一个分支判断“是不是空队列”而且出队删到最后一个节点时还要记得把 rear 也置空否则 rear 就成了悬空指针。带头结点后情况就统一了空队列时 front 指向头结点rear 也指向头结点入队永远在 rear 后面插入出队永远删除 front-next。所有操作的逻辑一模一样不需要额外判断边界分支。这种“用哨兵统一边界条件”的品味在 C 语言这种手写数据结构的语境下非常关键面试时能体现你的工程意识。3.2 链式队列的入队与出队实现入队操作三步走int enQueue(LinkQueue *q, int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (!newNode) return 0; // 内存申请失败 newNode-data val; newNode-next NULL; q-rear-next newNode; // 挂到队尾后面 q-rear newNode; // 更新队尾指针 return 1; }出队操作注意删的是头结点后面的那个节点int deQueue(LinkQueue *q, int *val) { if (q-front-next NULL) { printf(队列为空\n); return 0; } Node *tmp q-front-next; *val tmp-data; q-front-next tmp-next; if (q-rear tmp) { q-rear q-front; // 删除的是最后一个元素同步更新 rear } free(tmp); return 1; }这里有个容易被忽略的细节如果队里只有一个元素出队后 front-next 为空同时 rear 还指着这个已经被删除的节点。如果不把 rear 重新指向头结点下一次入队时就会通过一个悬空指针去挂新节点程序崩溃都算轻的悄悄写坏内存才叫要命。这个边界场景我见过好几个人掉坑里。3.3 链式队列的空间特征与劣势链式队列最大的优势是容量不受限理论上只要内存足够就能一直入队不会出现“假溢出”问题。但它的代价也很明显每个节点都要额外开销一个指针的内存。如果你的队列里存的是小结构体比如一个 int指针的开销可能比数据本身还大内存利用率并不高。频繁的 malloc/free 会造成内存碎片在小内存的嵌入式环境里甚至可能导致内存分配失败。还有一点容易被忽略链式队列的随机性差。它是通过指针逐个跳转的如果你需要遍历队列找某个元素只能从头走到尾CPU 缓存预取的效果也远不如数组连续内存好。在需要高性能、频繁遍历的场景下链式队列不是首选。4. 顺序队列和链式队列的选型到底什么时候用哪个很多朋友学完两种实现脑子里只有一个模糊的印象“数组有上限链表没上限”但这远远不够。选型的本质是在费率、容量、复杂度之间找平衡下面拆解一下。4.1 核心维度对比我整理了一个对比表基本覆盖了两种实现的所有差异点对比维度顺序队列循环队列链式队列存储结构数组连续内存链表节点分散内存容量上限固定或需扩容理论仅受内存限制入队/出队时间复杂度O(1)O(1)访问第二个元素取模计算即可快要 next 跳一次稍慢内存利用率高无额外指针开销较低每个节点多一个指针CPU 缓存友好性连续内存好分散内存差扩容/缩容需要搬移数据O(n)天然支持无需搬移实现复杂度取模边界需小心指针操作容易出错4.2 实战选型建议选顺序队列的场景队列的最大长度可以提前估算且对性能敏感。典型例子是嵌入式系统的串口环形缓冲区——数据量不大几百字节频率很高用数组加头尾指针的循环队列是最标准的做法。FreeRTOS 底层的消息队列实现本质上就是一个基于静态数组的环形缓冲区因为嵌入式环境里内存极其宝贵动态分配是被严格限制的。再比如操作系统的任务就绪队列、网络驱动的收包缓冲区长度都有上限且要求极低的延迟这类场景顺序队列完胜。选链式队列的场景队列长度不可预知或者波动极大。典型例子是某个后台服务的任务队列——平时每分钟几千个任务但大促时可能一秒钟就涌进来几十万个这时候如果预先分配固定容量要么浪费空间要么丢任务。用链式队列内存按需分配即便消息中间件这种场景底层通常也是用可增长的链表结构加锁来实现。另外在 Java 的 LinkedList 同时实现了 Deque 接口用来做队列的时候本质上就是一个链式队列适合需要频繁增删且长度不固定的场景。还有一个比较反直觉的建议如果你用 Java/C/Go 这类高级语言底层容器已经帮你处理好了扩容逻辑比如 Java 的 ArrayDeque 会自动扩容那么即使“逻辑上是顺序队列”你也不用操心手动扩容的复杂度。这种情况下优先选择基于数组的实现性能和缓存友好性都更好。只有在下层没有动态扩容能力、且容量确实无法预估时才应该选链式实现。4.3 延伸线程池里的阻塞队列该怎么选热词里提到了“线程池的阻塞队列选择”这其实是顺序队列和链式队列思想在上层工程里的延展。Java 的 ThreadPoolExecutor 支持多种阻塞队列最常用的三个你理解了底层存储结构就不难选了。ArrayBlockingQueue底层是数组必须指定容量。它的特点是“定长”线程池满了之后新任务只能被拒绝或者由调用方处理适合对任务堆积量有严格上限、不希望内存无限膨胀的场景。LinkedBlockingQueue底层是链表默认容量是 Integer.MAX_VALUE约21亿。它不指定容量时“似乎”可以无限堆积任务但这恰恰是生产事故的温床——线程池处理不过来时任务全堆在队列里内存一点一点耗尽直到 OOM。我第一次排查这种事故时看到监控里堆内存呈一条直线上升最后容器直接被杀掉印象太深了。所以用 LinkedBlockingQueue 务必显式指定容量上限。SynchronousQueue更特殊它本身不存储任务每个入队的操作必须等待一个出队的操作同时发生所以它相当于一个零容量的队列。适合追求低延迟、任务来了立即交给线程执行、不要排队缓冲的场景。你看选线程池队列这件事本质上就是在问任务堆积是可接受的吗堆积量能不能估出来想清楚这两个问题选哪个队列就不需要背了。5. 把队列放到更大的版图里看顺序队列和链式队列只是队列家族的基石往上还有更多变形应用。这块不算必考但理解了会让你的知识体系完整很多。5.1 从数据结构队列到分布式消息队列热词里反复出现 Kafka、RabbitMQ、RocketMQ 的消息队列选型对比很多初学朋友容易混淆数据结构里的队列和消息中间件是一回事吗完全不是一回事但思想一脉相承。“分布式消息队列”本质上是把“先进先出”这个内核放在一个分布式系统里重新实现。Kafka 的每个分区Partition内部就是一条严格有序的消息日志消费者按顺序读取RabbitMQ 的队列支持多消费者时还能做轮询分发RocketMQ 则强调消息事务和延迟消息底层也是队列模型的扩展。它们要解决的是“跨进程”甚至“跨机器”的消息传递涉及网络通信、持久化、高可用、消费端负载均衡这比内存里一个队列复杂得多。理解基础队列模型的最大价值在于你面对 Kafka 消息乱序问题、重复消费问题、堆积预警调优时第一反应是回到“先进先出”和“缓冲”的本源去看问题而不是一头扎进配置参数里。5.2 阻塞队列与生产者消费者模式阻塞队列是队列在并发编程里的标准形态。它在入队和出队操作上加上了线程安全控制并提供两种特殊行为队列满时入队线程阻塞等待队列空时出队线程阻塞等待。这种设计让生产者和消费者不需要互相通知、轮询判断谁空了谁等着就行代码极简。Java 的BlockingQueue、Go 的channel、C 里各种并发库的concurrent_queue本质都是在这个模型上封装出来的。写多线程代码时如果你发现总是不由自主地去写while(true) { check(); sleep(10); }这样的轮询逻辑试着换成阻塞队列代码会清爽一个量级。5.3 单调队列队列的“算法形态”热词里还有“单调队列优化DP”这也是队列的高级应用之一。单调队列是指队列内部元素保持严格单调递增或递减它的核心用途是在滑动窗口问题里维护窗口内的极值。比如给你一个数组和一个窗口大小 k要你输出每个窗口的最大值用普通做法每次扫一遍窗口时间复杂度是 O(n*k)用单调队列优化后是 O(n)。单调队列的特殊之处在于它不但要维护“进出顺序”还要在入队时把队尾不满足单调性的元素全部弹出。这已经超出了普通出队入队的语义属于队列思想的拓展应用。建议先把基础队列写熟练再接触单调队列否则两件事混在一起容易懵。6. 高频踩坑现场与排查技巧队列的实现虽然短但工程里用起来坑不少。我把自己实际调试中遇到过的问题整理成了一份清单按“症状—原因—解法”的格式列出来你以后遇到类似问题能少走弯路。6.1 顺序队列的假溢出症状队列明明还有空间入队却报错或越界。原因rear 指针到了数组尾部前面的空间没有利用。解法用循环队列入队出队都强制取模。如果用的是非循环实现务必在每次入队前检查 rear 是否触底触底就整体搬移数据。这块属于必须理解到骨子里的知识点面试官只要看你代码里有没有取模运算就知道你是不是真的懂了循环队列而不是背了个示意图。6.2 链式队列删除最后一个元素后的悬空指针症状队列删除到空后再入队发生段错误或者内存被莫名写坏。原因出队删除了最后一个节点rear 还指向已被释放的内存区域。解法出队时判断q-rear tmp如果成立立即把 rear 指回头结点。写代码时这个分支看起来多余但少写了就是这样的小事故。6.3 循环队列的判空判满条件写反症状队列满了还能继续入队、覆盖掉旧数据或者队列为空时出队拿到脏数据。原因混淆了判空front rear和判满(rear1)%MAX_SIZE front两个条件。解法自己动手画一个容量为4的循环队列手推一遍入队出队过程。我强烈建议每个学这块的朋友都花十分钟做这件事画正方形表示数组用两个小箭头表示 front 和 rear手动模拟入队、出队、再入队直到满、再出队直到空。推完一遍这两个条件永远都不会忘。6.4 动态扩容后的元素顺序错乱症状扩容后遍历队列元素顺序变成乱序或者元素丢失。原因从旧数组拷贝元素时没有把两段环形排列的数据拼成正确的顺序。解法按(front i) % oldCapacity的方式遍历旧队列把元素依次塞到新数组的 0、1、2... 位置然后重新设置 front0、rearcount。除非你彻底不打算扩容否则这个细节绕不开。6.5 多线程环境下直接用普通队列症状并发入队出队时偶发数据不一致、死锁或者程序崩溃。原因head 和 tail 指针的读写不是原子的。解法并发场景不要手写裸队列。优先用现成的并发队列库Java BlockingQueue、Go channel如果必须手写用 CAS 无锁队列或者加锁保护并且测试时用高并发压测工具验证。手写并发队列的难度比手写单线程队列高一个档次除非是学习目的否则别在线上造这个轮子。6.6 队列元素上限导致的业务静默丢弃症状系统高峰期部分用户请求消失了日志没有任何报错。原因队列满了入队失败但业务代码没处理返回值。解法入队一定要检查返回值。队列满时的策略阻塞等待、丢弃、拒绝并提示、记录日志需要业务方明确约定。那种“入队失败就静默忽略”的代码迟早会把线上问题变成玄学问题。这条不管对内存队列还是消息队列都适用。7. 一个完整的链式队列示例上面讲了这么多最后给一个可以直接编译运行的完整示例把前面所有细节落进代码里。我比较推荐用链式队列示例作为模板因为它的指针操作比顺序队列更容易出错跑通了会有更深的体感。#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 initQueue(LinkQueue *q) { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; q-front head; q-rear head; } bool isEmpty(LinkQueue *q) { return q-front-next NULL; } bool enQueue(LinkQueue *q, int val) { Node *newNode (Node *)malloc(sizeof(Node)); if (!newNode) return false; newNode-data val; newNode-next NULL; q-rear-next newNode; q-rear newNode; return true; } bool deQueue(LinkQueue *q, int *val) { if (isEmpty(q)) return false; Node *tmp q-front-next; *val tmp-data; q-front-next tmp-next; if (q-rear tmp) { q-rear q-front; } free(tmp); return true; } void destroyQueue(LinkQueue *q) { while (q-front ! NULL) { q-rear q-front-next; free(q-front); q-front q-rear; } } int main() { LinkQueue q; initQueue(q); enQueue(q, 1); enQueue(q, 2); enQueue(q, 3); int val; while (deQueue(q, val)) { printf(%d , val); } printf(\n); destroyQueue(q); return 0; }这段代码输出1 2 3逻辑和上面讲的一致。你可以在本地跑一下再试试删除到空之后继续入队观察是否正常。我个人的建议是在此基础上自己再写一个循环队列版本跑通之后把两者放到一起对比你收获的会比单纯看完这篇文章大得多。回到文章开头说的队列是那种看起来简单、但值得反复琢磨的基础结构。我从顺序队列的假溢出讲到循环队列的取模技巧再到链式队列的头结点设计然后又把这套基础放到了线程池、消息中间件这些上层工程里看了一圈。这些内容不是割裂的知识点而是同一个“先进先出”内核在不同约束条件下的自然演化。理解了这个内核你在任何语言、任何框架里遇到队列这个问题都能秒速想清楚它底层大概是怎么实现的有哪些边界需要注意也就能在工作里更从容地做取舍了。