雙棧實現佇列：Java 完整實現與時間複雜度分析

核心思想

• Stack1 (inStack)：專職**入隊** (push)，元素按到達順序疊放，最新在頂。
• Stack2 (outStack)：專職**出隊** (pop)，元素順序與佇列 FIFO 一致，最舊在頂。
• 出隊時若 outStack 為空，將 inStack 全部 pop 再 push 進 outStack，順序自動反轉。

完整 Java 實現

import java.util.Stack;

public class QueueWithTwoStacks {
    private final Stack inStack = new Stack<>();
    private final Stack outStack = new Stack<>();

    /** 入隊：O(1) */
    public void appendTail(E e) {
        inStack.push(e);
    }

    /** 出隊：均攤 O(1) */
    public E deleteHead() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        if (outStack.isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return outStack.pop();
    }

    /** 輔助：查看隊首不移除 */
    public E peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.peek();
    }

    public boolean isEmpty() { return inStack.isEmpty() && outStack.isEmpty(); }
    public int size() { return inStack.size() + outStack.size(); }
}

時間複雜度證明：均攤 O(1)

• 每個元素**一生只被移動一次**：inStack.push → inStack.pop → outStack.push → outStack.pop。
• N 次操作總移動次數 ≤ 2N，均攤每操作 ≤ 2 次棧操作 = O(1)。
• 最壞單次 deleteHead() 觸發搬移 O(k)，但後續 k-1 次為 O(1)。

空間複雜度

O(N) — 兩棧共存元素總數等於佇列大小，無額外開銷。

變體與擴展

面試延伸題

1. 用佇列實現棧：單佇列 push 後旋轉 n-1 次，pop 直接 poll。
2. 實現 getMin() O(1) 的棧：輔助棧同步存最小值。
3. 為什麼不用 ArrayList 直接實現佇列？：remove(0) 觸發陣列位移 O(n)；環形陣列可 O(1) 但需擴容策略。

生產代碼建議

**直接用 ArrayDeque** — 實現雙端佇列、陣列基底、無容量上限、非線程安全但效能極佳，JDK 內部 Stack 文檔已建議棄用。

雙棧佇列是經典面試題，理解「空間換時間、延遲反轉、均攤分析」三大思想，比背誦代碼更有價值。