《代码随想录》刷到day11终于进入栈与队列part2的实战环节。day10用栈模拟队列、用队列模拟栈刚把两种结构的基本性质摸清从day11开始题目画风突变全部变成给你一个真实的问题场景你自己判断该用栈还是队列。这天安排的20.有效的括号、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值看起来题型各不相同实际上全在围绕一个核心栈这种后进先出的结构最擅长处理需要回头看最近状态的问题。如果你正在跟着刷这套题单或者刷了不少题但遇到栈和队列到底什么时候用哪个依然靠感觉这篇笔记应该能帮上忙。我会把三道题的完整思路、Python写法以及我实际踩过的坑都摊开来说。1. 为什么day11三道题全在考栈先搞懂栈和队列的使用边界1.1 从day10到day11栈和队列在使用上的分工day10的两道模拟题很多初学者会觉得绕用两个栈倒腾来倒腾去模拟队列用队列反着模拟栈。但做完之后你对这两种结构的性格就应该有直觉了——栈讲究后进先出你最后放进去的东西第一个被拿走队列讲究先进先出谁先来谁先被处理。到了day11三道题不再考你怎么实现栈和队列而是考你怎么识别它们。拿括号匹配来说当你扫到一个右括号的时候心里想的一定是它应该和哪个左括号配对答案永远是最靠近它的、还没被匹配掉的那个左括号。这个最近的、还没被处理的、随时可能被顶掉的状态就是栈的舒适区。后进先出在题目里不是概念而是实实在在的执行规则。队列干的则是另一件事按顺序排队处理。取号办事、打印店排队、商家按订单顺序发货任务先到先得这是队列的舒适区。工程里的阻塞队列、线程池任务队列、消息队列全都建立在这个基础上。所以判断一个场景到底用栈还是用队列看的不是有没有顺序而是你更关心最近来的那一个还是最早来的那一个。我平时刷题就靠下面这张表快速定位判断维度栈队列核心规则后进先出LIFO先进先出FIFO关注对象最近一个待处理状态最早一个待处理状态典型问题括号匹配、表达式求值、函数调用、DFS任务调度、消息缓冲、窗口滑动day10/11里的角色被用来模拟队列也被20/1047/150直接使用被用来模拟栈后续滑动窗口也登场1.2 拿到题先问自己我需要记住什么状态我刷题有一个习惯看到题不先想数据结构先想如果我人肉按顺序处理脑子里需要记住什么。如果需要记住的是最近一次看到的那个那就用栈如果需要记住的是最早来的那个那就用队列。这个判断做完解题方向基本不会偏。很多人在day11卡住不是不会写代码而是压根没想清楚为什么栈是答案。带着这个视角去看三道题每一道的解法都会自然很多。还有一个容易误解的地方不是所有带顺序的问题都用队列。day11的三道题虽然也涉及字符串的遍历顺序但处理的关键是最近状态所以是栈只有那些先到先消费、严格按到达顺序处理的场景才是队列的地盘。2. 有效的括号LeetCode 20匹配类问题的栈解法2.1 题解思路与存对应右括号的写法题目是给定一个只包含(、)、{、}、[、]的字符串判断括号是否有效。所谓有效就是每个左括号都有同类型的右括号闭合而且闭合顺序必须正确。思路可以拆成四步遇到左括号把对应的右括号压入栈遇到右括号检查栈顶是不是和当前字符相同相同就弹出继续扫描不同或栈已经为空说明前面的某个左括号没有正确闭合直接返回False。为什么我在这里建议存对应的右括号而不是存左括号因为写起来更舒服。如果存左括号遇到右括号时还得查表确认这个右括号和栈顶的左括号是不是一对如果存右括号遇到右括号只需要一次判断。代码少了分支人也少想一层映射。2.2 代码实现与三个容易踩的坑class Solution: def isValid(self, s: str) - bool: if len(s) % 2 1: return False pairs {(: ), [: ], {: }} stack [] for ch in s: if ch in pairs: stack.append(pairs[ch]) else: if not stack or stack[-1] ! ch: return False stack.pop() return not stack代码不长但有几个坑必须注意。第一弹栈前一定先判空。Python的list在空栈上pop会直接抛IndexError这个错误往往不是逻辑问题而是你没预料到输入字符串可能以右括号开头。第二奇偶剪枝。字符串长度为奇数时括号不可能全部配对直接返回False虽然只省一次遍历但能帮你在动手前先想边界。第三遍历结束不代表成功。比如()(这个字符串前面能匹配最后栈里还留着一个左括号说明有括号没闭合所以最终返回值要写成not stack而不是True。2.3 这类题在工程里的真实投影括号匹配并不只是LeetCode的玩具题。你在IDE里写代码括号高亮、未闭合提示是编辑器在实时做栈匹配你在解析HTML/XML时看到标签未闭合的报错同样是栈在起作用。以后真要做代码格式化插件、写类似Lint的检查工具这个问题一定会再出现。刷题时多花几分钟想想它现实里长什么样比单纯背过代码有用得多。3. 删除字符串中的所有相邻重复项LeetCode 1047栈模拟消消乐3.1 贪心消除与连锁反应题目要求给出一个小写字母组成的字符串反复删除两个相邻且相同的字母直到不能继续删除返回最终字符串。abbaca的消除过程是先删除中间的bb变成aaca再删除中间的aa变成caca没有相邻重复结束。这题很多人第一反应是直接扫描一遍看到重复就删但容易忽略连锁反应删掉bb之后两侧的a又拼到了一起变成新的相邻重复。如果只扫一遍下标处理完这次重复还得回头重新看代码写起来很纠结。用栈就自然了从左到右遍历字符串每次把当前字符和栈顶比一比。相同说明新来的字符和最近的一个待定字符撞车了直接把栈顶弹出这不光消掉了当前字符还让栈里更早的元素浮到了栈顶不同就把当前字符压进去。连锁反应由栈一站式接管不需要你手工回头。提示两个相邻元素需要相互作用而且作用结果会影响更前面的元素时栈就是默认选项。3.2 用list当栈以及为什么不要原地改字符串class Solution: def removeDuplicates(self, s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)代码很短但有个性能细节值得说。Python里也有用结果字符串本身当栈的想法比如res[-1] ch就弹出否则拼上去。但字符串是不可变对象每次拼接或删除都会生成新字符串假设字符串长度是n最坏情况下要做O(n)次这种操作总复杂度会退化到O(n²)。用list当栈追加和弹出都是O(1)最后一次性join才是稳妥的写法。3.3 同类型变种行星碰撞删相邻重复项换个包装就是LeetCode 735行星碰撞。题目里每颗行星有大小和运动方向向右为正、向左为负两个方向相反的行星相遇时小的会被撞碎一样大就同归于尽最后剩下的行星按原顺序返回。解题思路一模一样从左到右遍历如果栈顶行星向右、当前行星向左就一定有碰撞根据大小关系决定谁留下其他情况直接入栈。做完1047再写735你会发现代码框架几乎没变变的只是什么条件下弹栈的判定。这类题的关键不是记住题目而是记住场景判断。4. 逆波兰表达式求值LeetCode 150后缀表达式与栈的计算逻辑4.1 先搞懂什么是后缀表达式逆波兰表达式其实就是后缀表达式操作符写在两个操作数的后面。12写成后缀是1 2 (12)*3写成后缀是1 2 3 *。可能有人会问好好的中缀表达式不用为什么要折腾成后缀因为计算机处理括号和优先级很费劲。中缀表达式里12*3到底先算哪个得看优先级表后缀表达式则完全没有歧义操作数的先后顺序已经把运算顺序锁死了。编译器和计算器在处理表达式时常常先把中缀转成后缀再用栈一路求值省去优先级判断的开销。4.2 求值逻辑与操作数顺序的坑这道题给的是一个已经合法的后缀表达式tokens数组我们只需要负责求值遇到数字压栈遇到运算符弹出两个操作数先弹出的是b后弹出的是a计算a op b再把结果压栈遍历结束栈顶就是最终结果。这里有个顺序陷阱。加减乘除里加法和乘法不受操作数顺序影响但减法和除法必须严格区分栈里如果从底到顶是[3, 4]遇到减号pop()先拿4再拿3实际要算的是3-4而不是4-3。写错顺序除法直接变成倒数减法变成相反数这个坑值得专门划线。4.3 代码实现与Python负数的除法陷阱from typing import List class Solution: def evalRPN(self, tokens: List[str]) - int: stack [] for token in tokens: if token in {, -, *, /}: b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) else: stack.append(int(a / b)) else: stack.append(int(token)) return stack[0]Python的除法坑在除法分支里题目要求除法向零截断而Python的a // b是向下取整。举例来说6除以-132向零截断得到06 // -132结果是-1。所以除法这里不要写a // b要用int(a / b)得到向零取整的结果。注意a // b 是向下取整int(a / b) 是向零取整也就是这里题目要求的截断行为。如果你平时用别的语言写这个题转到Python后特别容易在负数用例上翻车。我第一次就用整数除法写完跑到负数用例直接错排查半天才反应过来是取整方向的问题。4.4 后缀表达式求值在真实系统里的样子逆波兰表达式不是纯粹的竞赛概念。JVM的字节码执行就是典型的基于栈的求值模型指令从操作数栈取数、计算完压回栈顶和这道题的流程几乎一致。以后去研究解释器、计算器、表达式引擎都会看到后缀表达式和栈的影子。把150题做透相当于提前把这类系统的核心逻辑摸了一遍。5. 栈不只是数据结构从三道题到调用栈与回溯5.1 函数调用本身就是一座栈刷完三道题有一个认知层面的收获值得单独讲栈不只是算法题里的数据结构程序能跑起来靠的就是栈。你调用一个函数系统会往调用栈里压一帧存放局部变量和返回地址函数执行完这一帧被弹出回到调用点继续执行。递归为什么可能栈溢出因为每深入一层就压一帧帧数超过栈空间上限就炸了。搜索引擎热词里的backtrace栈回溯、ARM调用栈回溯本质上是把这个运行时栈的内容展开给你看当前代码执行到哪一行、中间经过了哪些函数调用。理解了这一点你会觉得调试器里的call stack面板不再神秘它就是运行时的那座栈。5.2 递归、回溯与显式栈的同构关系day11三道题是我们手动管理栈让系统帮我们管理栈的情况则是递归和回溯。很多人觉得回溯算法玄乎其实回溯就是深度优先搜索加上状态撤销而DFS的遍历本来就依赖栈你显式地写一个stack或者直接交给递归去用系统调用栈。我学到这里最大的变化是不再把递归和迭代当成两种割裂的写法而是当成同一种思想的两种实现。需要精确控制回溯时机、担心栈溢出的时候用显式栈递归写法自然贴合问题结构的时候直接递归。理解这一点后面刷二叉树和回溯专题时会轻松很多。5.3 递归改迭代的关键控制压栈与弹栈时机举一个最常见的例子二叉树中序遍历递归版三行写完迭代版就要自己维护一个显式栈先把当前节点一路向左压到底然后弹出节点访问再转向右子树。这个一路压左、弹栈访问、转向右子树的过程本质就是模拟系统调用栈在递归时做的事。递归的好处是自动完成压栈弹栈缺点是栈帧里塞了很多额外信息显式栈则只存你关心的信息因此更好控制深度也方便在弹栈时做剪枝。对于正在刷《代码随想录》的同学day10亲手实现过栈的push和popday11又在多个算法题里反复操作栈这些练习最终会沉淀成一种手感遇到需要深度优先探索、需要状态撤销的问题你知道栈是那个幕后的主角。6. 预习接下来要面对的单调队列与优先队列6.1 滑动窗口最大值为什么普通队列不够用day11之后的日程里会出现两道经典题239.滑动窗口最大值、347.前K个高频元素。这里提前打个预防针。239题要求在滑动窗口里依次输出最大值。如果每次重新扫一遍窗口复杂度是O(nk)数据量一大必然超时。正解是设计一个单调队列队列里的元素从队首到队尾保持递减队首永远是当前窗口的最大值。新元素入队时先把队尾所有比它小的元素弹掉再把新元素放进来窗口左边界移出时如果移出的正是队首元素就让它出队。这里要用到双端队列deque因为需要在队尾弹出、队首弹出、队尾加入三个位置同时操作。我在刷这道题之前一直以为队列只能严格先进先出做完才发现数据结构是死的但你完全可以根据业务需求定制它的进出规则。单调队列这种不按常理出牌的结构在滑动窗口类问题里非常常见。6.2 前K个高频元素从栈到堆理解优先队列347题的思路是统计频率后取前K个高频元素。这一步用普通栈和队列都不太顺手最适合的是优先队列也就是堆。维护一个大小为K的小顶堆堆顶是堆里最小的一个每遇到一个频次比堆顶高的元素就把它替换进去最终堆里剩下的就是频次最高的K个。Python里直接用heapq模块就能实现。顺带一提热词里频繁出现的阻塞队列、无锁队列也和队列的工程应用有关。线程池用阻塞队列缓冲任务生产者把任务放进去消费者从里面取取不到就阻塞等待无锁队列在高并发场景用CAS原子操作避免锁竞争消息队列解决分布式系统的异步解耦又带来了重复消费、消费顺序这类工程问题。这些都是生产环境里真正高频的话题但地基还是在day11这个地方打的。6.3 顺带聊聊队列在真实系统里的角色队列在代码里写起来只有几个方法但在真实系统里无处不在。阻塞队列是线程池的默认缓冲带消息队列是微服务之间的异步通道滑动窗口是流量控制的基础。这些名词乍看陌生但核心都逃不开先来先服务或者按某种规则顺序处理。反过来看栈应用同样藏在日常里浏览器的前进后退、编辑器的撤销、括号匹配、函数调用、表达式求值。刷完day11再去回想这些场景你会发现自己看底层系统的眼光不一样了。数据结构不难难的是在合适的场景把它认出来。最后分享一点自己的体会。day11这三道题难度不高但价值很高。我刷完之后最大的收获不是记住解法而是形成了条件反射——看到匹配、对称、相邻消除、后缀运算第一反应是栈看到顺序缓冲、滑动窗口、先来先服务第一反应是队列。建议你也试试每刷完一道题用一句话给自己解释为什么这里必须用栈/队列这个习惯比单纯把题做完有用得多。