数据结构学习到第5天按大多数教材和考研复习资料的正常节奏线性结构刚好从顺序表、链表、栈一路走到队列。这一天表面上不如链表和栈那么“刺激”但队列在笔试题和算法题里的出场频率相当高尤其是双端队列以及基于队列演化出来的单调队列、广度优先搜索几乎每个面试季都要见几面。我把day05的完整学习笔记整理了一下覆盖手写循环队列、链式队列、双端队列的多种实现思路也把考研和期末复习里关于队列判空判满、空间复杂度的常见坑一并列出来。无论你是刚学到队列这门课的在校生还是准备期末突击、考研冲刺这份笔记应该都能用上。1. 第5天轮到队列一点也不意外1.1 线性结构时间线上的最后一环从数据结构学习路径来看线性结构大体按“顺序表 - 链表 - 栈 - 队列”这个顺序推进。前三天解决的是“数据怎么存、怎么遍历、怎么插入删除”到了栈和队列角度发生了变化它们都是操作受限的线性表。栈是后进先出队列是先进先出这两个受限操作恰好构成线性结构里最重要的两个抽象模型。为什么队列要放到第5天而不是第2天我的理解是队列的实现本身并不比链表难难的是队列背后的“场景思维”。链表考的是指针操作队列考的是你能不能在实际问题里识别出“谁先到谁先处理”的模型。排队叫号、消息推送、导航路径搜索本质上都是队列。所以第5天表面上是在写代码实际上是在训练一种建模能力这也是为什么很多课程把队列安排在熟悉了顺序存储和链式存储之后——你得先会存数据才有资格讨论用什么规则取数据。另外一个现实原因也很直接循环队列的取模运算、判空判满逻辑需要你已经熟悉了数组下标和链表指针。如果第2天就来学队列学生很容易被取模绕晕有了前4天的铺垫队列的内容消化起来会顺畅很多。这个顺序不是随便定的是课程设计里反复验证过的。1.2 三个术语、一个类比、一个隐藏考点队列的核心术语就几个队头front、队尾rear、入队enqueue、出队dequeue。生活里排队做核酸、食堂打饭就是最标准的队列模型——先来的站前面新来的排后面窗口只服务队头那个人。这个类比还有个隐藏含义队列不允许插队。在数据结构层面“不允许插队”意味着插入只能在队尾删除只能在队头。这是队列与普通线性表最大的区别。能理解“操作受限”这个限制后面理解双端队列“两头都能进出”的设计动机就顺理成章了。很多人学队列时容易忽略一个隐藏考点同样是线性表为什么顺序表和链表支持任意位置的插入删除而队列非要自我限制答案是因为现实场景需要。操作系统里的任务调度如果允许任意插队后面的任务永远可能被插队饿死消息队列如果允许中间插入消费者处理顺序就会乱掉。数据结构里的“限制”从来不是为了难为你而是为了映射真实世界的规则。把这个想通了队列这章就算入门了。2. 手写顺序队列绕不开的循环2.1 朴素方案为什么会“假满”很多初学者第一次写顺序队列都会写出下面这样的结构#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front, rear; } SqQueue;入队时data[rear] x出队时x data[front]。表面上看没什么问题但跑几次就会发现rear 一直在往上涨front 也一直在涨前面的数组空间永远空着整个数组真正能用的次数只有 MAXSIZE 次。队列明明没满却因为 rear 到了数组末尾而报“队满”。这就是顺序队列最经典的“假满”问题。解决办法是让 rear 和 front 可以回落也就是把数组在逻辑上首尾相接成环。数学上叫取模直观上叫循环队列。我当年第一次理解循环队列时想的是操场跑圈跑完一圈回到起点但数据还是那批数据位置却可以循环复用。这个类比虽然简单但确实帮我从“数组就一条直线”的思维定式里跳了出来。2.2 循环队列的判空判满与长度公式循环队列的存储结构还是上面那个只是入队出队时都做一次取模// 入队 if ((q.rear 1) % MAXSIZE q.front) { // 队满 } else { q.data[q.rear] x; q.rear (q.rear 1) % MAXSIZE; } // 出队 if (q.rear q.front) { // 队空 } else { x q.data[q.front]; q.front (q.front 1) % MAXSIZE; }这里有个新手必踩的坑循环队列的判满是(rear 1) % MAXSIZE front而不是rear front。因为rear front同时是判空的条件如果不牺牲一个存储单元空和满就区分不出来。所以循环队列的实际最大容量是 MAXSIZE - 1。这个“牺牲一个格子”的设计考研题里反复考期末复习也经常考一定要理解而不是死记。另一个配套公式是队列长度(rear - front MAXSIZE) % MAXSIZE。为什么中间要加 MAXSIZE因为 rear 可能已经绕圈绕到 front 前面去了直接相减可能是负数先加一圈保证结果为正再取模就能得到正确的元素个数。这两个公式可以一起记忆做题时经常联动出现。2.3 可以直接跑的C语言实现下面给一个可以直接编译运行的版本我实测跑过细节都处理好了#include stdio.h #define MAXSIZE 5 typedef struct { int data[MAXSIZE]; int front, rear; } SqQueue; void init(SqQueue *q) { q-front q-rear 0; } int enqueue(SqQueue *q, int x) { if ((q-rear 1) % MAXSIZE q-front) return 0; q-data[q-rear] x; q-rear (q-rear 1) % MAXSIZE; return 1; } int dequeue(SqQueue *q, int *x) { if (q-rear q-front) return 0; *x q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; } int length(SqQueue q) { return (q.rear - q.front MAXSIZE) % MAXSIZE; } int main() { SqQueue q; init(q); int x; enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); dequeue(q, x); // x 10 enqueue(q, 40); enqueue(q, 50); // 此时还能入队一个元素 printf(当前长度: %d\n, length(q)); // 4 return 0; }注意 MAXSIZE 只开了 5但最多只能存 4 个元素。很多人拿类似代码去跑发现数组明明有 5 个位置却报队满就是这个设计导致的。如果不想浪费这一个格子可以额外加一个 size 计数变量或者用 flag 标记最近一次操作是入队还是出队。王道考研书里就介绍过加 size 的改良版面试官问“循环队列如何在不牺牲空间的情况下判满”时加 size 是最常见的标准答案值得顺手记住。2.4 实操心得先画图再写码我强烈建议第一次学循环队列时别急着写代码先在纸上画一个环形数组手动模拟“入队3个、出队2个、再入队3个”的过程每走一步都更新 front 和 rear。我自己带过几个学弟学妹他们卡住的地方几乎都在“取模到底什么时候用”。画一遍图就明白了取模不是数学作业而是让下标回到数组开头的一种循环计数方式。这个习惯还能帮你省下大量调试时间。我见过不少同学写出来的循环队列代码里面有各种魔改的 if 分支结果越写越乱就是因为脑子里没有“环形”这个画面。数据结构这类的课程七分靠理解三分靠代码。画图这个动作就是在补足那七分理解。3. 链式队列容量自由细节更多3.1 结构设计与带头结点的理由链式队列本质上是单链表加两个指针一个指向队头一个指向队尾。入队操作在尾部进行出队操作在头部进行。结构可以这样定义typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front, *rear; } LinkQueue;链表部分在第3天就练过了所以第5天的主要难点在于头尾指针的维护尤其是出队时如果队头就是队尾front 和 rear 都要更新漏一个就会留下悬空指针。这里我建议带头结点。带头结点的链式队列空队列时 front 和 rear 都指向头结点入队删除的判断会统一很多代码也不容易写乱。不带头结点的版本是王道和李春葆教材里的常见变形考试偶尔会引导你去推导但实际工程里我几乎都用带头结点版本理由只有一个少写分支少出错。3.2 入队出队实现与野指针隐患入队出队的完整参考实现如下#include stdio.h #include stdlib.h typedef struct QNode { int data; struct QNode *next; } QNode; typedef struct { QNode *front, *rear; } LinkQueue; void init(LinkQueue *q) { q-front q-rear (QNode *)malloc(sizeof(QNode)); q-front-next NULL; } void enqueue(LinkQueue *q, int x) { QNode *s (QNode *)malloc(sizeof(QNode)); s-data x; s-next NULL; q-rear-next s; q-rear s; } int dequeue(LinkQueue *q, int *x) { if (q-front q-rear) return 0; // 空队 QNode *p q-front-next; *x p-data; q-front-next p-next; if (q-rear p) q-rear q-front; // 删除的是最后一个节点 free(p); return 1; }出队最后有个很容易被忽略的细节如果被删除的节点是队尾节点rear 必须回退到 front否则 rear 会指向一个已经被 free 掉的内存这就是典型的野指针问题。我在 LeetCode 刷题时见过不少人栽在这。你可以在调试时故意把那一行注释掉用 valgrind 跑一下就能看到 heap-use-after-free 的报错。这个现象比任何教科书解释都直观建议亲手试一次。3.3 顺序队列和链式队列怎么选维度循环队列链式队列容量固定最多 MAXSIZE-1可能假满动态内存够就能入队入队出队时间复杂度O(1)O(1)额外开销无指针开销每个节点多一个 next 指针和 malloc 开销内存分布连续缓存友好离散可能有缓存不友好的问题典型场景嵌入式、内核缓冲区业务系统消息缓冲、动态任务队列这个表是我在教学和实际项目里反复对照得出的结论。很多初学者觉得链式队列更高端其实不见得。循环队列的内存连续性在缓存层面更友好而链式队列每次 malloc 都有时间开销频繁入队出队时差距会很明显。如果队列长度可预知、又要极致性能选循环如果长度波动大、无法预估选链式。考研里如果让你比较两者就按这个思路答时间上都是 O(1)空间上链式更灵活但有额外指针开销顺序的优点是简单和连续。4. 双端队列把“排队”玩出花4.1 双端队列是什么考研爱考什么双端队列deque全称 double-ended queue允许在队头和队尾两端都执行插入和删除。常见变体有两种输出受限双端队列只能从一端出但两端都能进和输入受限双端队列只能从一端进但两端都能出。考研题常常给一个双端队列问一串输入序列经过它之后能否得到某个输出序列这类题画图模拟比看代码更高效因为结论取决于进出顺序的组合。双端队列不是花架子。历史记录里的撤销重做单靠栈模型解决不了时滑动窗口最大值、回文判断、任务调度这些场景双端队列常常是标准工具。这也是为什么数据结构课程虽然只讲概念但面试和竞赛都把它当重点。平时觉得“两头都能进出的队列”有点奇怪真到了需要用它的时候你会感谢当年认真学过这个数据结构。4.2 Python里的deque以及pandas小提醒如果是为了刷算法题Python 最常用的就是 collections.dequefrom collections import deque dq deque([1, 2, 3]) dq.append(4) # 队尾入 dq.appendleft(0) # 队头入 dq.pop() # 队尾出 dq.popleft() # 队头出 print(dq) # deque([1, 2, 3])deque 底层是双向链表加块状存储从两端增删都是 O(1)而列表 list 在头部插入是 O(n)。如果你看到有人拿 list 当队列用而且经常pop(0)那复杂度大概率已经退化到 O(n) 了。实测 1 万次pop(0)和popleft()的耗时差距非常明显写算法题时务必养成用 deque 的习惯。顺带说一句热词里还有“pandas数据结构创建”。pandas 里的 Series 和 DataFrame 也是“数据结构”但那是建立在数组和索引之上的高层数据分析结构和算法课上的队列栈不在一个层次。头歌上有专门的 pandas 数据结构创建练习如果你是跟着平台做实验注意区分“底层数据结构”和“数据分析数据结构”两个概念别混在一起复习不然到了期末考试容易记混。4.3 Java里的ArrayDeque与LinkedListJava 里队列相关的接口是 Queue 和 Deque核心实现是 ArrayDeque 和 LinkedList。ArrayDeque 底层是循环数组LinkedList 底层是双向链表。用的时候推荐优先选 ArrayDequeDequeInteger deque new ArrayDeque(); deque.addLast(1); deque.addFirst(0); int x deque.pollFirst(); int y deque.pollLast();很多人忽略的一点ArrayDeque 不允许 null 元素而 LinkedList 允许。如果你从数据库查出来的数据可能带 null用 ArrayDeque 会抛 NullPointerException需要提前判空。另外 ArrayDeque 当栈用也很好速度比 Stack 类快因为 Stack 是继承 Vector 的线程安全类有同步开销。面试聊到 Java 集合框架时能说出“Deque 接口、ArrayDeque 循环数组实现、LinkedList 链表实现、Stack 线程安全但慢”这一串基本就过关了。4.4 双端队列的三种典型应用第一个应用是滑动窗口最大值。LeetCode 239 这道经典题维护一个递减双端队列窗口滑动时从队头取最大值新元素入队前把队尾所有比它小的元素弹出。这个做法能用 O(n) 代替 O(n*k) 的暴力解我第一次见时觉得简直是在变魔术但画图模拟两遍就懂了。重点在于理解为什么要弹出队尾的小元素窗口里已经有更大的新元素那些旧的小元素永远不可能成为最大值了留着纯属浪费。第二个应用是回文判断。从两端同时 pop比较字符是否相同天然就是双端队列的主场def is_palindrome(s: str) - bool: dq deque(s) while len(dq) 1: if dq.popleft() ! dq.pop(): return False return True第三个应用是并发编程里的工作窃取算法。每个工作者线程维护一个 deque任务从队头取别的空闲线程从队尾“偷”任务避免队列竞争。Java 的 ForkJoinPool 就是这么设计的。学数据结构听到“双端队列”时很多人觉得鸡肋等到看并发框架源码时就会感叹当初没白学。5. 队列在算法题里的进阶用法5.1 BFS队列的完美舞台广度优先搜索的核心思想是“逐层扩散”逐层扩散天然需要队列先入队的节点先访问访问完把邻居入队。树的层序遍历、图的无权最短路径、迷宫最短步数全是 BFS。BFS 的模板很短但有几个细节我必须提醒入队前用 visited 数组标记否则图里节点可能重复入队队列规模指数级暴涨。分层 BFS 时要在进入循环时先记录当前队列长度 size q.size()再循环 size 次这样才能知道“这一层”有多少个节点。起点和终点的处理先想清楚再动手尤其是要计算步数时是先入队起点算第0步还是算第1步不同写法差很多。我在刷题时统计过BFS 类题目在热门题单里占比不低而绝大多数人写错都是因为漏了 visited 标记。这不是队列本身的问题而是建模时少了一个状态把图当成树来遍历了。5.2 单调队列滑动窗口的幕后英雄单调队列是循环队列和双端队列的进阶组合常用于维护窗口内最大最小值。以滑动窗口最大值为例核心思路是队头永远是当前窗口最大值队内元素按下标递增、按值递减任何新元素入队前先把队尾比它小的全部弹掉因为它们“不可能成为接下来的最大值”。这个过程很有意思比新元素小的旧元素在新元素存在期间永远没机会出头所以直接淘汰。这种“淘汰不可能更优的候选”的思想和单调栈、动态规划优化里的决策单调性是一家人。理解和记住这一点比背代码重要得多。我见过不少同学能把模板背下来但换一种问法就懵就是因为只背了步骤没理解淘汰逻辑。5.3 队列在系统里无处不在内核里的任务队列、网络包的接收缓冲、消息中间件的发布订阅、线程池的任务队列全是队列的应用。以消息中间件为例消费者的消费顺序就是先进先出这和食堂排队一模一样如果需要按优先级处理就引出了优先队列堆那是第7天之后的话题了。做系统设计面试时如果聊到削峰填谷消息队列几乎是标准答案。你会发现学校里的“数据结构第5天”和公司里的“高并发架构”在思想上完全一致先到先服务缓冲突发流量让系统稳定运行。这就是为什么我一直跟学弟学妹说别觉得基础数据结构没用它实际上是整个计算机世界的底层语法。6. 期末复习与考研的队列高频考点6.1 循环队列判空判满理解比记忆重要考研和期末最爱考的就是循环队列的判空判满。光记结论不够用考场上会换各种形式。比如给一个用 size 变量计数的版本问你如何判空判满给你 front 指向队头元素、rear 指向队尾元素的下一个位置问队满条件或者 rear 指向队尾元素、front 指向队头元素的前一个位置问队满条件。三种定义方式都能出题你必须根据定义现场推而不是照抄公式。我的建议是记住一个母题画一个圆圈标出 front 和 rear 在不同定义下的位置手动走一遍入队出队看什么时候两者相等、什么时候相差 1公式自然就推出来了。这个“现场推导”的能力是考场上最稳的护身符比刷十道同类型题都管用。6.2 空间复杂度分析的常见误区热词里出现了“数据结构与算法 空间复杂度”这里我多说两句。很多同学写层序遍历时以为队列空间就是 O(n)但没算上递归栈写链式队列时忘了每个节点还有 next 指针和 malloc 对齐带来的额外开销。考试分析空间复杂度时要分清楚“辅助空间”和数据本身占用的空间。队列题里辅助空间通常是 O(n)但如果你每次入队都复制一遍数据那可能是 O(n) 的复制操作带来 O(1) 空间但 O(n) 时间别把时间和空间混为一谈。还有一个细节循环队列的空间复杂度是 O(1) 还是 O(n)取决于你怎么看。固定长度的循环队列辅助空间就是那一个数组大小是常量严格说 O(1)但如果题目要求你分析“整个结构占用的内存”那就是 O(MAXSIZE)即 O(n)。考试时看清楚题干的问法这里丢分非常可惜。6.3 常见问题速查问题原因解决办法循环队列提示队满但明明还有空格牺牲了一个存储单元记住实际容量是 MAXSIZE-1或改用 size 计数链式队列出队后程序崩溃删除尾节点后 rear 没回退判断 q-rear p 时回退到 front用 list 当 Python 队列越跑越慢pop(0) 是 O(n)改用 collections.dequeJava ArrayDeque 插入时报空指针存入了 null 元素换 LinkedList 或提前判空BFS 死循环或结果异常缺少 visited 标记入队时立刻标记为已访问滑动窗口最大值超时暴力取窗口 max用单调双端队列降为 O(n)这张表我每带一届学生都会更新一次基本覆盖了从入门到刷题阶段最常见的报错。每个坑我都亲测过或者看着别人踩过尤其是链式队列的野指针问题几乎每个用 C 写队列的人都会遇到一次遇到别慌按表排查就行。6.4 复习资料怎么选热词里出现了很多教材和资源王道、大话数据结构、李春葆的《数据结构》第五版、还有《数据结构与算法分析》的 Java 描述版。我的建议是主线选一本比如王道或者李春葆配合课后题过一遍想加深理解再看大话数据结构那种趣味性强的如果主语言是 Java可以翻《数据结构与算法分析: Java语言描述》。另外李春葆第五版网上有学弟整理的勘误汇总教材和习题偶尔会有笔误做题对不上答案时先去查勘误别一上来就怀疑自己。我当年还专门找过山东大学软件学院的数据结构课程材料来对照复习因为期末出题风格各校不太一样多看几家的练习题比只盯一本书更稳妥。现在很多高校都有公开的实验报告模板搜索“数据结构实验报告”也能找到不少参考但实验报告终究是辅助核心还是把代码和原理都吃透。教材 PDF 虽然方便但纸质书或电子版配合手写笔记的效果更好至少我是这么觉得的。队列这部分内容我个人在教学和刷题里的体会是它不像链表那样考验指针技巧也不像树那样考验递归思维但它考验的是对“先进先出”这个模型的理解深度。循环队列那个“牺牲一格”的设计表面上是空间浪费实际上教会我一件事任何数据结构的设计都伴随权衡没有免费午餐。学完队列后面排序算法、查找、树和图会一个个排着队来排序算法那一关有新的坑要踩到时候再开一篇慢慢聊。