)
栈LIFO和队列FIFO是数据结构里的一对“冤家”——一个后进先出一个先进先出。但面试官偏要问“能不能用栈实现队列”这就是LC.232这道经典设计题的由来。它不考复杂算法考的是你对两种数据结构本质差异的理解栈底元素要想先出去就得先把上面的都搬走。今天我们就用两个栈 一次“倒水”把LIFO硬生生变成FIFO而且每个操作均摊O(1)。更妙的是理解了“倒水”思想反过来“用队列实现栈”也顺理成章。 题目速览30 秒读懂用两个栈实现一个队列支持push、pop、peek、empty四个操作。示例push(1) → push(2) → peek() → pop() → empty() 输出1, 1, false约束操作次数 ≤ 100所有pop/peek保证队列非空。进阶每个操作均摊O(1)时间复杂度。 核心思路一个栈负责进一个栈负责出“倒水”一次顺序归位一个栈为什么不行单栈模拟队列push正常压栈但pop要取栈底元素必须先把栈顶到栈底的元素全部临时搬到另一个数组取出栈底再搬回来。每次pop都是O(n)n次就是O(n²)显然不优雅。双栈分工in 管进out 管出inStackpush的新元素一律压入这里负责“收新货”。outStackpop/peek从这里取负责“出货”。关键规则当outStack为空时把inStack中所有元素一次性弹出并压入outStack。这个操作我称之为“倒水”——因为这一倒元素的顺序就翻转了inStack的栈底最早入队的变成了outStack的栈顶最先出队的✅。之后所有的pop/peek都从outStack取O(1)。直到outStack空了再触发下一次“倒水”。为什么是均摊 O(1)每个元素只经历三步压入inStack → 被倒进outStack → 从outStack弹出全程常数次操作。一次“倒水”虽O(k)但k个元素每个只被倒这一次平摊到每次操作上就是O(1)。搬家很累但只搬一次。️ 图解算法手把手走一遍push(1) → push(2) → push(3) → pop() → peek() → pop()步骤操作inStack底→顶outStack底→顶返回1push(1)[1][]—2push(2)[1,2][]—3push(3)[1,2,3][]—4pop()[]全部倒入[3,2,1]1栈顶5peek()[][3,2,1]1栈顶6pop()[][3,2]2第 4 步是灵魂outStack为空触发“倒水”。inStack的[1,2,3]底→顶依次弹出并压入outStack变成[3,2,1]底→顶。此时最早入队的1躺在了栈顶pop直接弹出完美复刻 FIFO ✅。 代码实现Python JavaPython 版classMyQueue:def__init__(self):self.in_stack[]# 入队栈self.out_stack[]# 出队栈defpush(self,x:int)-None:self.in_stack.append(x)# 新元素一律进 indefpop(self)-int:self._transfer()# 保证 out 有货returnself.out_stack.pop()defpeek(self)-int:self._transfer()returnself.out_stack[-1]defempty(self)-bool:returnnotself.in_stackandnotself.out_stackdef_transfer(self)-None:# 只在 out 为空时倒水一次倒干净ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())Java 版importjava.util.ArrayDeque;importjava.util.Deque;classMyQueue{privateDequeIntegerinStacknewArrayDeque();privateDequeIntegeroutStacknewArrayDeque();publicvoidpush(intx){inStack.push(x);}publicintpop(){transfer();returnoutStack.pop();}publicintpeek(){transfer();returnoutStack.peek();}publicbooleanempty(){returninStack.isEmpty()outStack.isEmpty();}privatevoidtransfer(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}}}⚠️关键细节必看_transfer()只在outStack为空时调用否则会打乱已有顺序混入“新货”会破坏 FIFO。peek和pop都要先调_transfer()共用逻辑。Java 推荐用ArrayDeque做栈性能优于Stack。⏱️ 复杂度分析面试必问操作时间复杂度说明pushO(1)直接压入 inStackemptyO(1)检查两个栈是否都空pop/peek均摊O(1)单次最坏O(n)触发倒水但每个元素只倒一次n次总O(n)严格证明会计法每个元素被压入in1次、弹出in 压入out2次、从out 弹出1次——总计4次常数操作均摊常数。 举一反三3道高频变体题题目变化点思路调整LC.225 用队列实现栈反过来用队列模拟栈push后把前面元素移到队尾让新元素“插队”到队首剑指Offer09 用两个栈实现队列同LC.232面试常客完全一致的“倒水”思想LC.155 最小栈栈 O(1)取最小值辅助栈存当前最小值是“双栈”的另一种形态 面试追问模拟提前准备Q1均摊O(1) 怎么严格证明会计法每个元素被压入in时我们给它“预存”3个单位的信用——未来它会被弹出in1、压入out1、再从out 弹出1。一次“倒水”的O(k)成本正好由这k个元素预存的信用覆盖所以每个操作的总成本是常数。因为每个元素只被倒一次总成本O(n)均摊O(1)。Q2什么时候会触发“倒水”只在outStack为空且执行pop或peek时。如果outStack还有货直接取栈顶即可——此时若再倒水会把inStack中的新元素混到outStack里破坏FIFO顺序因为outStack里还有更早入队的元素未出完。Q3只用一个栈能不能实现队列能但效率低每次pop要把栈顶到栈底的全部元素临时搬到辅助数组取出栈底再搬回来每次O(n)。递归也可视为隐式栈但本质还是两个栈。面试标准答案两个栈一个进一个出“倒水”一次一劳永逸。Q4如果同时有大量push和pop交替会不会频繁倒水不会。每次倒水后outStack会承载一批元素只有当这批元素全部弹出后才会触发下一次倒水。所以每个元素只倒一次交替操作也不会增加倒水次数。 实战小技巧刷题党必备口诀in管进out管出out空了再倒水一次倒干净。模板凡是“用X模拟Y”的设计题思考核心差异顺序反转用辅助结构逆转顺序。防坑peek和pop必须先transfer()别漏了。 实际应用场景不止是刷题消息队列缓冲区底层可用双栈优化批处理撤销/重做系统双栈模型撤销栈 重做栈表达式求值运算符栈 操作数栈网络数据包双缓冲收包栈 → 处理队列 今日思考题如果要求用“一个队列实现栈”你会怎么做提示push后把队列前面元素依次移到队尾让新元素“插队”到队首这样pop就直接取队首了。 双栈模拟队列：一次“倒水”，把LIFO硬生生扭成FIFO，均摊O(1)
栈LIFO和队列FIFO是数据结构里的一对“冤家”——一个后进先出一个先进先出。但面试官偏要问“能不能用栈实现队列”这就是LC.232这道经典设计题的由来。它不考复杂算法考的是你对两种数据结构本质差异的理解栈底元素要想先出去就得先把上面的都搬走。今天我们就用两个栈 一次“倒水”把LIFO硬生生变成FIFO而且每个操作均摊O(1)。更妙的是理解了“倒水”思想反过来“用队列实现栈”也顺理成章。 题目速览30 秒读懂用两个栈实现一个队列支持push、pop、peek、empty四个操作。示例push(1) → push(2) → peek() → pop() → empty() 输出1, 1, false约束操作次数 ≤ 100所有pop/peek保证队列非空。进阶每个操作均摊O(1)时间复杂度。 核心思路一个栈负责进一个栈负责出“倒水”一次顺序归位一个栈为什么不行单栈模拟队列push正常压栈但pop要取栈底元素必须先把栈顶到栈底的元素全部临时搬到另一个数组取出栈底再搬回来。每次pop都是O(n)n次就是O(n²)显然不优雅。双栈分工in 管进out 管出inStackpush的新元素一律压入这里负责“收新货”。outStackpop/peek从这里取负责“出货”。关键规则当outStack为空时把inStack中所有元素一次性弹出并压入outStack。这个操作我称之为“倒水”——因为这一倒元素的顺序就翻转了inStack的栈底最早入队的变成了outStack的栈顶最先出队的✅。之后所有的pop/peek都从outStack取O(1)。直到outStack空了再触发下一次“倒水”。为什么是均摊 O(1)每个元素只经历三步压入inStack → 被倒进outStack → 从outStack弹出全程常数次操作。一次“倒水”虽O(k)但k个元素每个只被倒这一次平摊到每次操作上就是O(1)。搬家很累但只搬一次。️ 图解算法手把手走一遍push(1) → push(2) → push(3) → pop() → peek() → pop()步骤操作inStack底→顶outStack底→顶返回1push(1)[1][]—2push(2)[1,2][]—3push(3)[1,2,3][]—4pop()[]全部倒入[3,2,1]1栈顶5peek()[][3,2,1]1栈顶6pop()[][3,2]2第 4 步是灵魂outStack为空触发“倒水”。inStack的[1,2,3]底→顶依次弹出并压入outStack变成[3,2,1]底→顶。此时最早入队的1躺在了栈顶pop直接弹出完美复刻 FIFO ✅。 代码实现Python JavaPython 版classMyQueue:def__init__(self):self.in_stack[]# 入队栈self.out_stack[]# 出队栈defpush(self,x:int)-None:self.in_stack.append(x)# 新元素一律进 indefpop(self)-int:self._transfer()# 保证 out 有货returnself.out_stack.pop()defpeek(self)-int:self._transfer()returnself.out_stack[-1]defempty(self)-bool:returnnotself.in_stackandnotself.out_stackdef_transfer(self)-None:# 只在 out 为空时倒水一次倒干净ifnotself.out_stack:whileself.in_stack:self.out_stack.append(self.in_stack.pop())Java 版importjava.util.ArrayDeque;importjava.util.Deque;classMyQueue{privateDequeIntegerinStacknewArrayDeque();privateDequeIntegeroutStacknewArrayDeque();publicvoidpush(intx){inStack.push(x);}publicintpop(){transfer();returnoutStack.pop();}publicintpeek(){transfer();returnoutStack.peek();}publicbooleanempty(){returninStack.isEmpty()outStack.isEmpty();}privatevoidtransfer(){if(outStack.isEmpty()){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}}}⚠️关键细节必看_transfer()只在outStack为空时调用否则会打乱已有顺序混入“新货”会破坏 FIFO。peek和pop都要先调_transfer()共用逻辑。Java 推荐用ArrayDeque做栈性能优于Stack。⏱️ 复杂度分析面试必问操作时间复杂度说明pushO(1)直接压入 inStackemptyO(1)检查两个栈是否都空pop/peek均摊O(1)单次最坏O(n)触发倒水但每个元素只倒一次n次总O(n)严格证明会计法每个元素被压入in1次、弹出in 压入out2次、从out 弹出1次——总计4次常数操作均摊常数。 举一反三3道高频变体题题目变化点思路调整LC.225 用队列实现栈反过来用队列模拟栈push后把前面元素移到队尾让新元素“插队”到队首剑指Offer09 用两个栈实现队列同LC.232面试常客完全一致的“倒水”思想LC.155 最小栈栈 O(1)取最小值辅助栈存当前最小值是“双栈”的另一种形态 面试追问模拟提前准备Q1均摊O(1) 怎么严格证明会计法每个元素被压入in时我们给它“预存”3个单位的信用——未来它会被弹出in1、压入out1、再从out 弹出1。一次“倒水”的O(k)成本正好由这k个元素预存的信用覆盖所以每个操作的总成本是常数。因为每个元素只被倒一次总成本O(n)均摊O(1)。Q2什么时候会触发“倒水”只在outStack为空且执行pop或peek时。如果outStack还有货直接取栈顶即可——此时若再倒水会把inStack中的新元素混到outStack里破坏FIFO顺序因为outStack里还有更早入队的元素未出完。Q3只用一个栈能不能实现队列能但效率低每次pop要把栈顶到栈底的全部元素临时搬到辅助数组取出栈底再搬回来每次O(n)。递归也可视为隐式栈但本质还是两个栈。面试标准答案两个栈一个进一个出“倒水”一次一劳永逸。Q4如果同时有大量push和pop交替会不会频繁倒水不会。每次倒水后outStack会承载一批元素只有当这批元素全部弹出后才会触发下一次倒水。所以每个元素只倒一次交替操作也不会增加倒水次数。 实战小技巧刷题党必备口诀in管进out管出out空了再倒水一次倒干净。模板凡是“用X模拟Y”的设计题思考核心差异顺序反转用辅助结构逆转顺序。防坑peek和pop必须先transfer()别漏了。 实际应用场景不止是刷题消息队列缓冲区底层可用双栈优化批处理撤销/重做系统双栈模型撤销栈 重做栈表达式求值运算符栈 操作数栈网络数据包双缓冲收包栈 → 处理队列 今日思考题如果要求用“一个队列实现栈”你会怎么做提示push后把队列前面元素依次移到队尾让新元素“插队”到队首这样pop就直接取队首了。