LeetCode 232. Implement Queue using Stacks

问题描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。使用自定义的 MyQueue 类（位于 datastructure 包中），内部用两个栈实现队列。

解题思路

栈是后进先出（LIFO）的数据结构，队列是先进先出（FIFO）的数据结构。要用栈模拟队列，关键在于两次入栈等于一次顺序反转。

双栈设计

使用两个栈：

• 输入栈（stackIn）：专门负责接收 push 操作
• 输出栈（stackOut）：专门负责 pop 和 peek 操作

核心操作原理

1. push(x)：直接将元素压入 stackIn。时间复杂度 O(1)。

2. pop() / peek()：

   • 如果 stackOut 不为空，直接从 stackOut 弹出/查看栈顶元素
   • 如果 stackOut 为空，则将 stackIn 中的所有元素依次弹出并压入 stackOut。经过这次转移，stackIn 中的元素顺序被反转，stackOut 的栈顶恰好就是整个队列的队首元素

3. empty()：当两个栈都为空时，队列为空。

为什么这样做是正确的？

假设依次 push 1, 2, 3：

• stackIn（栈顶在右）：[1, 2, 3]
• 当需要 pop 时，将 stackIn 全部转移到 stackOut：
  • 弹出 3，压入 stackOut → [3]
  • 弹出 2，压入 stackOut → [3, 2]
  • 弹出 1，压入 stackOut → [3, 2, 1]
• 此时 stackOut 栈顶是 1，正是最先入队的元素，pop 返回 1

关键点：只有当 stackOut 为空时才从 stackIn 转移元素，这保证了元素的 FIFO 顺序不被破坏。如果一边 pop 一边 push，新 push 的元素会暂存在 stackIn 中，等 stackOut 再次变空时才会被转移过来。

复杂度分析

• push 时间复杂度：O(1)
• pop/peek 均摊时间复杂度：O(1)。虽然单次转移操作可能需要 O(n)，但每个元素最多被转移两次（一次从 stackIn 到 stackOut，一次从 stackOut 弹出），均摊下来每次操作 O(1)
• 空间复杂度：O(n)，两个栈共存储 n 个元素

代码

package code.J232;

import datastructure.MyQueue;

public class J232 {
    MyQueue myQueue = new MyQueue();
}