先说下我自己的感受。算法训练营第九天打卡前三天还在数组、链表、哈希表里摸爬滚打到这一天切入“栈与队列”时很多人以为换了个温柔点的主题结果一看这两道题232 用栈实现队列、225 用队列实现栈直接被绕晕。这两道题题目本身不难但它的难点不在解法复杂而在于“如果你只背了栈是先进后出、队列是先进先出却不知道它们底层操作是怎么发生的你根本不知道这题在干嘛”。今天这篇就专门把这两道题拆开从“为什么要用两个栈”“为什么要旋转队列”这种最底层的问题讲起保证你刷完这一篇再回去看题目会顺手很多。先说清楚一件事这道题值得认真做不只是因为它是 LeetCode 经典题而是因为“用 A 实现 B”本质上是在训练你对结构操作的理解力。后面你会遇到单调栈、滑动窗口、BFS 里的队列应用很多题都是从这里长出来的。所以不是背答案而是要把“操作关系”吃透。1. 整体设计与思路拆解1.1 栈和队列的本质差异一进一出的操作约束在真正动手写代码之前我强烈建议大家先在脑子里把栈和队列的区别理一遍。栈是后进先出LIFO队列是先进先出FIFO。这句话谁都会背但很多人没有真正理解“为什么会这样”。往底层看栈的插入和删除操作都只允许在同一个端点栈顶进行队列的插入在队尾、删除在队首两个端点分别被占用。这个差别听起来很小但在实际编码里会导致完全不同的行为。我习惯用一个生活化类比来说明栈就像一摞盘子你要拿盘子只能从最上面拿新盘子也只能放在最上面队列就像食堂排队后来的人必须排在队尾先来的先打到饭先走。回到代码层面你用数组实现栈只需要一个指针top从尾部操作append 和 pop 都是 O(1)。用数组实现队列则麻烦一点如果直接用数组尾部插入、头部弹出那么头部弹出一个元素后整个数组要往前移动时间开销就变成 O(n)。这也是为什么我们做栈和队列互相模拟的时候需要考虑的不仅仅是“能不能实现”还要考虑“每次操作是不是足够高效”。训练营第九天的题核心考点就是你能不能在这个“操作端点”的层面上来回切换而不是死记“用两个栈”或者“用一个队列”这种结论。1.2 为什么“用栈实现队列”需要两个栈而“用队列实现栈”用一个队列就能搞定这个问题值得现在就摆出来因为它直接决定这两道题的做法方向。先说 232栈是 LIFO队列是 FIFO。如果你只有一个栈你往栈里推入 1、2、3弹出来是 3、2、1这和队列想要的 1、2、3 正好相反。一个栈变不出反转效果那怎么办再加一个栈把第一个栈里的元素“倒出来”再弹顺序就被反转了两次负负得正变成先进先出。再说 225队列是 FIFO你要实现的是 LIFO。一个队列能不能做到初看起来不行因为队列天生就是先进先出你按 1、2、3 的顺序入队弹出的顺序肯定是 1、2、3而栈要的是 3、2、1。但这里有个关键操作队列允许你在队尾入队、队首出队。如果我每次 push 一个新元素后把队列里之前的所有元素从队首依次弹出再重新加入队尾那么新元素就被“挤”到了队首下次弹出时就会先弹它。这相当于利用了队列“尾部插入、头部删除”的特性做了一次旋转新元素插队成功。所以这道题的核心不是“一个容器能不能装下数据”而是“你是否能利用容器允许的操作特性去改变元素被读出的顺序”。理解了这一点代码只是顺水推舟的事情。1.3 两道题的常规选型与复杂度目标做题之前还得明确一个目标题目要求的时间复杂度是什么级别LeetCode 232 的要求是 push、pop、peek、empty 这四个操作均摊下来时间复杂度是 O(1)225 也是类似push 可以是 O(n)但 pop、top、empty 一般是 O(1)。这意味着你写出来的解法不能是每次取队首元素时都把整个元素组复制一遍。我们需要考虑“摊还分析”这个概念。用两个栈实现队列push 是 O(1)pop 在大多数时候是 O(1)只有在 outStack 为空、需要倒灌的时候才出现一次 O(n) 的操作因为每个元素只会被倒灌一次所以均摊下来还是 O(1)。用队列实现栈如果用单队列旋转法push 变成 O(n)pop 是 O(1)如果用双队列切换法pop 变成 O(n)。这两种都是允许的因为题目通常只约束整体操作的平均复杂度没有硬性限制某一次操作必须 O(1)。到这一步整体设计思路基本清晰了232两个栈 倒灌时机控制225单队列旋转法或双队列切换法2. 232 题拆解用栈实现队列的核心细节2.1 核心思路一个负责进一个负责出倒灌的时机是重点232 的常规解法是用两个栈一个输入栈inStack一个输出栈outStack。push 的元素一律进 inStackpop 或 peek 的时候从 outStack 取。但 outStack 里的元素来自哪里来自 inStack 的倒灌。什么时候倒灌只有 outStack 为空的时候才倒灌。这个时机必须想清楚否则就会出错。我举个例子说明为什么要这么设计。假设 inStack 依次推入 1、2、3此时 inStack 从栈底到栈顶是 [1, 2, 3]。如果我现在想 pop队列应该先弹出 1。怎么做把 inStack 里的元素一个一个弹出再压入 outStackoutStack 就变成 [3, 2, 1]栈顶是 1pop 一下1 就出来了正好是队列想要的顺序。那为什么不能每次 pop 都重新倒灌一遍因为倒灌本质上是一次“反转操作”如果你反复倒灌顺序会反复反转数据就乱了。比如你已经倒灌了一次outStack 是 [3, 2, 1]此时你 pop 掉了 1outStack 剩下 [3, 2]栈顶是 2。如果你又倒灌一遍2 会被压回 inStack再马上倒出来折腾一圈还是 2走了冤枉路。所以倒灌的正确时机是只有当 outStack 为空时才把 inStack 的所有元素一次性倒过来。否则一直从 outStack 出。这保证了每个元素从 inStack 转入 outStack 的次数最多一次摊还复杂度才是 O(1)。2.2 代码实现与每个操作的设计理由先给一份可运行的 Python 代码然后我再逐行解释为什么这么写。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: # 复用pop逻辑但要把弹出的元素放回去 res self.pop() self.out_stack.append(res) return res def empty(self) - bool: return not self.in_stack and not self.out_stackpush 非常简单直接 append 到 in_stack 尾部因为尾部就是栈顶。pop 是核心。当 out_stack 非空时说明已经有之前倒灌好的元素直接 pop 栈顶即可这个顺序就是队首的顺序。当 out_stack 为空时必须先把 in_stack 里的元素全部弹出并压入 out_stack完成一次反转然后再 pop。peek 的实现值得特别注意。它的目的只是看一眼队首元素是什么不把它移出队列。最容易想到的方法是如果 out_stack 非空直接返回 out_stack[-1]如果 out_stack 为空先倒灌再返回 out_stack[-1]。但这样写会有重复代码。我更喜欢复用 pop 再压回去先 pop 一次拿到队首元素再把它 append 回 out_stack。这里有个细节pop 之后 out_stack 已经空了如果队列只有一个元素再 append 回去依然在正确位置。这是一个很常用的“复用”技巧能少写很多重复判断。但要注意如果你用的是 C 或 Java 的 Deque 接口取队首元素是 peekFirst()不会修改结构直接调用即可不需要这个“弹出去再放回来”的操作。empty 的判断一定要同时检查两个栈。很多人只检查输出栈结果队列里其实还有元素但输出了错判为“空”。因为 in_stack 里的元素还没被倒灌到 out_stack它们也是队列的一部分。2.3 边界情况与踩坑点做这道题最恶心的地方在于LeetCode 的测试用例会非常刁钻。我帮大家把边界情况列一列空队列调用 pop题目保证不会这样但如果你自己实现最好抛异常或返回特定值。out_stack 为空时调用 peek必须先倒灌否则 out_stack[-1] 直接越界报错。连续 push、再连续 pop、再 push、再 pop这要求倒灌只能发生在 out_stack 为空时如果 out_stack 不为空还强制倒灌顺序就会出错。我自己在第一次写这道题时犯过一个特别蠢的错误pop 的时候直接把 in_stack 里的元素弹出来了完全没管 out_stack。逻辑是这样的我心想 in_stack 的元素是最新加入的队列要弹出的是最早加入的但 in_stack 是 LIFO直接弹出得到的是最新加入的这一下就把题意搞反了。所以大家写之前一定要先在纸上模拟几个数字别直接上代码。3. 225 题拆解用队列实现栈的核心细节3.1 思路核心每次 push 后把旧元素挪到新元素后面225 题和 232 题不一样的地方在于它不需要两个独立容器完成“一次反转”而是需要一个“旋转”操作来改变新元素的相对位置。单队列的思路是这样的队列的特性是队首出、队尾进。如果我每次 push 一个新元素然后把队列前面原有的元素依次出队再重新加入队尾那新元素就会出现在队首栈顶效果就出来了。我举个例子。假设队列当前是 [1, 2]队首是 1。现在 push(3)3 入队队列变成 [1, 2, 3]。把队列中除了新元素 3 以外的元素按顺序弹出一个加入队尾先弹出 1队列变成 [2, 3]再把 1 放到队尾变成 [2, 3, 1]。继续弹出 2队列变成 [3, 1]再把 2 放到队尾变成 [3, 1, 2]。到此队列是 [3, 1, 2]队首是 3正好是最后加入的元素pop 或者 top 的时候直接看队首就行。这里的核心操作次数是每次 push 都要移动队列里已有的 n-1 个旧元素到队尾所以 push 的时间复杂度为 O(n)但 pop/top/empty 都是 O(1)。3.2 单队列版本的代码实现用 Python 的 collections.deque 来写因为它同时支持队首弹出和队尾追加并且 popleft 是 O(1) 的效率比列表的 pop(0) 高得多。from collections import deque class MyStack: def __init__(self): self.queue deque() def push(self, x: int) - None: self.queue.append(x) # 把前面 n-1 个元素重新放到队尾让新元素到队首 size len(self.queue) for _ in range(size - 1): self.queue.append(self.queue.popleft()) def pop(self) - int: return self.queue.popleft() def top(self) - int: return self.queue[0] def empty(self) - bool: return not self.queuepush 中的循环是这道题的关键。加入新元素后队列长度是 size队首是旧元素。循环 size - 1 次每次把队首元素弹出并接到尾部经过这轮操作新元素就变成了队首。如果把 push 的循环次数记成 size那新元素也会被弹到队尾再回来虽然最后队首还是新元素但多走了一次无用功而且如果只有这一个元素时还会平白多一次操作。所以在写循环条件时留意只需要移动原先就在队列里的元素次数是 size - 1。pop 直接 popleft因为队首就是最后加入的元素符合栈后进先出的规则。top 直接读取队首值queue[0] 即可不需要弹出再放回。empty 判断队列是否为空即可。3.3 双队列版本另一种实现方式对比除了单队列旋转法训练营里很多人还见到过双队列解法。思路是用两个队列 q1 和 q2始终保持其中一个队列为空另一个队列存数据。push 操作把新元素放入非空的队列。pop 操作把非空队列的前 n-1 个元素依次转移到空队列剩下最后一个元素直接弹出。代码大概长这样from collections import deque class MyStack: def __init__(self): self.q1 deque() self.q2 deque() def push(self, x: int) - None: self.q1.append(x) def pop(self) - int: # 把 q1 中前 n-1 个元素移到 q2 while len(self.q1) 1: self.q2.append(self.q1.popleft()) # 交换 q1 和 q2保证 q1 始终是数据队列 self.q1, self.q2 self.q2, self.q1 return self.q2.popleft() def top(self) - int: res self.pop() self.q1.append(res) return res def empty(self) - bool: return not self.q1 and not self.q2对比下来单队列旋转法的 push 是 O(n)双队列法的 pop 和 top 是 O(n)。二者整体均摊复杂度差不多但单队列版代码更短双队列版的思路更直观。我更推荐训练营的同学把单队列版写熟因为它在 push 时完成旋转后续读操作非常顺滑不容易在 top 和 pop 之间出现状态混乱。3.4 一个小问题225 的 top 怎么实现才不破坏栈结构top 和 pop 的区别在于top 只是看一眼栈顶不能把元素移除。双队列法里常见错误是直接 top 的时候也把最后一个元素弹出来然后忘记放回去。更稳的做法是复用 pop在拿到 res 之后再把它 push 回栈里。但要注意你复用的 pop 会把栈里的元素重新调整一下此时你 push 回去的是最后一个元素它会被当作新元素旋转到队首所以最终栈内顺序不会被破坏。这个技巧和 232 题里 peek 复用 pop 是一个道理也是训练营里反复强调的“代码复用”思路。4. 两题对比、常见问题与排查技巧4.1 一道“对称题”为什么做法完全不同这两道题放在同一天训练营的用意很明显让你对比理解两种结构在操作上的不对称性。用栈实现队列需要两个容器因为一个栈只能改变一次顺序而栈的内部顺序和队列要求完全相反必须反转两次。用队列实现栈只需要一个队列就能实现旋转因为队列的元素进出顺序本来就符合“循环”的特征利用旋转可以任意改变队首元素。关键在于栈只能从顶部操作所以把一串元素从栈中弹出再压入另一个栈顺序会反转而队列可以从队首弹出、从队尾插入所以把一路元素整个转一圈顺序并不会反转只是位置发生偏移。我把两题的匹配方案整理成表方便复习时一眼看清题目目标顺序使用容器核心操作操作次数较高的方法232 用栈实现队列FIFO两个栈输出栈为空时倒灌pop/peek 偶尔 O(n)225 用队列实现栈单队列LIFO一个队列push 后旋转旧元素push 每次 O(n)225 用队列实现栈双队列LIFO两个队列pop 前转移前 n-1 个pop/top 每次 O(n)从表格就能看出一个有趣的点当目标顺序与容器特性相反时要么多一个容器232要么对入容器顺序做点手脚225 的 push 旋转。这些套路在后续的算法题里会反复出现比如滑动窗口用队列维护候选值、表达式求值用栈处理运算符优先级本质上都是在利用这两种结构的操作特性。4.2 写代码时最常见的四个坑第一个坑忘记一次性转移所有元素。232 的倒灌必须用 while 循环把所有 in_stack 元素全部倒到 out_stack而不是只倒一个。如果只倒一个pop 到的不是队首而是元素集合里相对靠后的那个。第二个坑pop 和 peek 搞混。pop 返回并移除队首/栈顶peek/top 只返回不移除。很多人为了图省事在 peek/top 里直接调用 pop却忘了把弹出的元素放回去导致一次 peek 就改变数据结构后续测试用例全挂。第三个坑225 单队列 push 时循环次数写错。如果你循环 len(queue) 次而不是 len(queue)-1 次新元素虽然也能到队首但多了一次无意义的转移更重要的是当队列只有一个元素时会把唯一元素弹到队尾再弹回来虽然结果看起来没变但代码逻辑不够严谨。第四个坑判断空时只检查一个容器。232 的 empty 必须同时检查 inStack 和 outStack。因为 inStack 里可能有元素还没有倒灌到 outStack此时队列并非空。225 如果用双队列也要同时检查两个队列。4.3 排查思路从“看代码”到“画状态”我在训练营里带打卡的时候发现很多同学出问题后喜欢反复盯着代码看却看不出个所以然。更高效的方式是把每一轮操作后的两个容器状态画出来。比如 232可以从空队列开始依次做 push(1)、push(2)、pop()、push(3)、peek()、pop()每一步都记录下来 inStack 和 outStack 里具体是哪些元素。如果你画出来的状态和代码预期不一致问题出在哪一步就很清楚了。225 同理单队列旋转法每次 push 后队列中每个元素的位置都会变化。画状态时重点看新元素是不是在队首以及旧元素的相对顺序是否保持不变。我个人的排查顺序是先跑请假用例再跑边界用例只 push 一个元素就 pop、连续 pop 到空、pop 完之后再 push最后再随机生成一批操作序列与 Python 自带的 queue.Queue 或 list 模拟的行为做对照。这三个层次的测试基本能覆盖所有写挂的情况。4.4 一个训练营之外的补充经验手写模拟题更适合用 Deque 而不是 List如果你写的是 Python很多人会直接用 list 模拟队列比如 list.pop(0)。这个操作在最坏情况下是 O(n) 的因为列表头部弹出后后面的所有元素都要前移。LeetCode 这种平台本来就能过但如果你在主程序中频繁调用性能下降很严重。建议用 collections.deque 来模拟队列它支持 popleft() 和 append()两端的操作都是 O(1)。同样用栈实现队列时Python 的 list 本身就可以当栈用append 和 pop 都是 O(1)直接用 list 没问题。但如果题目改成用队列实现其他结构尤其是大量操作的场景一定记得优先考虑 deque。5. 实操过程从题面到 AC 的完整思考示范5.1 以 232 为例走一遍完整思考流程题面拿到手先不急着写代码在草稿纸上列出四件事需要实现哪些方法、输入输出的类型、操作的约束、复杂度目标。232 需要 push、pop、peek、empty 四个方法全是 int 或 bool 类型。第二步问自己“栈和队列操作特性差异是什么”。理清后想到用一个栈做反转再用另一个栈还原于是形成 inStack 和 outStack 的雏形。第三步确定倒灌时机。这里可以模拟一个小例子push(1)、push(2)然后 pop()观察两个栈的状态。如果没倒灌pop 会拿到 2不对倒灌一次拿到 1正确。第四步把 peek 也纳入设计。peek 不能破坏队列所以要么直接看 outStack[-1]要么复用 pop 再放回。第五步处理 empty 判断。这是最容易漏的因为两个栈都可能存有元素。第六步翻译成代码。写完后再把第一步的用例跑一遍确认状态一致。5.2 以 225 为例对比两种写法的调试感受225 我建议至少把单队列法和双队列法各写一遍。单队列法第一次写的时候很多人会卡在“为什么要循环 size-1 次而不是 size 次”上。我的建议是直接在 push 里加入 print打印出每一轮旋转前后队列的内容。比如 push(1)、push(2)、push(3)你会在 push(3) 时看到队列从 [1, 2, 3] 变成 [3, 1, 2] 的完整过程。看到这个过程比读十遍讲解都管用。双队列法调试时重点看 pop 之后 q1 和 q2 是否交换。如果忘记交换下一次 push 就会把新元素放到旧的 q1 中而真正存数据的 q2 反而被忽略了数据就错乱。两种写法我都建议用 LeetCode 的题目内置测试跑一遍然后再构造一个操作序列push(1), push(2), top(), pop(), empty()。这是最基础的冒烟测试能快速暴露大多数问题。5.3 从训练营角度看的“过题标准”很多同学误以为 AC 了就万事大吉。但在训练营里我会把一道题分三个层次AC、能讲清楚、能改写成多种语言或多种写法。232 和 225 这两道题AC 只是第一层。第二层是你能不能用口述的方式把“倒灌时机”“旋转次数”讲给同桌听。第三层是你能不能在五分钟内用另一种写法实现出来比如 225 用双队列、232 用 C 的 stack 容器。如果你能到第三层后面的单调队列、单调栈、表达式求值这些内容你会学得很快。因为这些题的本质并不是数据结构本身而是“如何利用结构的特性去控制数据的顺序”。6. 后续扩展与个人经验这两道题刷完之后紧接着的训练营内容大概率是有效的括号、删除字符串中的所有相邻重复项、逆波兰表达式求值等栈的经典应用。你会发现那些题其实大量借用了“栈顶状态”的概念而 232 和 225 给你打下的基础就是让你在脑子里能清楚地呈现“容器里数据的实时状态”。这个能力太重要了后面很多题不是算法有多难而是你把状态画出来之后思路自己就出来了。我个人在刷这部分时的做法是把每一道栈和队列题的容器状态都画在一个本子上推演完再写代码。这个习惯一直保留到现在遇到复杂的题哪怕不写代码也会先在纸上把操作过程过一遍。你可能觉得多此一举但真到面试手写代码的时候这个习惯会救你很多次。最后分享一个实操小技巧不管是 232 还是 225写完之后立刻把类方法全部注释掉只留一个操作序列然后重新实现一遍。如果能不看原来的代码靠理解把全类补全才算真正掌握了。这种“背题不如默写理解”的方法放到任何算法知识点上都好使。
