算法训练进行到第11天终于轮到栈与队列了。说实话我在前十天排计划的时候一度觉得这两个结构太“简单”甚至想跳过——先进后出、先进先出定义倒背如流不就是个受限的线性表嘛。可真动手刷起来才发现栈与队列这对兄弟才是后面几乎所有复杂算法的底盘树的中序非递归遍历要栈图的BFS要队列单调栈、单调队列、优先队列更是各种进阶题里的常客连工程里的调用栈回溯、线程池阻塞队列、消息队列底层都能追到这两张表上。这篇文章就把我Day11的刷题笔记、踩坑记录和几个高频面试考点的思路整理出来既有基础题的代码实现也有从LeetCode延伸出去的工程视角适合刚学完数据结构基础、准备系统刷题的朋友也适合想在工程场景里反向理解“队列”和“栈”价值的开发者。1. 栈与队列不是“一个先进后出一个先进先出”这么简单1.1 栈的本质是回溯队列的本质是排队如果只把栈记成“先进后出”把队列记成“先进先出”那你只是知道了操作顺序没有理解它们存在的根本原因。栈存在的意义是保存“还没做完的事”的状态等当前的事情处理完再回到之前的状态继续。浏览器后退按钮就是一个典型你每打开一个新页面旧页面就被压进“后退栈”你点后退其实就是在弹栈回到上一个页面。编辑器里的撤销功能也一样每一次操作都被压入撤销栈CtrlZ就是把最近一次操作弹出来恢复之前的状态。所以栈天然适合处理“回溯”“逆序”“递归”“嵌套”这类问题。队列存在的意义则是公平地按到达顺序处理事务。食堂打饭要排队打印机任务要排队操作系统里的进程按时间片轮转也要排队。队列保证了先来先得的顺序谁先到谁先被处理这是工业界最基本的行为约束不能插队不能因为后到的任务更紧急就抢占前面的位置除非你用了优先队列那是另一回事。所以说栈是一种“处理半成品”的结构队列是一种“安排成品顺序”的结构二者服务的场景完全不同。1.2 为什么算法题总把栈和队列搞成一堆“对偶题”栈和队列在底层都是线性表唯一的区别是操作端点的位置栈只能在一端进出队列在一端进、另一端出。正是因为底层材料相同、操作方法不同算法题里才会高频出现“用栈实现队列”“用队列实现栈”这种互相转换的题目。这类题考的不是技巧而是你对操作时序的理解把一个元素压进栈再弹出来顺序会反转把一个元素从队列末尾取出再插到末尾顺序会轮转。靠这两种基础操作就能从一个结构推导出另一个结构的行为。这种对偶关系在算法里无处不在二叉树的前序/中序/后序遍历递归版本本质是利用系统调用栈实现回溯而迭代版本是我们自己维护一个显式的栈手动模拟递归压栈、弹栈的过程。图论的DFS用栈系统栈或显式栈BFS用队列两者的实现套路几乎完全对应。掌握了“栈和队列到底在替我们保存什么东西”这个认知后面遇到任何变形题你都不会慌因为你知道核心是状态保存和状态恢复而不是死记API。1.3 面试里那些容易被忽略的“栈与队列”信号刷题多了你会发现题目里其实藏着辨别该用栈还是该用队列的信号词。看到“匹配”“嵌套”“逆序”“回溯”“撤销”这类关键词优先想栈看到“滑动”“排队”“按序处理”“宽度优先”这类关键词优先想队列。当然还有一堆变体双端队列Deque是栈和队列的合体两端都能进出BFS的0-1最短路就是靠它实现的循环队列解决的是数组空间的再利用单调栈和单调队列解决的是寻找“下一个更大/更小元素”和维护滑动窗口统计的问题优先队列解决的是“不是先来先服务而是最大/最小先服务”的问题。这几个变体在热词里频繁出现说明它们确实是面试和工程中的重点。提示判断标准不是“这个数据结构叫什么”而是“我需要保存的状态的出场顺序是什么”——后保存的先出场就选栈先保存的先出场就选队列。2. 用栈实现队列、用队列实现栈Day11最具代表性的两道题2.1 两个栈实现队列摊还O(1)的精髓LeetCode 232是学完栈与队列后必刷的第一道题。思路很朴素准备两个栈一个in_stack专门负责入队一个out_stack专门负责出队。入队时直接push到in_stack出队时如果out_stack不为空直接从out_stack弹出如果out_stack为空先把in_stack里所有元素搬到out_stack再做弹出。此时in_stack里的元素顺序被完全反转所以out_stack栈顶就是最早进入的元素完美模拟了先进先出。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): self._move() return self.out_stack.pop() def peek(self): self._move() return self.out_stack[-1] def empty(self): return not self.in_stack and not self.out_stack def _move(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop())摊还O(1)的关键就在这个_move()每个元素只会从in_stack搬到out_stack一次不会反复搬运。面试时容易被追问的一个细节是如果push了几个新元素之后out_stack还没搬空此时pop会发生什么其实没问题——当前队首永远是out_stack栈顶新元素全部留在in_stack里等待顺序不会乱。另一个细节是peek()和pop()都必须先调用_move()如果忘了在out_stack为空时会直接访问不存在的元素这是最常翻车的边界。2.2 一个队列也能实现栈旋转大法LeetCode 225要求用队列实现栈。用两个队列的解法当然可以但有一个更惊艳的做法只用一个队列每次push时把前面已有的元素依次出队并重新入队让刚进来的新元素旋转到队头。这样新元素永远在队头pop时直接弹出队头就实现了后进先出。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x): self.q.append(x) for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def pop(self): return self.q.popleft() def top(self): return self.q[0] def empty(self): return not self.q这里有一个所有讲解都值得强调的细节如果要用list模拟队列的popleft千万别写成pop(0)因为Python的list.pop(0)是O(n)的整体复杂度会退化成O(n^2)。用collections.deque的popleft()是O(1)才能真正达到预期的时间复杂度。这道题做错的人大多数不是思路不会而是语言API用错了。2.3 从互相转换里提炼出的“状态转移”思维这两道题放在Day11意义不在于记住代码而在于提炼一种思维把一个结构的状态通过明确的操作规则转移到另一个结构。用两个栈实现队列其实是在两个栈之间执行“倒水”操作用一个队列实现栈其实是在同一队列内执行“循环平移”操作。这种状态转移的思想在后面刷图论、刷动态规划、刷自动机时都会反复出现。比如在做二叉树迭代遍历时你的显式栈里存放的就是“接下来要处理哪个节点”的状态做拓扑排序时队列里存放的是“当前入度为0、可以处理的节点”的状态。无论结构怎么变核心都逃不开“保存状态、取出状态、更新状态”这三步。能把这个步骤想清楚栈与队列这两章就算真正吃透了而不是只会背几道热门题。3. 单调栈与单调队列滑动窗口和“下一个更大元素”的进阶玩法3.1 单调栈每日温度问题背后的“延迟匹配”Day11刷到这儿最让我觉得“基础结构直接上强度”的就是单调栈和单调队列。先看单调栈经典题目是LeetCode 739每日温度给一个温度数组要求输出每一天还要等几天才出现更高的温度。暴力解法是两重循环时间O(n^2)数据规模一大就超时。单调栈的解法是O(n)的而且代码非常短。思路是维护一个栈栈内下标对应的温度是单调递减的。遍历每一天当遇到当前温度比栈顶下标那天的温度更高时说明栈顶那天终于找到了“下一个更高温度”天数差就是答案弹出栈顶继续和新的栈顶比较直到栈顶温度高于当前温度或栈空再把当前下标压栈。def dailyTemperatures(temperatures): n len(temperatures) ans [0] * n stack [] # 存下标而不是温度本身 for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: prev stack.pop() ans[prev] i - prev stack.append(i) return ans这里最容易出错的地方是没有意识到栈里存的是下标不是温度值。因为最终要求的是天数差存下标方便直接做减法温度值用来决定while循环的条件。这个“栈里存下标”的套路在单调栈的四连杀每日温度、下一个更大元素、柱状图中最大矩形、接雨水里都是通用的一旦记住能帮你少走很多弯路。3.2 单调队列滑动窗口最大值的双端队列实现单调队列的经典题是LeetCode 239滑动窗口最大值。暴力解法每次在窗口里找最大值复杂度O(nk)当k接近n时会退化到O(n^2)。单调队列的解法能把整体复杂度压到O(n)。它维护一个双端队列队列里的元素下标对应的值是从队头到队尾单调递减的这样队头永远就是当前窗口的最大值。每次窗口右移要做两件事把已经离开窗口左边界的队头元素弹出因为它过期了从队尾开始把所有小于等于新元素的队尾元素弹出因为新元素比它们大、还比它们新在窗口里它们永远不可能成为最大值新元素从队尾入队此时队头元素仍然或重新变成最大值。from collections import deque def maxSlidingWindow(nums, k): dq deque() ans [] for i, x in enumerate(nums): # 队头已滑出窗口 if dq and dq[0] i - k 1: dq.popleft() # 维护单调递减丢掉不可能成为最大值的队尾 while dq and nums[dq[-1]] x: dq.pop() dq.append(i) if i k - 1: ans.append(nums[dq[0]]) return ans我当初理解这个算法时卡在“为什么要从队尾丢掉比新元素小的元素”这一步。用一个生活类比就通了如果新来的员工能力更强、还更年轻那所有比他能力弱、资历也更老的员工就永远排不到他了——在窗口内他们绝无机会成为“最大”留着纯属浪费空间。这就是单调队列的“剪枝”思想。3.3 为什么这类题在面试里几乎属于“必考送分题”单调栈和单调队列高频出现是有原因的它们考察的不只是栈/队列的基本操作而是“维护单调性”这个通用技巧。能在一轮扫描中同时完成查找和淘汰空间换时间这是面试官非常喜欢的思维路径。而且这道题非常容易现场推演给你一个例子你一步步照着规则把队列画出来面试官立刻能看出你对数据结构的理解是否到位。我在训练中有一个很深的体会这两类题与其说是“栈与队列”的题目不如说是“动态维护信息”的题目。普通栈与队列只是容器单调栈与单调队列则给容器里的元素加上了“有序性”这个约束。这个“容器约束”的组合模式才是它们能秒杀O(n^2)暴力的根本原因。掌握了这个点类似“和至少为K的最短子数组”“接雨水”这类题你也能很快想到用单调栈/队列去解。4. 出了LeetCode栈与队列还在哪里等你4.1 线程池里的阻塞队列有界和无界的选择刷算法题时我们用的队列是“纯内存”“无阻塞”的但到工程里队列直接升级成了阻塞队列。Java的ThreadPoolExecutor里就有几个核心参数专门围绕队列ArrayBlockingQueue是有界数组队列LinkedBlockingQueue可以是无界链表队列SynchronousQueue则完全不存任务直接把任务交给线程。为什么不能随手选一个因为队列的选择直接影响背压机制。如果选无界队列任务无限堆积内存迟早被耗尽如果选有界队列满了之后就需要拒绝策略是丢弃任务、是抛出异常、还是让提交线程自己执行任务各有适用场景。热词里“线程池的阻塞队列选择”搜的人特别多就是因为很多人把LeetCode里“队列”的概念搬进工程时忽略了“资源有限”这个现实约束。算法里的队列假设资源无限工程里的队列必须思考容量和淘汰策略这是从刷题到落地最重要的认知转换。阻塞队列的另一层价值是解决生产者消费者的忙等待问题。算法课上你可能见过while(empty) sleep()这种轮询低效且浪费CPU。阻塞队列提供了take()和put()这样的阻塞语义队列为空时消费者自动挂起队列满时生产者自动挂起不需要锁和条件变量自己拼。这其实就是把“队列不仅仅是存储结构还是一种协调机制”的思想工业化了。4.2 消息队列里的重复消费与顺序问题再往上看Kafka、RocketMQ这一类消息队列本质上是把“队列”这个结构从单机内存挪到了分布式系统层面。这里的热词“消息队列重复消费问题”几乎是每家公司面试都会问的网络超时导致消费者处理完消息但没来得及提交offset消费者重启后重新拉取旧消息就产生了重复消费。解决办法不是让消息队列保证不重复而是让消费端实现幂等同一消息处理两次和一次的效果必须一致。顺序问题同样经典。Kafka只在分区内部保证消息顺序跨分区无法保证全局有序。如果业务要求“先创建订单再支付订单”这两条消息被发到不同分区就可能出现先支付后创建。解决思路是让业务相关消息携带同一个keyKafka会按key哈希到同一个分区从而保住局部顺序。你看这些问题的核心还是队列的“顺序、积压、消费能力”只不过从单线程变成了多消费者、从内存变成了磁盘分区算法训练里的队列知识依然是底层支柱。4.3 调用栈回溯栈到底是怎么“溢出”的栈在系统层的表现就是函数调用栈。每次函数调用都会压入一个栈帧栈帧里保存着函数的局部变量、参数和返回地址函数返回后就弹出栈帧。热词里的“backtrace栈回溯”“arm调用栈回溯”“中断栈针”都是系统调试中与调用栈直接相关的工具和概念——程序崩溃时通过栈回溯可以打印出完整的调用链定位是从哪一层函数进入死循环、哪一层越界访问了内存。那么栈溢出是怎么发生的两种常见情况一是递归调用太深每个递归层级都在栈上压入帧一直不返回栈空间耗尽二是函数里声明了超大局部数组比如在栈上分配几MB的数组直接把有限栈空间撑爆。C常见的Segmentation Fault很多时候就是栈帧过大或递归无限导致的。算法Day11学到递归改迭代本质上就是用显式的堆栈或者循环结构来替换系统调用栈避免递归深度受限于物理栈大小。这层理解能帮你把算法概念和真实程序运行时行为真正串起来。5. 刷栈与队列最容易踩的五个坑及应对方式5.1 数组循环队列的“满”“空”判断和模运算热词里有一句非常经典的原题话“假设以数组q[m]存放循环队列中的元素同时以rear和length分别指示环形队列中的队”。这是数据结构教科书里循环队列的必考设计。为什么需要循环队列因为普通数组队列出队后数组前部空间无法复用总会“队尾满、队头空”。用循环取模的方式rear和front都按(index 1) % m移动空间就能重复利用。如果只用front和rear两个指针队空和队满时front rear无法区分。所以常见解法是引入length或tag标记或者少用一个存储单元。以“rear指向队尾的下一个空位length存元素个数”的方式队空length 0队满length m队头位置front (rear - length m) % m入队q[rear] value; rear (rear 1) % m; length出队front (front 1) % m; length--。我第一次写时就在“rear到底指向队尾元素还是队尾下一个空位”上栽了跟头导致队头和队尾错位一位。建议初学时把“rear指向下一个空位”当作统一约定所有公式都基于这个约定推算逻辑才不容易乱。5.2 语言选型Python的list、dequeJava的Stack与ArrayDeque刷题时语言细节经常决定一道题会不会TLE。Python里用list模拟栈非常舒服append()和pop()都是O(1)但模拟队列千万别用list因为pop(0)是O(n)的数据量稍大就会超时。正确做法是用collections.deque它的popleft()是O(1)才符合队列理论复杂度。热词里“双端队列”就是deque它不仅支持队尾进出还支持队头进出在实现单调队列和0-1 BFS时几乎是标配。Java里有个历史遗留坑Stack类。它继承自Vector所有方法都加了synchronized并发场景下有锁开销而且它还用search()这类不常见方法干扰视线。官方文档明确建议用ArrayDeque来实现栈功能push()、pop()、peek()都是O(1)且无锁开销。用双端队列实现栈可能让新手不太习惯但这是更现代的实践。C则直接用std::stack、std::queue这类容器适配器即可但要注意它们的底层容器是deque默认情况下并没有特殊的性能问题。5.3 递归深度与显式栈什么时候需要把递归改写成迭代树的前序、中序、后序遍历是检验“栈与递归关系”的试金石。递归版本很简单但深度一大就会栈溢出原因就像4.3里说的系统调用栈空间有限。把递归改成显式栈的迭代版本本质上是用一个堆上的数据结构来替代系统栈堆内存通常大得多。以二叉树前序遍历为例递归版本是先处理根再递归左子树再递归右子树。迭代版本用栈就要反过来先把右孩子压栈再把左孩子压栈这样左孩子会先出栈被处理。压栈顺序和遍历顺序相反这是最容易写反的地方。后序迭代遍历更麻烦需要标记节点已经访问过右子树或用“逆前序翻转”的技巧。Day11建议至少把前序遍历的递归/迭代两个版本都手写一遍能亲手体会到“用栈保存待处理状态”到底是什么感觉。Python里如果实在想调深递归sys.setrecursionlimit()可以调大限制但这只是把上限抬高了物理栈空间耗尽该崩还是会崩。所以遇到深度不确定的DFS直接上显式栈或BFS才是工程上稳妥的解法。这也是为什么说栈与队列看似基础却直接关系到你能不能写出一个在大规模输入下不崩溃的程序。写到这栈与队列在我脑子里的形象已经完全变了——它们不是一个“先进后出/先进先出”的冷冰冰定义而是一套关于“状态保存”和“顺序调度”的通用思维模型。第11天的训练给了我一个特别明显的收获越基础的数据结构越值得用最深入的方式去理解因为后面所有复杂的树、图、搜索、动态规划追根溯源都会回到这两个容器身上。