算法训练营刷到 day10栈和队列专题正式开始了。整个代码随想录训练营走到这里其实是一个很微妙的分水岭前面几天的数组、链表、哈希表多少还能靠直觉硬写到了栈和队列突然就要求你学会“抽象”——不是拿现成的数据结构去套题目而是用底层的操作去组装行为。栈和队列这两个东西单独看几乎没什么难度但这一讲的真正练点是“用两个栈实现一个队列”“用两个队列实现一个栈”这种从操作到语义的思维转换。这篇文章我把 Day10 这一讲的思路、四道核心题的解法、容易踩的坑以及栈和队列在工程里的真实应用全部串一遍。不管是跟着训练营走的同学还是准备面试想补一下数据结构基础的人都可以照着这份笔记复现一遍我是按照实际刷题节奏写的尽量把“为什么这么做”也说清楚。1. Day10在训练营里的真实定位这一讲到底要拿下什么1.1 为什么偏偏把栈和队列放在一起讲数组、链表、哈希表这些结构本质都是在讨论“数据怎么存、怎么找”。但栈和队列不一样它们讨论的是“访问顺序”后进先出LIFO还是先进先出FIFO。代码随想录把这两个结构放在一个专题里不是因为它们简单而是因为它们正好是一对可以互相转换的结构。用栈实现队列、用队列实现栈这两道题几乎就是为“数据结构之间可以互相模拟”这个概念设计的。它们逼着你跳出“这个容器有现成方法”的惯性去思考“我到底需要什么行为”。比如队列需要的是“先进先出”那我可以把两个栈分别当作入口和出口用一次倒腾来改变数据顺序。这种思路一旦打开后面做单调栈、单调队列、滑动窗口最大值之类的题目就顺手很多。还有一个很重要的原因栈和队列在工程里的出场率远比你想象的高。函数调用靠栈任务调度靠队列浏览器回退按钮靠栈消息队列、线程池也都是队列思想的延伸。刷这几道题不是应付面试官是在给后续理解系统和框架打底。1.2 这一讲的通关标准我给自己定的标准是三件事。第一能独立手写四个基础操作push、pop、peek/top、empty并且知道在什么情况下要判空、什么情况下永不判空。第二能说清楚“用栈实现队列”里那个灵魂倒腾动作的时机以及为什么 pop 时 out 栈还有元素就不能再次倒入。第三能闭着眼画出括号匹配的整个流程包括三种不匹配情况的处理顺序。很多同学刷完题回头就忘就是因为没抓住这些“关键节点”。栈和队列的题目套路化很明显只要你把标准动作记牢后续任何变种题都是换汤不换药。2. 栈和队列的本质两张图讲透容器适配器2.1 两个生活化类比先建立直觉栈的经典类比是叠盘子。你往桌上放盘子最后放上去的盘子一定是第一个被拿走的。所以栈叫“后进先出”只能从顶部操作。队列的经典类比是排队打饭先来的人先打到饭后来的必须排在队尾所以叫“先进先出”。这两个直觉听起来很简单但刷题时真正容易出错的地方恰恰是栈的“顶部”到底在数组哪一端。用代码随想录里最常用的写法Python 里用 list 模拟栈append 和 pop 操作的就是栈顶C 里 stack 的 push 和 pop 也是从顶部。你只要记住“栈顶永远是最近进入的那个元素”再往下推导就很顺。队列的道理一样Python 里推荐用 collections.deque因为从头部 popleft 和从尾部 append 都是常数时间C 里 queue 默认的底层容器也是 deque。头部是队首尾部是队尾进队从尾部出队从头部。2.2 底层实现为什么默认用deque而不是vector这里有一个值得深挖的细节C STL 的 stack 和 queue 默认底层容器都是 deque而不是 vector。为什么不用 vector因为 vector 在头部插入删除很贵需要搬动所有元素deque 支持双端插入删除而且容量不够扩容时不需要整体搬迁内存它是一段段连续空间拼接的“块状结构”头部尾部进出都很高效。所以 stack 和 queue 在 C 里被叫做“容器适配器”底层是别的容器外层只暴露栈或队列的语义。Python 里也有类似概念collections.deque 就是一个双端队列既可以当栈也可以当队列但如果你只用 list 模拟队列从头部 pop(0) 是 O(n) 的数据量一上来直接卡成慢动作。这个差异面试经常问我建议直接把底层选型这件事吃透。2.3 调用栈与栈帧数据结构在操作系统里活了一次数据结构里的栈在操作系统里有一个货真价实的对应物——调用栈。程序每调用一个函数系统会往调用栈里压入一个“栈帧”里面存着局部变量、返回地址、上一帧的指针等信息函数返回时这一帧被弹出。这个过程和你刷题时 push、pop 操作一模一样只不过栈里的元素变成了函数调用帧。所以递归为什么会爆栈因为递归一层层往下调用函数还没返回栈帧就一直往上堆。如果你递归深度太大栈空间不够用就会出现 Stack Overflow。这也能解释热词里有人问“C语言局部变量越少所占栈空间越小”——是的局部变量存在栈帧里你局部变量越多每个栈帧占的空间就越大同样大小的栈能容纳的递归深度就越浅。“栈帧形成过程”这个热词本质上就是在问这一整套压栈、寻址、返回的过程。2.4 数据结构栈、内存栈、堆三个“堆栈”别搞混继续多说一句很多初学者在这里会被名词绕晕。数据结构里的“栈”是线性表“内存里的栈”是程序运行时保存函数调用信息的一块区域而“堆”更复杂一方面指程序运行时动态分配内存的区域比如 C 语言 malloc、Java 里的对象分配另一方面又是数据结构“优先队列”通常用完全二叉树实现的那个“二叉堆”。这三个概念重名但完全不同数据结构栈是逻辑结构内存栈是内存布局数据结构堆是树形结构内存堆是分配内存的区域。代码随想录讲到栈和队列专题时建议大家顺手把这些名词分清。我之前面试时被连环问过“栈和堆的区别”大多数人能说出“栈快、堆慢、栈自动释放、堆要手动释放”但能把“调用栈里的栈帧”和“算法题里的栈”关联起来的很少如果你能把这一层讲透面试官会高看你一眼。3. 四道核心题完整解析栈与队列互撸到括号匹配3.1 用栈实现队列双栈搬运关键在于“倒空再倒”第一道题是 LeetCode 232 用栈实现队列。题目要求只用栈的 push、pop、peek、empty 这四个基本操作实现一个先进先出的队列。核心思路是准备两个栈一个入队栈 stack_in一个出队栈 stack_out。push 的时候元素直接进 stack_inpop 的时候先把 stack_in 里的元素全部倒进 stack_out这样最早进来的元素就跑到 stack_out 顶部了再从 stack_out 弹出。关键细节来了只有当 stack_out 为空时才能倒数据。如果 stack_out 里还有元素就直接从 stack_out 弹绝不能重复倒腾否则顺序会乱。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 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_out我刷这题的时候一开始 pop 里每次无脑搬运结果队列顺序完全是乱的。后来想明白一个道理栈和队列的差异只体现在“出入顺序”你只要保证出队栈里存的永远是“待出队的元素并且顺序已经翻转过了”问题就迎刃而解。这题还有一个细节peek 用 pop 再塞回去是一个很常见的“偷懒”写法面试时也无所谓但你要能说清楚为什么这样不会破坏顺序。3.2 用队列实现栈单队列转圈就能搞定与之相对的是 LeetCode 225 用队列实现栈。数学上可以用一个队列实现栈方法是每次 push 的时候把新元素先放到队尾然后把前面所有元素依次出队并重新入队这样新元素就跑到队首了正好变成“栈顶”。不过更符合直觉教法的是双队列写法。实际刷的时候有个更轻巧的单队列版本我在代码随想录评论区里见过很多人推荐就是用“转圈”的方式pop 的时候把队列里前 n-1 个元素依次弹出并重新入队队首剩下的最后一个元素就是栈顶直接弹出即可。from collections import deque class MyStack: def __init__(self): self.q deque() def push(self, x: int) - None: self.q.append(x) def pop(self) - int: # 把前 n-1 个元素依次出队再入队最后第 n 个就是栈顶 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) return self.q.popleft() def top(self) - int: # 复用 pop 再塞回去 res self.pop() self.q.append(res) return res def empty(self) - bool: return not self.q这道题的复杂度不太一样push 是 O(1)pop 是 O(n)。这与“用栈实现队列”正好相反那里 push 是 O(1)pop 均摊 O(1)。如果你能在纸上画出这个转圈过程队列实现栈就特别稳。3.3 有效的括号栈天然匹配“最近配对”第三道题是 LeetCode 20 有效的括号。为什么括号匹配要用栈因为你需要匹配的是“最近的左括号”遇到右括号时要找的是最近一个还没匹配的左括号这正好是栈顶。处理方式是遇到左括号就入栈遇到右括号就检查栈顶是否匹配匹配就弹不匹配就返回 False。三种错误情况顺一遍左括号多了最后栈不为空右括号多了遇到右括号时栈已经为空左右括号类型不匹配栈顶和当前右括号对不上。其实这三种情况可以用一段代码统一判断我习惯先建一个右括号到左括号的映射这样代码简洁很多。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这题我第一次写漏了栈空的判断遇到单个右括号直接报了索引错误。括号匹配代码本身短难的是把三种不合法情况都覆盖到。二刷时我还特意拿这题跟“删除相邻重复项”对照因为它们的核心都是“用栈顶记录最近的状态”。3.4 删除相邻重复项这个栈用法很多人会忽略第四道题是 LeetCode 1047 删除字符串中的所有相邻重复项。题目说字符串 abbaca 返回 ca因为 bb 删掉后前面的 a 和后面的 a 又相邻了再删一轮。这里栈的作用是“动态维护最近的未处理字符”遍历每个字符时如果和栈顶相同就弹出栈顶否则入栈。整个过程只扫一遍字符串最后栈里剩下的字符拼接起来就是答案。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)这道题有一个容易被忽略的点删除后产生的新相邻重复会在循环后续步骤里自动处理因为你下一轮处理的字符会继续跟栈顶比较。也就是说栈天然“记住了上一次的结果”所以连锁反应不需要额外递归或回溯。这种思路以后做“消消乐”类的题都能用上。3.5 逆波兰表达式求值用后缀表达式练一次完整流程最后一道题是 LeetCode 150 逆波兰表达式求值也就是后缀表达式。它考察的是表达式已经去掉了括号把运算符放在两个操作数后面比如 “2 1 3 *” 等于 (2 1) * 3 9。求值方式很简单遇到数字入栈遇到运算符就弹出两个数字计算结果压回栈里。因为表达式已经保证合法最后栈顶就是答案。这道题会对很多人有一个考验操作数顺序。比如做减法时先弹出的是右操作数 b后弹出的是左操作数 a计算时要用 a - b而不是 b - a。除法也一样。另一个坑是 Python 的整数除法负数除法要特别小心。def evalRPN(tokens: list[str]) - int: stack [] for t in tokens: if t in (, -, *, /): b stack.pop() a stack.pop() if t : stack.append(a b) elif t -: stack.append(a - b) elif t *: stack.append(a * b) elif t /: stack.append(int(a / b)) # 向零取整 else: stack.append(int(t)) return stack[0]负数除法这个坑我在本地跑测试时发现 Python 的常规除法是向下取整而题目要求向零取整。踩了几次之后我直接写 int(a / b)。这其实是一个很好的经验LeetCode 上的除法语义和很多语言的默认行为不同读题时要注意做题时更要小心类型转换。4. 实操中的性能与边界绕过那些必踩的坑4.1 均摊O(1)和均摊O(n)别被大O忽悠栈实现队列的 pop 操作最坏情况确实是 O(n)——比如刚 push 完 n 个元素后一次性全部 pop第一次 pop 要搬运 n 个元素。但均摊下来每个元素最多被搬进搬出两次所以总体是 O(1)。很多初学者一说“均摊”就发怵我提供一个简单的理解方式你不用盯着某一次 pop 慢不慢而是看整个操作序列的总成本。每个元素从入队栈 pop 出来一次、再压入出队栈一次、之后从出队栈弹出一次总共三次常数时间操作平摊到它参与的 push 和 pop 里肯定算得上 O(1)。队列实现栈则不同每次 pop 都必须把 n-1 个元素全部转圈一遍每一次 pop 都花 O(n)不存在均摊优势。所以如果你面试被问到“哪个方案更好”不要只看功能还要看场景频繁入队、偶尔出队的场景双栈队列就很香频繁入栈、偶尔弹栈的场景双栈队列的反向操作照样可用。4.2 Python与C的容器选型差异用 Python 刷题list 适合当栈用append 和 pop 都很顺手。但如果你想模拟队列别直接用 list.pop(0)那是 O(n)数据量一大容易超时要用 collections.deque 的 popleft。用 C 刷题stack 和 queue 直接用即可但你要知道它们底层默认用的是 deque。有些代码会用 vector 作为 stack 的底层容器因为 vector 尾部操作也很快内存更紧凑。说实话笔试场景用默认的就行但面试被问到“STL 里 stack 的底层是什么”时能答出 deque 是一个加分点。还有一个对比值得注意Java 的 Stack 类已经算“历史遗留”官方更推荐 Deque 的 ArrayDeque 实现因为 Stack 继承自 Vector所有方法都加锁有同步开销。凡是这种语言层面的细节刷题时留意一下面试会很加分。4.3 边界条件自查清单刷完这四道题我总结了一个自查清单每次提交前先过一遍用栈实现队列pop 时是否先判断了 stack_out 是否为空如果为空才搬运。empty 是否同时检查两个栈只查一个会出错。用队列实现栈pop 时转圈次数是 len(q)-1不是 len(q)。top 复用 pop 后是否记得把栈顶元素再塞回去有效括号奇数长度直接返回 False 能否省时间右括号来时如果栈空是否立即返回 False逆波兰表达式求值弹出两个操作数时先弹的是右操作数后弹的是左操作数。负数除法是否按题目要求取整我之前犯过的惨痛教训之一就是“用栈实现队列”里 empty 忘了查两个栈。当时觉得“入队栈空就是队空”结果出队栈里还残留数据逻辑直接炸了。5. 从刷题到工程栈和队列的应用全景5.1 函数调用栈、浏览器回退、undo/redo同一个套路工程里最经典的栈应用是函数调用栈前面提过这里再延伸一句你平时调试代码时看到的调用栈Call Stack就是程序世界里栈的活实例。某个函数调了另一个函数自己还没返回栈帧就一直压着报错时看到的堆栈信息其实就是把这一串帧从上到下打出来。浏览器前进后退按钮也是一个双栈模型。你每访问一个新页面把当前页面压入“后退栈”点后退就是从后退栈弹出页面同时把它压入“前进栈”。点前进再反向操作。这几乎就是“用两个栈实现队列”的亲戚版。文本编辑器的 undo/redo 同样是这个思路。刷过这些题后再看到这些系统会有一种“原来都是老熟人”的感觉。5.2 线程池的阻塞队列生产消费模型怎么落地线程池的核心组件几乎都会有一个阻塞队列用来存放提交到线程池但暂时还没被处理的 Runnable 任务。这个队列选什么类型直接决定线程池的排期策略。常见选择有几种ArrayBlockingQueue 是有界数组队列容量固定可以防止任务无限积压LinkedBlockingQueue 默认无界也可以设置为有界很多线程池的默认选择SynchronousQueue 容量为零生产者和消费者必须直接交接提交任务时如果没有空闲线程直接失败或等待。DelayQueue 则适合延迟任务。本质上刷题时你只是操作一个队列接口但工程化之后你需要考虑有界还是无界、阻塞还是非阻塞、公平还是非公平、延迟还是即到即执行。有一个热词叫“线程池的阻塞队列选择”如果你要答好这个问题我建议把“生产者消费者模型”和“队列为什么天然适合解耦”结合在一起。消息队列的本质其实就是把队列从单机内存搬到分布式系统里。5.3 消息队列把“队列”搬到分布式系统Kafka、RabbitMQ、RocketMQ 这些中间件核心模型就是分布式队列。生产者把消息投递到队列或主题消费者从队列拉取消息。跟刷题时的队列相比它加了很多东西持久化、分区分片、消费组机制、重试与死信、顺序保证。为什么业界要做这么复杂的选型对比因为一旦队列变成了分布式的单机的先进先出就不够了。比如 Kafka 强调高吞吐适合日志和流式场景RabbitMQ 有灵活的路由和延迟队列适合业务消息RocketMQ 在事务消息、延迟消息上有强项适合金融级场景。它们的共性是都保留了队列的“FIFO/解耦/缓冲”这个内核只是在不同约束条件下做了取舍。如果你刷到栈和队列专题顺带了解一点消息队列你会发现数据结构真正的生命力在于“抽象”。题目里那个 deque到了系统设计里就是几十个节点组成的消息管道。5.4 DFS与BFS两种遍历的骨架就是栈和队列再往后看一点图论的深度优先搜索DFS和广度优先搜索BFS一个用栈一个用队列。DFS 要沿着一条路走到底再回来钻下一条天然适合用递归递归就是栈或显式栈模拟BFS 要一层层地往外扩天然适合用队列控制扩展顺序。所以栈和队列不仅仅是“容器”它们直接塑造了遍历策略背后的语言。刷完这几道基础题接下来做二叉树、图论、动态规划优化里的单调队列都还会反复碰到这两兄弟。6. 二刷心法与常见问题速查表6.1 一刷、二刷分别怎么刷别在第一次就死磕一刷的目的是建立熟悉度不需要每道题都一次写对。我给自己定的规矩一道题 30 分钟没有完整思路就直接看题解按照题解的思路自己默写一遍然后做两道相似题巩固。二刷时才要求“独立写出 能讲清复杂度 能处理边界条件”。栈和队列专题是特别适合二刷的专题因为题目少、套路集中。二刷时我会刻意做一件事不看代码只口述思路。比如“用两个栈实现队列只要出队栈为空就把入队栈全部倒过去出队栈不为空就绝对不能倒”。能把关键约束讲清楚比闷头写十遍更有用。6.2 常见问题速查表我把这个专题里常见的毛病整理成了一张速查表刷题遇到 Bug 先在这里找症状可能原因解决方式队列顺序变成反的出队栈里有元素时又倒入了新元素只在出队栈为空时执行搬运动作括号题报索引越界遇到右括号没先判断栈空访问栈顶前必须判断 not stack跳跃删除后结果不对删除相邻重复时用字符串拼接代替栈复杂度高且逻辑乱统一用栈维护“最后一个未处理字符”RPN 除法结果差 1Python 除法默认向下取整题目要求向零取整用 int(a / b) 或手动处理符号deque 用法报错混用了 pop 和 popleft记住左端是队首出队用 popleft右端是队尾判断队空不准双栈队列只检查了入队栈empty 必须同时检查入队栈和出队栈6.3 每天复盘的五分钟模板最后分享一下我每天结束训练营的复盘方法。不用长就五个问题今天做了什么题每道题用了什么结构有没有哪个操作让我卡了十分钟以上卡点是什么如果让我三天后再做一遍我会忘掉的关键点是什么栈和队列专题第一天我的关键点很简单出队栈非空不动、队列转圈 n-1、右括号先判空。这三句话写进笔记里二刷时看到就能快速唤起记忆。我个人操作下来的体会是刷算法最忌讳“刷过就忘”。代码随想录这套训练营的好处是题目编排有递进感但真正的提升还是来自你自己的归纳。今天这四道题其实就是把栈和队列的四个最核心动作练熟压入、弹出、判空、查看栈顶/队首。后续的单调栈、单调队列、滑动窗口最大值全都是在这四个动作之上加一点逻辑。把这四个动作练成条件反射后面会轻松很多。