代码随想录算法训练营刷到 Day10主题是栈与队列。很多刷题的人会觉得栈和队列属于“我早就懂了”的数据结构——一个先进后出、一个先进先出概念一两句话就能讲完。但真到了笔试现场被“用栈实现队列”“用队列实现栈”这种题卡住的人可不少。Day10 之所以把这两个结构放在同一天核心就是想让大家先想清楚一件事这两种容器为什么存在它们的本质区别到底是什么这篇文章不打算逐题复述题解而是把这一天的核心认知线拎出来——底层容器的差异、双栈双队列模拟时的顺序翻转逻辑、括号匹配和相邻消除背后的统一套路以及逆波兰表达式求值为什么天然就是栈的舞台。适合正在跟训练营刷 LeetCode、准备算法面试的读者也适合那些“会用 API 但说不清原理”的人。你会发现一个很有意思的规律理解了栈和队列的“方向感”这一天的五道题至少有四道可以凭直觉推出来。1. 栈与队列同为线性表方向感却完全相反1.1 栈后进先出计算机里无处不在的“撤销键”栈的操作被限制在栈顶只有 push、pop、peek 三个核心动作没有“从中间访问”的接口。这看起来是一种限制却对应了现实生活中一大批“撤销”“回退”场景。放一摞盘子的比喻最直观后放上去的盘子最先被拿下来。编辑器的撤销操作就是这个模型——你刚输入的字符压入栈顶撤销时先撤销最近的一次操作。浏览器的后退按钮同样如此你访问页面 A、页面 B、页面 C后退时先回到 B再回到 A顺序完全由 LIFO 控制。函数调用栈更是典型main 调用 functionAfunctionA 再调用 functionB返回时 functionB 先结束然后把结果交还给 functionA最后回到 main这跟压栈弹栈的顺序严丝合缝。所以栈不是“一种数据结构”这么简单它是对“最近发生的事最优先处理”这一逻辑的抽象。1.2 队列先进先出系统里的调度秩序队列锁死的是 FIFO先到的人先被服务。操作集合也变成入队、出队、取队头。队列天然建模的是“排队等待”的资源分配场景CPU 的任务调度、网络数据包的处理顺序、打印机任务队列、超市收银台全是这种秩序。广度优先搜索BFS也一定要用队列因为 BFS 按层推进先进入某一层的节点必然先被访问这个访问顺序恰好由队列维护。如果非要用一句话概括两者的区别我会说栈关心“最近”队列关心“最早”。这决定了它们在不同题目里的适用范围。1.3 从底层实现看数组和链表分别怎么搭这两种结构理解容器库之前先想一遍底层否则后面写模拟题时会总觉得摸不到本质。数组模拟栈很简单维护一个 top 指针push 时 toppop 时 top--容量足够的情况下都是 O(1)。数组模拟队列就比较麻烦直接复用下标 0 的位置pop 会让队头下标前移时间长了下标 0 之前的空间就浪费了所以普通数组实现队列往往配合“循环队列”来复用空间。链表模拟栈只需要在头部插入删除节点链表模拟队列则维护 head 和 tail 两个指针尾节点入队、头节点出队两者都是 O(1)。训练营把栈和队列放在同一天还有一个隐藏用意它们底层都可以由数组或链表实现区别只在于操作约束不同。既然底层这么接近那“用栈实现队列”“用队列实现栈”这种互转题就有了解题的可能——不是凭空变魔术而是把一种约束转换成另一种。2. 不同语言容器库的差异API 表面一样底层脾气不一样2.1 C 的 stack 和 queue 是容器适配器C STL 里stack 和 queue 默认的底层容器都是 deque因此它们被称作“容器适配器”——本身不管理内存只是在一层容器之上重新定义接口。deque 是双端队列两端操作都是 O(1)所以既能支撑 stack 的 push/pop也能支撑 queue 的 push/pop/front/back。很多初学者下意识以为 stack 是“基于数组的”严格说默认不是 vector 而是 deque。stack 展开来看其实是 std::stackint, std::deque 。如果你愿意也可以手动指定底层为std::stackint, std::vectorint在只需要尾部增删时它的缓存表现可能会更好不过实际工程里很少有人这么做。记住这个点面试时提起“容器适配器”三个字会比单纯背 API 显得扎实很多。2.2 Python 的 list 能当栈但千万别当队列Python 里没有专门的 Stack 类最自然的用法就是 list。append 和 pop() 都是尾部 O(1)当栈绝对够用。但如果你用list.pop(0)模拟队列出队那就是灾难pop(0) 要把后面所有元素整体前移时间复杂度 O(n)数据量大一点立刻超时。正确的姿势是使用collections.deque。deque 的 append 和 popleft 都是 O(1)它内部是块状链表结构两端操作性能稳定。刷题时用 deque 模拟普通队列、模拟栈都没有问题。还有一个细节from collections import deque之后deque 本身也是一个序列容器可以直接遍历、按下标访问灵活性比 list 高不少。2.3 Java 的 Stack 类值得用吗Java 早年的 Stack 类继承自 Vector方法级同步线程安全。但在单线程算法题里这种同步反而成了不必要的性能负担。更关键的是Stack 为了兼容老设计包含了继承来的add(int, E)、get(int)等一堆不属于栈语义的方法容易误导调用者。现代刷题和工程都更推荐用 ArrayDeque 作为栈和队列的统一容器。ArrayDeque 当栈用push/pop当队列用offer/poll底层是循环数组不需要扩容时的元素搬移也处理得很高效。唯一要注意的是 ArrayDeque 不允许 null 元素这一点比 LinkedList 严格实践中别往里面塞 null。语言栈推荐队列推荐注意事项Cstd::stackstd::queue默认底层 deque可指定 vectorPythonlist 或 dequecollections.dequelist.pop(0) 是 O(n)JavaArrayDequeArrayDeque / LinkedListArrayDeque 禁止 null3. 用栈实现队列双栈的顺序翻转是关键3.1 为什么一个栈不行栈的出口在栈顶队列的出口在队底。你需要返回的永远是“最先进入”的元素但栈顶永远是“最后进入”的元素。单栈的 pop 根本没有办法找到队首元素除非每次 pop 都把整个栈倒腾一遍——那就不是实现队列而是在做排序了。双栈的思路是让一个栈负责入口另一个栈负责出口。入口栈维持入队顺序出口栈把顺序翻转回来。3.2 inStack 和 outStack 的分工逻辑实现时维护两个栈inStack 负责 pushoutStack 负责 pop。push 时直接压入 inStack。pop 时先看 outStack 是否为空如果为空就把 inStack 的元素全部弹出再按弹出顺序压进 outStack最后从 outStack 弹出栈顶。来看一个例子inStack 依次压入 1、2、3从栈顶到栈底是 [3, 2, 1]。把 inStack 全部弹出弹出顺序是 3、2、1依次压入 outStack 后outStack 从栈顶到栈底变成 [1, 2, 3]。也就是说 outStack 的栈顶就是 1恰好是队列头出栈顺序 1、2、3 就是 FIFO。这里有个非常容易踩的坑inStack 倒入 outStack 的时机。必须等 outStack 完全为空时才倒入而且必须整批倒完。如果 outStack 还残留着元素说明栈顶已经是最早进入队列的元素此时倒入新的元素会把新元素压在老元素下面破坏顺序。形象地说入口缓冲区里的货物只有在出口缓冲区彻底清空时才能搬一次而且要一次性全部搬完。3.3 peek 的优化与复杂度分析peek 和 pop 的逻辑几乎一样只是 peek 只读取 outStack 栈顶而不出栈。empty 需要同时检查 inStack 和 outStack 是否都为空。复杂度上每个元素最多经历“压入 inStack 一次、倒入 outStack 一次、从 outStack 弹出一次”所以均摊到每次操作都是 O(1)。面试时谈到这个题顺手补一句“amortized O(1)”非常加分——它体现的是摊还分析意识而不是只记住了答案。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x: int) - None: self.in_stack.append(x) def pop(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self) - int: if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def empty(self) - bool: return not self.in_stack and not self.out_stack4. 用队列实现栈两种模拟策略第二种更漂亮4.1 双队列法新元素先去备用队列完成“插队”LeetCode 225 这道题要求只用队列实现栈。先讲双队列的思路。维护 q1 作为“当前栈”q2 作为搬运队列。push(x) 时先把 x 放进空的 q2然后把 q1 中的所有元素依次出队并入队到 q2。此时 q2 的队头是 x也就是最后入栈的元素它恰恰应该成为“栈顶”。交换 q1 和 q2 的引用让 q1 持有整理后的序列。pop 时直接从 q1 队头出队即可。push 的时间复杂度是 O(n)pop、top、empty 是 O(1)。因为每次 push 都要搬运之前的所有元素让新元素跑到队头去“插队”。4.2 单队列优化入队之后旋转双队列其实还有改进空间。既然 q2 只是个中转站那干脆不用第二个队列push(x) 时先把 x 入队然后循环把队列前 size-1 个元素依次取出再重新入队。这样 x 就被旋转到了队头。举个例子当前队列 q [3, 2, 1]队头 3 就是栈顶。push(4) 后q 变成 [3, 2, 1, 4]。把前三个元素依次取出并放回队尾取出 3 放回q [2, 1, 4, 3]取出 2 放回q [1, 4, 3, 2]取出 1 放回q [4, 3, 2, 1]。此时队头 4正好对应最后一个入栈的元素。pop 时直接取队头。单队列版本的代码量只有双队列的一半但逻辑上需要想清楚“旋转”这个动作的意义。面试时如果先写了双队列面试官追问能不能优化再改成单队列旋转会让整段对话非常顺畅。4.3 两种策略的对比用双队列与单队列实现栈本质上都在做同一件事把最后入队的元素从队尾搬到队头。一个是借一个临时队列完成搬运一个是直接在原队列里转圈。我发现很多人在训练营打卡时只写一种解法就过了但我个人强烈建议把两种都写一遍。因为“栈实现队列”和“队列实现栈”放在同一天学真正想考察的就是你能否在两种受限操作之间自由切换。把顺序倒过来是一种能力把顺序转起来是另一种能力两种都亲手写过才算真的吸收了这一天的核心。5. 括号匹配与相邻消除栈顶就是“当前状态”5.1 有效括号三种括号为什么必须用栈有效括号这道题核心套路是遇到左括号压栈遇到右括号检查栈顶是否匹配匹配则弹出否则直接判定无效。为什么不是用一个计数器来统计左右括号数量单种括号确实可以但题目给了三种括号而且括号不能交叉。([)]这种字符串如果我们只计数左括号和右括号总数相等却完全无效。正确的逻辑是栈顶永远保存“最近一个未闭合的左括号”遇到右括号时必须和这个最近未闭合的左括号配对。如果类型不匹配说明括号交叉了立刻返回 false。一个非常实用的小优化字符串长度是奇数时直接返回 false。虽然这是一个 O(1) 的提前判断但能省去后续大量无效入栈操作。笔试里这种细节不会让你超时但会让代码看起来更干净。5.2 删除相邻重复项栈帮你做好“连锁反应”题目要求把字符串中相邻重复的字符删除删完之后新产生的相邻重复项还要继续删直到不能删为止。这就是一个“字符串消消乐”问题。用栈来处理再自然不过遍历字符如果当前字符和栈顶相同说明这是一对相邻重复项弹出栈顶否则把当前字符压栈。遍历结束后栈里剩下的就是从栈底到栈顶拼接出的最终字符串。为什么这个做法天然处理了连锁反应因为当一个字符和栈顶字符消除后栈顶自动回退到更早的字符。下一个读取的新字符会直接和这个更早的字符比较正好模拟了消除后左右两侧变成新邻居的效果。如果没有栈你每次消除后都得从头扫描字符串尤其麻烦。5.3 统一视角什么时候该想到栈把括号匹配和相邻消除放在同一天学是想训练同一种直觉“最近的信息优先处理”。判断一道题是否该用栈可以问自己一个问题当我读完下一个元素是否需要依赖最近一次保存的信息来决定要不要做操作如果需要栈就是最自然的工具。括号匹配依赖最近未闭合的左括号相邻消除依赖最近保留的字符逆波兰表达式求值依赖最近的两个数字——这些全都可以用“最近信息优先”四个字概括。掌握了这个判断方式哪怕面试遇到没见过的新题也能很快把方向定到栈上。6. 逆波兰表达式求值为什么后缀表达式更适合机器6.1 中缀让人读后缀让机器读人写的数学表达式通常是中缀比如3 4 * 5需要按运算符优先级先乘后加有时还需要括号改变优先级。计算机如果直接处理中缀就得解析运算符优先级、括号嵌套、左右结合性编译器需要做的工作相当多。逆波兰表达式也叫后缀表达式把运算符写在操作数之后3 4 5 * 。这个式子从左到右读遇到数字就压栈遇到运算符就弹出两个数做运算结果再压回栈。全程不需要管优先级也不需要括号非常适合机器顺序执行。6.2 求值实现里的细节坑遍历 tokens 时遇到数字压栈遇到运算符弹出两个操作数计算结果再压栈。这里最容易翻车的是弹出顺序。栈顶弹出的是右操作数第二个弹出的是左操作数。比如3 4 -遇到减号时先弹出 4 作为右操作数再弹出 3 作为左操作数结果是3 - 4 -1。如果写反就会得出4 - 3 1答案完全不一样。减法、除法、取模这些不满足交换律的运算尤其要注意操作数顺序。另一个隐蔽的坑是除法取整方向。C 的整数除法默认向零截断而 Python 的//是向下取整对于负数运算两者结果会不同。跨语言刷逆波兰表达式时如果不能保证操作数都是正数一定要显式处理向零取整否则本地跑得好好的代码换一个平台提交就答案错误。6.3 栈在这里扮演的角色逆波兰表达式求值是“后进先出”最直接的价值证明。编译器运行时表达式并不是一次性计算完毕而是靠一个栈记住中间结果遇到数字压栈遇到运算符把最近的两个数字取出来算完再放回去。数字之间谁先谁后完全由入栈顺序决定——中间结果必须暂存在某个地方而栈恰好是这种“最近结果优先”的天然容器。这也解释了为什么训练营要把逆波兰表达式放在栈与队列这一天。它不只是简单的求值题更是一把理解“栈为什么被设计出来”的钥匙。7. 工程场景里如何选择到底用栈还是队列7.1 系统底层的栈函数调用栈就是最典型的栈应用。递归函数如果不控制深度很快会把调用栈耗尽这种“栈溢出”的说法本身就来自栈结构。浏览器的前进后退工程上可以抽象为一个主栈和一个前进栈每次访问新页面压入主栈后退时把当前页弹出并压入前进栈前进时再反向操作。编辑器撤销重做也是同一套模型。凡是“最近的操作最先被回滚”的需求栈都是第一选择。7.2 系统底层的队列队列负责的是公平和缓冲。任务调度先到先服务消息队列削峰填谷网络数据包按顺序处理打印机任务排队等待——这些场景关心的不是“最近”而是“最早”。广度优先搜索用队列也是这个道理先访问上一层节点再按入队顺序访问下一层节点队列保证了层与层之间的顺序不乱。7.3 做设计决策时的一套判断清单我做个简单的总结方便面试时快速判断如果题目出现“撤销、回退、最近匹配、嵌套、括号、最近一次”这些词优先考虑栈。如果题目出现“排队、先到先服务、按层遍历、任务调度、缓冲、公平”这些词优先考虑队列。如果数据需要两端高效访问直接用双端队列。如果只是临时容器栈和队列都能过选择更短代码的那个。拿这个清单回去对照 Day10 的五道题你会发现每一道都能对号入座。栈与队列看起来简单但正因为简单它们才成为面试中最爱用来考察“是否真的理解了数据结构约束”的工具。最后再分享一个实操体会这一天的训练营内容不建议只把五道题的代码各过一遍就收工。把“用栈实现队列”的代码改成手动模拟几个用例把“用队列实现栈”的旋转步骤在纸上画一遍比凭空背十道题都有用。当你不需要任何提示就能解释“为什么这里的弹出顺序是右操作数先出栈”这一天才算真正吃透了。