代码随想录刷到 Day13正好是栈与队列专题。这一天的四道题——232.用栈实现队列、225.用队列实现栈、20.有效的括号、1047.删除字符串中的所有相邻重复项——看着是四道独立的题实际串起来就是一条完整的思路链先用栈和队列互相模拟去理解两者的行为差异再用栈去解决括号匹配和相邻重复删除这两个最经典的场景。如果你正在刷题入门阶段这四道题属于那种“搞懂了就不难没搞懂就处处别扭”的类型非常值得停下来细细复盘。这篇文章就把我自己的实现思路、踩过的坑和细节上的优化过程完整写出来。1. 先搞懂栈与队列的本质差异1.1 栈只从一端进出的“叠盘子”栈这个东西你用代码实现就是几行但它的行为特性你得先刻在脑子里只能在同一端栈顶做插入和删除。我用叠盘子来理解它——你往一摞盘子上叠新盘子只能放在最上面拿盘子也只能从最上面拿。想拿最下面的那个盘子对不起你得先把上面的全挪走。所以栈的进出顺序是后进先出LIFO最后一个进去的元素永远最先出来。工程里的例子到处都是文本编辑器的撤销CtrlZ就是一个栈每次撤销都是撤销最近一次操作浏览器后退按钮也是栈你点后退返回的是最近访问的页面。函数调用栈更是基础中的基础一层层函数调进去再一层层返回来顺序严丝合缝。在 Python 里用list模拟栈极方便append()入栈、pop()出栈两个操作都是 O(1)。需要注意的就是别用list头部的操作比如pop(0)、insert(0, ...)那是 O(n) 的栈的语义也完全不是这样。1.2 队列两端的“排队通道”队列对应的生活场景就是排队我常举的例子是排队买奶茶。新来的人排在队伍末尾队伍最前面的人先拿到奶茶走人。所以队列是先进先出FIFO先来的先走后来的后走。实现队列在 Python 里有个小讲究别用list模拟队列的头部弹出。list.pop(0)会把后面所有元素都往前挪一位时间复杂度 O(n)数据一多直接拉胯。正确的做法是用collections.deque它的append()和popleft()都是 O(1)。deque 底层是双向链表或者分块数组反正两头操作都高效就对了。1.3 为什么要把这两个结构放在一起学栈和队列都是线性表底层都可以用数组或者链表实现唯一的区别就是出入口规则。232 题要求用栈实现队列225 题要求用队列实现栈这种“互相模拟”的题目真的是检验理解程度的试金石。你背会“栈是 LIFO、队列是 FIFO”这句话很容易但当你真正动手用栈去模拟队列行为时才发现顺序反转、双栈协作这些细节一写就暴露你懂没懂。从刷题路线的角度看栈与队列也是后面一堆难题的地基。单调栈、滑动窗口、表达式求值、BFS 的队列实现全都依赖今天这几道题建立起来的直觉。所以 Day13 这四道题刷的时候别急着 AC多想想每一步为什么这么写。2. 232. 用栈实现队列双栈倒腾才是正解2.1 核心思路两个栈一个管进一个管出一个栈实现不了队列原因很简单栈是 LIFO你往栈里依次 push 1、2、3pop 出来是 3、2、1顺序反了。队列需要的是先进先出你希望 pop 出来是 1、2、3。怎么把顺序再反转一次再用一个栈。第一个栈叫stack_in专门负责接收 push 进来的元素第二个栈叫stack_out专门负责 pop 时提供元素。关键操作发生在 pop 的时候如果stack_out是空的就把stack_in里的所有元素全部弹出再按顺序压进stack_out。这样顺序被反转了两次负负得正stack_out的栈顶正好是队列的队头。我实际推演一遍你就懂了push 1、2、3 后stack_in [1, 2, 3]栈顶是 3。现在要 popstack_out为空执行迁移从stack_in依次弹出 3、2、1压入stack_out迁移完stack_out [3, 2, 1]栈顶是 1。stack_out.pop()返回 1完美这就是队列应该弹出的第一个元素。这里有个很重要的细节必须等stack_out空了才能从stack_in倒数据而且一倒就是全部倒完。为什么你想想如果stack_out里还有元素时就往里面倒新数据新数据会压在旧数据上面那 pop 出来的顺序就乱了如果只倒一半另一半留在stack_in里下次再倒时顺序又对不上。所以规则就是stack_out空 → 一次性倒空stack_in。2.2 代码实现边写边讲每个方法class MyQueue: def __init__(self): self.stack_in [] # 负责入队 self.stack_out [] # 负责出队 def push(self, x: int) - None: self.stack_in.append(x) def pop(self) - int: if self.empty(): return -1 if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) - int: # 复用 pop再把元素还回去 res self.pop() self.stack_out.append(res) return res def empty(self) - bool: return not self.stack_in and not self.stack_outpush没什么好说的直接进stack_in。pop里第一行if self.empty()是防御性判断LeetCode 的题目保证不会对空队列调用 pop但写出来更稳。中间那段 while 是核心只在stack_out为空时才触发迁移迁移时用while self.stack_in保证一次倒干净。peek我用了“复用 还回去”的写法先调用pop()拿到队头元素再把元素压回stack_out。因为pop()已经把迁移逻辑处理好了所以peek就不用重复写迁移的代码这也是一个减少重复代码的小技巧。不过要注意pop()里我加了if self.empty(): return -1所以peek复用的时候也得接受 pop 返回的是有效元素不能拿 -1 当真元素压回去。实际刷题时题目保证不会空调用这个问题不大但思路要清晰。2.3 复杂度分析和两个容易忽略的细节先算复杂度。push就是一次 appendO(1)。pop乍一看是 O(n)因为要倒数据但仔细想想每个元素最多被弹出stack_in一次、压入stack_out一次真正被 pop 也就是一次。整体看n 次操作总的元素移动次数是 O(n)均摊到每次操作就是 O(1)。这就是摊还分析amortized analysis面试里常被问到建议自己心里过一遍这个推导。第二个容易忽略的细节是peek的另一种写法。如果你不想用“pop 再还回去”这种复用方式也可以直接判断stack_out是否为空为空就先迁移然后返回stack_out[-1]。好处是peek不会改变队列状态逻辑更直白def peek(self) - int: if not self.stack_out: while self.stack_in: self.stack_out.append(self.stack_in.pop()) return self.stack_out[-1]两种写法都对我个人的习惯是复用pop因为pop已经保证了迁移逻辑只会写一份。但面试的时候如果面试官让你分别实现 peek 和 pop用第二种会更直观不容易绕晕。3. 225. 用队列实现栈两种写法各有取舍3.1 两个队列的写法把队尾“抬”到队首队列模拟栈思路和栈模拟队列不太一样。栈的 pop 要弹出最后进来的元素也就是队列的队尾但队列只能从队头弹出元素所以核心操作就是把队尾元素变成队头元素。两个队列的做法是维护一个主队列queue_inpush 时直接进主队列。pop 时把主队列里除了最后一个元素以外的所有元素全部挪到辅助队列queue_out此时主队列剩下的那个元素就是最后进来的“栈顶”直接popleft()弹出。然后交换两个队列的引用保证下次继续用主队列接收新元素。我举个例子队列里现在是 [1, 2, 3]队头是 1队尾是 3对应栈顶是 3。要 pop把 1、2 挪到辅助队列主队列只剩 [3]弹出 3。此时辅助队列是 [1, 2]交换引用主队列变成 [1, 2]下一次 pop 就继续把 1 挪走弹出 2。顺序完全符合栈的后进先出。3.2 一个队列的写法循环左移 n-1 次其实仔细想辅助队列并没有存什么特殊数据它只是临时存放“暂时不要的元素”最终还是要回到主队列。既然这样用一个队列就够了pop 的时候把队头的元素依次弹出、再压到队尾循环 n-1 次队头就是原来的队尾。代码非常干净from collections import deque class MyStack: def __init__(self): self.queue deque() def push(self, x: int) - None: self.queue.append(x) def pop(self) - int: if self.empty(): return -1 for _ in range(len(self.queue) - 1): self.queue.append(self.queue.popleft()) return self.queue.popleft() def top(self) - int: res self.pop() self.queue.append(res) return res def empty(self) - bool: return not self.queue看pop里的那个 for 循环len(self.queue) - 1次每次把队头挪到队尾。比如队列是 [1, 2, 3]第一次 popleft 拿到 1append 回去变成 [2, 3, 1]第二次 popleft 拿到 2append 回去变成 [3, 1, 2]循环结束队头是 3popleft()弹出正好是栈顶。这是一种“轮转”的思路队列就像一个环形结构你不停地从一端取元素放到另一端转一圈之后原来的队尾就自然到了队头。3.3 对比push O(1) 好还是 pop O(1) 好用上面的写法push 是 O(1)pop 是 O(n)。那能不能反过来push O(n)、pop O(1)也可以。做法是每 push 一个新元素就把队列里已有的元素全部循环挪到新元素后面这样新元素永远在队头pop 的时候直接popleft()就行。两种方案总的均摊复杂度其实一样n 次操作都是 O(n) 的移动总量区别只是把开销放在哪。我个人的建议是记住“单队列 pop 时轮转”这种写法它最好理解、代码最少。面试时如果你能主动提一句“其实一个队列就够了”会显得你对这个问题的认识更深一层。再补充一个 top 的实现细节。上面代码里top是复用pop然后把元素还回去这和 232 的 peek 思路完全一样。还有一种做法是维护一个top_value变量每次push时更新它为最新入队的元素这样top就是 O(1)。但用“复用 还回去”的方式代码统一也不容易漏更新变量我更喜欢这个。4. 20. 有效的括号栈的教科书级应用4.1 无效括号的三种情况这题我当年第一次做的时候总觉得要分很多种情况处理后来理清楚了其实就三种左括号多了比如(()遍历完整个字符串栈里还剩一个(没被匹配说明多了个左括号。右括号多了比如())遍历到第二个)时栈已经空了没有左括号可以和它匹配。左右括号类型不匹配比如(]遍历到]时栈顶是(和]对应的[对不上。只要代码把这三件事都判断到这题就稳了。思路也很直接遍历字符串遇到左括号就入栈遇到右括号就检查栈顶。栈顶如果是匹配的左括号就弹出去如果栈空或者不匹配直接返回 False。遍历结束后如果栈为空说明所有左括号都被匹配掉了返回 True。4.2 代码实现用一个字典做映射def isValid(s: str) - bool: if len(s) % 2 1: return False stack [] mapping {): (, ]: [, }: {} for ch in s: if ch in mapping: # 当前是右括号 if not stack or stack[-1] ! mapping[ch]: return False stack.pop() else: # 当前是左括号入栈 stack.append(ch) return not stack这里我用了一个字典mapping把右括号映射到对应的左括号。这样判断stack[-1] ! mapping[ch]一行就能完成“类型不匹配”的校验不用写三个 if。哈希映射的好处是以后如果括号类型多了比如加上[、]以外的自定义标记只需要往字典里加一对映射代码逻辑不用动。4.3 易错点全是我刷题时踩过的第一个坑访问stack[-1]之前必须先检查stack是否为空。Python 里空列表取stack[-1]会直接抛IndexError如果不加not stack这个判断遇到)这种开头就是右括号的用例直接崩。第二个坑判断一个字符是否右括号用if ch in mapping。这个写法很巧妙因为字典的 key 全是右括号ch in mapping就等价于判断 ch 是不是右括号。反过来左括号就走 else 分支入栈。不需要额外再维护一个左括号集合。第三个坑奇数长度直接剪枝。字符串长度为奇数括号永远不可能全部匹配直接返回 False。这是一个小优化但能体现出你对题目边界条件的把握。第四个坑处理多层嵌套时的栈深度。比如[{([({})])}]这种深层嵌套的字符串显式用栈是安全的因为 Python 的递归深度有限制。这题如果用递归思路去做推导嵌套一深就容易碰到递归层数上限但用循环 显式栈就完全没有这个问题。这题背后的应用场景也很实在编译器的语法检查、IDE 里的括号自动匹配高亮、XML/HTML 标签嵌套校验本质上都是同一个模型。刷完这题你对“CPU 怎么校验括号”就有了具体的画面感。5. 1047. 删除字符串中的所有相邻重复项消消乐背后的栈思路5.1 为什么栈能高效解决“消消乐”先看题目给的例子abbaca。第一次看到bb相邻重复删掉字符串变成aaca。这时候aa又相邻重复了再删最后得到ca。关键点在于删除一对字符后新的相邻关系可能继续触发新的删除。这个“连锁反应”如果用暴力解法每删一次就要重新扫描字符串时间复杂度很高。但如果你用栈一切就顺理成章了遍历字符串每次只跟栈顶比较。如果当前字符和栈顶相同说明栈顶和当前字符是一对相邻重复项把栈顶弹出去相当于“消掉”如果不同就把当前字符压入栈顶等待后续匹配。拿abbaca推演一下a 入栈 → b 入栈 → 下一个 b 和栈顶 b 相同弹出 b → 下一个 a 和栈顶 a 相同弹出 a → 当前栈空 → c 入栈 → a 入栈。最后栈里剩[c, a]拼成字符串就是ca。这个模型像什么我觉得特别像消消乐或者俄罗斯方块——新方块落到顶部如果和上一个方块颜色一样就消除不一样就叠上去。每次只要关注“当前的最后一块”就够了之前的历史都被栈牢牢记着。5.2 代码实现前后两种思路对比def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)就这么多核心逻辑只有三行入栈、比较、弹出。时间复杂度 O(n)空间复杂度 O(n)n 是字符串长度。我再看另一种写法用双指针做原地操作可以把空间省到 O(1)如果忽略结果字符串本身占用的空间。思路是把字符串转成字符数组用slow指针表示“当前结果写到哪了”用fast指针遍历原字符串def removeDuplicates(s: str) - str: chars list(s) slow 0 for fast in range(len(chars)): if slow 0 and chars[slow - 1] chars[fast]: slow - 1 else: chars[slow] chars[fast] slow 1 return .join(chars[:slow])slow这个指针模拟的就是“栈顶位置”。slow 0相当于stack非空chars[slow - 1]相当于stack[-1]。如果相同就slow - 1相当于弹出如果不同就把chars[fast]写到slow位置然后slow 1相当于入栈。这个优化有点意思但我的建议是第一步先用栈版本 AC再去看原地双指针。双指针思路在代码上确实省了空间可读性不如栈版本直观。面试的时候先把栈版本解释清楚再提一句“可以用双指针做原地优化”就显得你对复杂度和代码思路都有掌控。5.3 和“有效的括号”放在一起看模板就出来了20 题和 1047 题一个是括号匹配一个是相邻重复删除表面看起来不同但用栈的姿势一模一样遍历每个字符跟栈顶比较能匹配就弹出不能匹配就入栈。20 题里遇到右括号检查栈顶是否为对应的左括号是则弹出否则返回 False。1047 题里遇到字符检查栈顶是否相同是则弹出否则入栈。区别只在比较条件和弹出条件剩下的骨架完全一致。所以很多刷题人会告诉你栈的“相邻消除类”题目是有一套通用模板的。你刷完这两题可以自己总结出一句话“凡是需要回头看最近一个元素、并且可能产生连锁反应的问题优先想栈。”后面再遇到类似题目比如“删除字符串中出现次数大于 2 的相邻重复项”“行星碰撞”这类变体你就能触类旁通了。6. 四道题纵向对比与刷题心得6.1 一张表对照核心考点四道题全部刷完我习惯放在一起做一次横向对比这样复习时一眼能抓住重点。题号题目核心考点时间复杂度空间复杂度最关键的一步232用栈实现队列双栈协作顺序反转两次push O(1) / pop 均摊 O(1)O(n)只有 out 栈空了才一次性倒数据225用队列实现栈队列轮转把队尾移到队头push O(1) / pop O(n)O(n)pop 前循环左移 n-1 次20有效的括号栈顶比较 哈希映射O(n)O(n)先判空再访问栈顶1047删除相邻重复项栈顶比较 相邻消除O(n)O(n)相同就弹不同就压从这张表能看出两个特点。第一时间复杂度的关键在于你要不要访问“另一头”的元素栈访问的是栈顶天然顺手队列访问队尾就得先把前面的元素挪走。第二空间复杂度基本都是 O(n)因为需要用一个额外容器存储“还没处理完的元素”这也是这类题型的普遍代价。6.2 栈与队列互相模拟的统一思维模型232 和 225 放在同一天刷最大的收获是你会发现“用 A 模拟 B”是有通用套路的模拟的本质是用底层数据结构的操作去实现目标数据结构的操作语义。你需要承认一个现实底层数据结构做不到“直接”完成目标操作所以你要么做额外搬运队列模拟栈时的轮转要么做顺序反转栈模拟队列时的双栈。具体到操作层面就两个关注点迁移时机栈模拟队列时必须在 out 栈为空才迁移队列模拟栈时必须在 pop 时一次性把前 n-1 个元素挪走。时机错了顺序就乱了。空判断pop 和 top/peek 之前都要判断当前是否为空不然就会越界或返回错误结果。我刷完这两道模拟题之后再看 20 和 1047忽然觉得前面两题练的“对栈顶和队头的敏感度”直接派上了用场。这就是为什么刷题路线要把它们安排在同一天——模拟题训练你对数据结构行为的理解应用题训练你把它用到具体场景中的能力。6.3 我的踩坑记录和几个实用习惯最后分享几个我在实操中反复踩过、后来养成习惯的点空容器访问越界。Python 里stack[-1]在空栈时报 IndexErrorpopleft()在空队列时也会报错。所以只要涉及取栈顶/队头我写的第一个判断永远是if not stack / if not queue。这个习惯在 20 题和 1047 题里尤其关键因为你不知道测试用例里会不会突然来一个空字符串或者以右括号开头。peek/top 复用 pop 时记得还元素。232 和 225 的题目都要求实现 peek/top我一开始写 peek 时直接对底层容器取[-1]结果没有考虑数据还在 stack_in 里的情况。后来改成复用 pop 再还回去逻辑就顺了。但“还回去”这个动作容易漏你要清楚自己写的 peek 是否改变了数据结构状态。Python 里 deque 和 list 的选用。只要涉及“队列”操作我统一用collections.deque哪怕刷题时数据量不大这是习惯问题——避免某天遇到大数据量时直接用list.pop(0)写出 O(n) 的代码。而模拟栈就用普通listappend/pop足够。先写方法签名再填实现。像 232、225 这种要设计一个类的题我拿到题先把__init__、push、pop、top/peek、empty的签名列出来再一个个想每个方法要调用哪些辅助逻辑。这个方法能让你避免“写一个方法时发现另一个状态变量还没初始化”的尴尬。这四道题刷完我对栈和队列的理解明显上了一个台阶尤其是“什么时候用栈、什么时候用队列”不再靠背而是能根据题目场景自然判断。建议你也尝试在做完一组题后像我一样画一张对比表、总结一个通用模板这种“复盘”比多刷十道新题都管用。