用两个栈高效实现队列：基于分工与惰性转移的O(1)均摊设计-java教程-PHP中文网

用两个栈高效实现队列：基于分工与惰性转移的O(1)均摊设计

本文详解如何用两个栈（instack 和 outstack）模拟队列的 fifo 行为，核心在于“入队只进 instack、出队优先取 outstack”，仅当 outstack 为空时才批量转移 instack 元素——此举确保 enqueue 恒为 o(1)，dequeue 均摊 o(1)，且逻辑清晰、边界鲁棒。

本文详解如何用两个栈（instack 和 outstack）模拟队列的 fifo 行为，核心在于“入队只进 instack、出队优先取 outstack”，仅当 outstack 为空时才批量转移 instack 元素——此举确保 enqueue 恒为 o(1)，dequeue 均摊 o(1)，且逻辑清晰、边界鲁棒。

在栈（LIFO）上构建队列（FIFO）的本质矛盾，是顺序的两次反转：第一次压入 inStack 将输入序列倒序，第二次整体转移到 outStack 再倒序一次，便还原原始入队顺序。但关键不在于“每次操作都反转”，而在于按需、惰性、单向转移——这正是高效实现的灵魂。

✅ 正确的操作逻辑：分工明确，转移有界

enqueue(x)：无条件将 x 压入 inStack。时间复杂度恒为 O(1)。
dequeue()：
- 若 outStack 非空 → 直接 pop() 栈顶（即队首），O(1)；
- 若 outStack 为空 → 将 inStack 中所有现存元素一次性弹出并压入 outStack（完成顺序翻转），再 pop()；此转移仅发生一次，后续出队复用 outStack，摊还代价为 O(1)。

⚠️ 重要澄清：绝不会在 outStack 非空时把新入队元素（如 25）再推入 outStack！
你原理解中的误区在于误以为“每次 dequeue 都要重新合并两栈”。实际上，代码中 while(!s1.isEmpty()) {...} 被严格包裹在 if(s2.isEmpty()) 内——只要 s2 还有元素，就跳过转移，直接出队。这保证了 s2 中始终维护着一个已就绪的 FIFO 序列（最早入队的在栈顶）。

以你的示例逐步验证：

操作	`s1`（inStack）	`s2`（outStack）	说明
`enqueue(5)`	`[5]`	`[]`	—
`enqueue(10)`	`[10,5]`	`[]`	—
`enqueue(15)`	`[15,10,5]`	`[]`	—
`enqueue(20)`	`[20,15,10,5]`	`[]`	—
`dequeue()` → 触发转移	`[]`	`[5,10,15,20]`	`s2.pop()` 返回 `5`，`s2` 变为 `[10,15,20]`
`enqueue(25)`	`[25]`	`[10,15,20]`	`s2` 非空，不转移
`dequeue()`	`[25]`	`[15,20]`	直接 `s2.pop()` → `10` ✅
`dequeue()`	`[25]`	`[20]`	`s2.pop()` → `15` ✅

可见：25 仍安静躺在 s1 中，未参与本次出队；s2 像一个“已预处理缓存”，持续提供正确队首，直到耗尽才触发下一次批量加载。

? 完整 Java 实现（含健壮校验）

import java.util.*;

class MyQueue {
    private Stack<integer> inStack = new Stack();
    private Stack<integer> outStack = new Stack();

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (empty()) throw new NoSuchElementException("Queue is empty");
        ensureOutStackReady(); // 仅当 outStack 为空时转移
        return outStack.pop();
    }

    public int peek() {
        if (empty()) throw new NoSuchElementException("Queue is empty");
        ensureOutStackReady();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    // 惰性加载：仅当 outStack 为空时，将 inStack 全部倒入
    private void ensureOutStackReady() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}</integer></integer>

⚖️ 性能与设计优势总结

时间复杂度：
- push() / empty() / peek()（非首次）：O(1)
- pop()：均摊 O(1) —— 每个元素最多被 push/pop 各两次（inStack 一次，outStack 一次），n 次操作总代价 O(n)。
空间复杂度：O(n)，仅存储元素本身。
工程优势：
- 无冗余移动（如不将 s2 元素倒回 s1）；
- 边界安全（空队列检查前置）；
- 符合直觉：inStack 是“待处理区”，outStack 是“就绪服务窗口”。