又是打卡的一天。训练营走到第11天栈和队列专题的第二讲刚好是很多人的分水岭前面数组、链表、哈希表还能靠直觉硬刚到了这一章很多解法开始变得不像“人话”比如用栈模拟递归、用单调队列处理滑动窗口。这篇文章就把第二讲里我实际消化下来的核心东西整理出来——栈和队列的基本性格、典型题型的解题套路、几个容易让人深夜崩溃的坑以及它们和现实系统里消息队列、函数调用栈的关系。先说结论这天的内容如果只是背模板过两天就会忘。真正值钱的是搞清楚三件事——什么时候该用栈、什么时候该用队列、为什么在某个场景下单调结构能把暴力解法的时间复杂度从 O(n²) 降到 O(n)。下面按我自己的复习顺序来写。1. 栈和队列不只是两种容器是两种“调度哲学”1.1 先给“性格”画像LIFO 与 FIFO栈和队列的规则初看简单到不需要解释。栈是后进先出英文简称 LIFO学过数据结构的人都知道“最后放进去的元素最先被拿出来”。队列是先进先出FIFO就像食堂排队打饭先到的人先打。但真正开始做题之后会发现这两个规则背后是两种完全不同的调度哲学。栈强调的是“回溯”它天然适合保存现场、撤销操作、深度优先探索——你现在处理的事情永远是最新被推到桌上的那一件旧事情被压在最底下等新事情处理完再翻出来。队列强调的则是“按序推进”它天然适合广度展开、任务调度、一层一层往外扩散——你收到的每个请求按先后顺序被公平处理谁也别想插队。这个性格差异决定了你写算法时的直觉。看到“最近”“撤销”“匹配”“嵌套”这类词第一反应是栈看到“按层”“按顺序”“轮询”“公平”这类词第一反应是队列。训练营第二讲真正要练的就是这个条件反射。1.2 底层存法数组与链表怎么选栈和队列都是抽象接口底层既可以用数组实现也可以用链表实现。数组实现的好处是随机访问快、缓存局部性好缺点是扩容需要拷贝且固定容量的数组一旦满再 push 就要考虑扩容策略。链表实现的好处是插入删除只改指针、天然支持动态增长缺点是有额外指针开销频繁 malloc 在性能敏感场景下不太友好。做算法题时我们一般直接调用语言自带的结构——Python 的 list 配合 append/pop 就是栈collections.deque 就是双向队列C 的 stack、queue 底层默认是 deque。但训练营里经常会出“用两个栈实现队列”这类题目目的就是逼你把接口和底层拆开看上层只关心行为语义底层用什么东西存是你自己的自由。理解这一点比背下一百道题更有价值。1.3 为什么函数调用偏偏用栈很多人在学栈时会顺便接触到“栈帧”这个词但代码随想录这类训练营通常不会展开太多底层细节。我来补一笔程序在调用函数时系统为每次调用分配一小块内存区域记录参数、局部变量和返回地址这块区域就是栈帧。函数调用的嵌套顺序天然是先调用后返回和栈的 LIFO 规则完全吻合——所以运行时栈成了函数调用的默认实现方案。理解这一点对刷题很有用。递归函数写多了你会发现递归特别深时会栈溢出这不是因为你代码写错了而是因为每一次未返回的递归调用都在占用栈空间。所谓“递归改迭代”本质往往就是“用显式的栈模拟系统栈”把递归调用时本来由运行时压栈的操作改为自己手动压栈。第二讲里经常出现的“二叉树遍历的非递归写法”走的就是这条路。2. 从“会用”到“会选”栈与队列的经典应用地图2.1 栈的高频出场场景栈最经典的题目无非那几类括号匹配、表达式求值、单调栈、DFS 非递归化。括号匹配的题思路是遇到左括号就压栈遇到右括号就检查栈顶是否匹配匹配就弹出最后看栈是否为空。这里栈的作用不是存数据而是存一种“待闭合的期望”最近的左括号必须最先被闭合这种“最近优先匹配”的特性只有栈能提供。表达式求值稍微复杂一点。中缀表达式转后缀表达式或者直接用两个栈处理运算符优先级靠的都是栈对“当前操作符”的管理。操作符会等待优先级更高的操作符先完成这种“等待”关系天然是栈结构。单调栈则是在暴力枚举基础上的经典优化。比如“下一个更大元素”这类题暴力做法是每个元素向右扫描找第一个更大的值时间复杂度 O(n²)。用单调栈维护一个递减序列每个元素最多入栈出栈一次整体变成 O(n)。这个思想一定要吃透因为后面滑动窗口最大值、直方图最大矩形本质上都是单调栈或单调队列的变形。2.2 队列的高频出场场景队列的核心应用是广度优先搜索BFS。树的层序遍历、无权图的最短路径、迷宫问题的最小步数都是用队列逐层扩展。典型写法是初始节点入队然后循环地“出队一个、处理、把它的邻居入队”。队列还大量出现在生产消费类场景。单机里线程池的任务队列就是阻塞队列分布式系统里消息队列把生产者消费者的耦合度打散。刷题时可以不必理解底层细节但要建立联想FIFO 结构本质上是一种“缓冲 按序调度”机制。哪天看到题面里出现“待办顺序”“先后到达”“公平分配”这些词大概率要用上队列。2.3 进阶单调栈与单调队列第二讲和第一讲最大的区别我猜在于从“基础用法”升级到了“单调结构”。单调栈和单调队列不是新的数据结构而是你在使用栈/队列时刻意维持其中的元素有序。单调栈常见用法是维持一个从栈底到栈顶递增或递减的序列。以“下一个更大元素”为例维护一个递减栈遍历数组时如果当前元素比栈顶元素大说明当前元素就是栈顶元素的下一个更大元素弹出栈顶并记录答案否则入栈。每个元素最多被弹出一次总复杂度是 O(n)这就是用空间换时间的典型。单调队列则是把单调栈思想搬到队列上常见应用是滑动窗口最值。窗口滑动时需要快速知道当前窗口里的最大值。暴力扫窗口每次 O(k)总复杂度 O(nk)。用双端队列维护下标保证队首到队尾对应元素从大到小那么队首永远是窗口最大值的候选。这个结构在后续 DP 优化比如单调队列优化 DP里还会反复出现值得多花时间。3. 两道必练题手写双栈成队列与滑动窗口最大值3.1 双栈实现队列这道题可以说是考察“接口语义”的入门必刷题。题目要求用两个栈实现队列的 push、pop、peek、empty。我第一次写的时候思路很直接一个栈用来接收另一个栈用来输出。关键点是只有当输出栈为空时才把输入栈的元素全部倒过来。class MyQueue: def __init__(self): self.in_stk [] self.out_stk [] def push(self, x): self.in_stk.append(x) def pop(self): if not self.out_stk: while self.in_stk: self.out_stk.append(self.in_stk.pop()) return self.out_stk.pop() def peek(self): if not self.out_stk: while self.in_stk: self.out_stk.append(self.in_stk.pop()) return self.out_stk[-1] def empty(self): return not self.in_stk and not self.out_stk这个实现的巧妙之处在于摊还复杂度。每个元素最多被压入输出栈一次也最多被弹出一次所以虽然某一次 pop 可能触发 O(n) 的倒腾但连续 n 次操作的总代价是 O(n)平均每次 O(1)。面试如果追问复杂度要能把“摊还分析”讲清楚。常见的错误是没加“输出栈为空”这个前提每次都把输入栈元素倒过去顺序反而错乱。原因很简单如果输出栈还有剩余元素它们才是队列前端此时把新元素倒进来会插在它们前面破坏 FIFO。我踩过这个坑之后养成了一个习惯——写代码前先把“栈顶到底是哪个位置”在草稿纸上画清楚。3.2 单调队列求滑动窗口最大值另一道必练题是 LeetCode 239 滑动窗口最大值。题目不难理解一个数组和一个固定大小 k 的窗口窗口每次向右移动一位要求输出每个窗口里的最大值。用暴力法每次扫一遍窗口代码很简单但复杂度是 O(nk)。第二讲的核心训练点就是把它优化成 O(n)。用单调队列实现的关键有两点第一队列里存的是数组下标而不是值这样方便判断元素是否已经滑出窗口第二维护的同时要保证队首到队尾对应的值是递减的队首始终是当前窗口最大值的候选项。from collections import deque def maxSlidingWindow(nums, k): dq deque() res [] for i, v in enumerate(nums): # 移除已经不在窗口内的队首元素 while dq and dq[0] i - k 1: dq.popleft() # 从队尾开始弹出所有小于等于当前值的元素下标 while dq and nums[dq[-1]] v: dq.pop() dq.append(i) # 窗口满 k 个元素后再记录答案 if i k - 1: res.append(nums[dq[0]]) return res为什么是而不是因为如果队列里有和当前值相等的旧元素留着它没有意义——它永远不会比新元素更“大”而且它的下标更靠前会比新元素更早滑出窗口。弹出等于的情况可以让队列更精简代码也更稳。这个细节单独写出来不值钱但在比赛或笔试时恰好是区分代码质量的地方。窗口的左边界很多人容易算错。固定窗口大小为 k当遍历到下标 i 时窗口覆盖的范围是[i - k 1, i]所以队首下标小于i - k 1就要移除。这个边界一定要在插入新元素之前处理顺序反了会导致刚插进去的元素因为下标问题被错误弹出。4. 栈帧、调用栈和现实世界里的“栈与队列”4.1 栈帧的形成和回溯栈在真实系统里最直观的存在就是调用栈。每次函数调用运行时都会压入一个新的栈帧栈帧里保存着参数、局部变量、返回地址以及上一层栈帧的基址信息。当函数返回时根据栈帧里的恢复信息弹栈回到原来的执行点。“栈回溯”这个词在排查线下问题时经常遇到。程序崩溃时backtrace能打出当前调用链原理就是顺着栈帧链往下走打印每一层函数名和地址。理解了栈帧结构你再看那些崩溃日志里的调用栈就不会两眼发黑。比如遇到递归函数栈溢出报错栈里的重复函数名能精确告诉你递归卡在哪一层。做算法题时也会间接用到这个知识点。递归太深导致栈溢出时除了用显式栈或循环改写还可以考虑是否能把递归状态压缩成迭代状态。比如 DFS 遍历二叉树递归版本非常简洁但改成显式栈版本后遇到“最近访问到哪一层”这种问题时会更有掌控力。这正是第11天专题里“栈模拟递归”的价值所在。4.2 从数据结构队列到消息队列的一步之遥训练营里的队列是抽象的 FIFO 容器现实项目里的消息队列则更像它的“分布式放大版”。我们常说的 Kafka、RabbitMQ、RocketMQ本质上是把多个生产者想要传递给消费者的消息按顺序缓冲起来再由消费者按某种策略消费。数据结构上的“队列”是单机内存里的结构消息队列要解决的是跨进程、跨机器甚至跨机房的消息流转。既然聊到消息队列就多说一个高频面试问题消息队列重复消费问题。很多消息系统采用 at-least-once 投递语义意味着消费者可能收到重复消息比如消费后还没来得及确认宕机重启后消息被重新投递。解决办法不是让队列丢掉消息而是让消费者做幂等处理通过唯一业务 ID 去重、用状态字段判断是否已经处理过或者借助数据库的幂等键来保证重复消息不会产生重复效果。这件事对学算法的人有什么启发数据结构里的队列本身没有“去重”能力但我们可以通过外部状态来解决重复处理问题。这和 BFS 里的 visited 标记思路一模一样——BFS 也要保证同一个节点不会被入队两次。能从一个简单的容器抽象联想到分布式系统里的工程问题这种迁移能力才是训练营给不了但你又必须自己练的东西。4.3 无锁队列和高性能场景再往前走一步单机队列在高并发下会因为加锁产生争抢于是有了无锁队列。C 里无锁队列通常基于原子操作CAS实现用atomic变量维护头尾指针通过循环 CAS 完成入队出队。无锁不是真的没有协调而是把协调粒度降到硬件指令级别。刷题阶段没必要深究无锁队列的实现细节但可以记住一个结论并发场景下队列选型需要权衡吞吐、延迟和有界性。比如线程池的阻塞队列选用无界队列可能让积压任务把内存打爆选用有界队列又要有拒绝策略。这种思维回到算法题里就是“空间与时间的 trade-off”在工程里的投影。栈和队列在这里不再是二维纸面上的结构而是真实系统里天天在用的调度基础设施。5. 训练营打卡常见的五个坑与速查表5.1 空栈 / 空队列直接操作新手最容易犯的错误就是 pop 之前不判断是否为空。语言实现不同报错方式也不同C 的 stack 在空栈上 pop 是未定义行为可能直接崩溃Python 的 list 在空列表上 pop 会抛 IndexError。刷题时一定要养成“先判断再操作”的肌肉记忆尤其是同时操作两个栈或两个队列的题目有一个是空的很容易忽略。5.2 BFS 的 visited 标记时机很多人在 BFS 用队列时会踩这个坑节点在出队时才标记 visited。如果图里有环同一个节点可能在出队之前被多次入队导致队列膨胀甚至死循环。正确做法是在节点入队时就标记 visited这样后来遇到同一节点时会直接被过滤掉。刷题时可以用一个简单的二叉树层序遍历验证一下二叉树没有环这个问题不明显一旦换成无向图立刻就会暴露。5.3 单调队列的边界顺序滑动窗口最大值里移除过期下标和插入新下标这两步的顺序不能换。先插入新下标再移除过期下标理论上也能得到正确答案但会让你多处理一次“新下标可能也过期”的边界情况代码更容易出 bug。老老实实按“先清理左边界再维护单调性最后插入”的顺序写几乎不会错。5.4 递归改栈时的压栈顺序用栈模拟递归时压栈顺序经常会搞反。递归版本的逻辑是先处理左子树再处理右子树但显式栈版本里如果想先处理左子树就要先把右子树压栈再把左子树压栈因为栈是后进先出。这个细节第二讲里几乎必考我见过不止一个人在这里写出了完全反转的遍历顺序。解决办法还是老一套先在草稿纸上画出栈的变化再写代码。5.5 Python 递归深度与系统栈限制如果你用 Python 刷题递归深度默认大约 1000 层。有些树的深度很大直接写递归会报 RecursionError。可以用sys.setrecursionlimit()临时调高但更稳妥的方案是尽量把递归改成迭代。问题不在 Python 本身而是系统栈空间本来有限理解这一点能帮你形成“递归有成本”的意识而不是遇到递归就无脑套。问题典型症状核心原因对策空栈/空队列操作崩溃或越界缺少空判断操作前统一检查BFS 重复入队内存膨胀或死循环visited 标记太晚入队时立即标记单调队列边界错乱结果里有过期值清理与插入顺序颠倒先清左边界再维护单调递归改栈顺序错遍历顺序反转没考虑栈的 LIFO先压后处理的子结构递归深度超限RecursionError系统栈空间不足改迭代或手动调栈6. 复盘从一道题看栈/队列题的思考顺序6.1 四步选题法刷到第 11 天我开始总结自己的答题流程。拿到一道题我先问自己四个问题。第一步是暴力解是什么。几乎所有栈和队列优化题都能先写出一版 O(n²) 或 O(nk) 的直觉解法先把暴力解写对后面才知道优化在优化什么。第二步是判断数据流动的顺序。新数据和旧数据之间是“最近优先”的关系还是“先后有序”的关系前者往栈想后者往队列想。第三步是看能不能引入单调性。如果题目需要反复找“最大/最小/第一个更大/第一个更小”单调栈和单调队列是天然的候选。第四步是处理边界。窗口过期、栈空、队列空、重复元素一个都不能漏。以“每日温度”这道题为例暴力做法是每往后找一个比当天温度高的日子O(n²)。观察发现每天要等“下一个更大温度”而且“后到的温度会覆盖先到的期待”这就是典型的单调栈问题。维护一个递减栈遍历温度数组遇到更高温度时弹出栈顶并计算天数差。整个过程思路非常顺用这套四步法基本不会卡壳。6.2 我的个人体会训练营走到这里最大的感受是栈和队列的知识密度不高但延展性极强。它们看着只是两种简单容器却能牵扯出函数调用栈、消息队列、单调优化、并发调度这些东西。算法题的价值不止于面试而是让你对一个日常不再细想的概念产生“原来里面还有这一层”的感觉。我个人刷这一专题时有个习惯每道题做完都强行给自己讲一遍“为什么这个结构选栈而不选队列”或者“为什么这道题能用单调性优化”。讲得出来才算真正吸收。第二讲里我卡得最久的是滑动窗口最大值不是因为代码写不对而是不理解为什么要维护一个递减的队列。后来自己画了十几分钟窗口滑动过程的图把队列里每个下标的进出顺序都标出来一下就豁然开朗了。如果你也卡在某道题上别急着背答案先画图先讲给自己听。栈和队列这两兄弟摸清楚脾气之后后面的二叉树、图论、动态规划会好走很多。