本文详解如何用两个栈（instack 和 outstack）高效模拟队列的 fifo 行为，重点阐明为何 dequeue 仅在 outstack 为空时才触发元素转移、为何无需将元素“回填”至 instack，以及该设计如何实现均摊 o(1) 时间复杂度。
本文详解如何用两个栈（instack 和 outstack）高效模拟队列的 fifo 行为，重点阐明为何 dequeue 仅在 outstack 为空时才触发元素转移、为何无需将元素“回填”至 instack，以及该设计如何实现均摊 o(1) 时间复杂度。
在用两个栈实现队列的经典方案中，“入队栈（inStack）只进不出，出队栈（outStack）只出不进”是核心分工原则。这一设计巧妙利用了“两次反转即还原顺序”的数学本质：
- 元素按
1→2→3→4入队 → 在 inStack 中存储为[4,3,2,1]（栈顶在前）； - 当首次调用
dequeue()且 outStack 为空时，将 inStack 全部弹出并压入 outStack → outStack 变为[1,2,3,4]（此时栈顶为1，即队首）； - 后续
dequeue()直接pop()outStack 栈顶，无需触碰 inStack —— 这才是关键所在。
你代码中的逻辑正是如此：
public int dequeue() {
if (s1.isEmpty() && s2.isEmpty())
throw new NoSuchElementException("Queue is empty");
// ✅ 关键判断：仅当 outStack(s2) 为空时，才从 inStack(s1) 转移元素
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop()); // 一次性反转全部现存元素
}
}
// ❌ 注意：此处没有“把 s2 剩余元素再推回 s1”的操作！
return s2.pop(); // 直接弹出 outStack 栈顶（即最早入队的元素）
}
让我们逐步追踪你的示例执行过程：
| 操作 | inStack (s1) | outStack (s2) | 说明 |
|---|---|---|---|
enqueue(5) |
[5] |
[] |
入队栈接收 |
enqueue(10) |
[10,5] |
[] |
— |
enqueue(15) |
[15,10,5] |
[] |
— |
enqueue(20) |
[20,15,10,5] |
[] |
— |
dequeue()（第一次） |
[] |
[5,10,15,20] |
s2 空 → 全量转移 → s2 栈顶为 5 → 返回 5
|
enqueue(25) |
[25] |
[10,15,20] |
✅ s2 非空，s1 独立接收新元素 |
dequeue()（第二次） |
[25] |
[15,20] |
✅ s2 仍非空 → 直接 pop() → 返回 10（原 s2 的第二个元素） |
dequeue()（第三次） |
[25] |
[20] |
继续 pop() → 返回 15
|
✅ 此时你观察到 10 被正确弹出，正是因为：
- 第一次转移后，outStack 已按 FIFO 顺序固化为
[5,10,15,20]（栈底→栈顶 = 队首→队尾）； - 后续
dequeue()不再触发转移，而是持续消费 outStack 的栈顶，直到它再次变空； -
enqueue(25)仅作用于 inStack，与 outStack 完全解耦 —— 这正是 O(1) 入队的保障。
⚠️ 重要提醒：不要混淆“转移时机”与“数据归属”
- 转移不是每次 dequeue 都发生，而是懒加载式触发（lazy transfer）；
- 一旦元素进入 outStack，它就“归属”于出队序列，不再返回 inStack —— 否则将破坏顺序性与时间复杂度；
- inStack 和 outStack 是互补而非镜像：二者共同构成队列的完整状态，但职责严格隔离。
? 性能分析（摊还分析）
-
enqueue()：恒为 O(1) —— 仅一次push； -
dequeue()：均摊 O(1) —— 单次最坏 O(n)，但每个元素最多被push/pop各两次（inStack 一次 + outStack 一次），故 n 次操作总代价为 O(n)； -
peek()/empty()：均为 O(1)。
✅ 总结一句话：outStack 是“已排序缓存”，inStack 是“待排序缓冲区”。只要缓存未耗尽，就绝不重排——这正是高效与正确的统一。
