LeetCode 232 用棧實現隊列：雙棧模擬先進先出

題目描述

僅使用棧的標準操作（push/pop/peek/empty/size）實現隊列：

• push(x)：元素入隊尾
• pop()：移除隊首元素
• peek()：返回隊首元素
• empty()：判斷隊列是否為空

假設所有操作合法（不會對空隊列 pop/peek）。

解題思路：一主一輔雙棧

核心洞察：棧是後進先出（LIFO），隊列是先進先出（FIFO）。兩個棧串聯可逆轉順序：

• s_main：主棧，push 直接入此棧
• s_aux：輔助棧，pop/peek 時將 s_main 元素倒入 s_aux，順序反轉，隊首即在 s_aux 栈頂

操作細節：

1. push(x)：s_main.push(x) — O(1)
2. pop()：若 s_aux 為空，將 s_main 全部倒入；彈出 s_aux.top() — 攤銷 O(1)
3. peek()：同 pop 但不彈出 — 攤銷 O(1)
4. empty()：s_main.empty() && s_aux.empty()

C++ 參考實現

class Queue {
public:
    std::stack s_main, s_aux;
    
    // 入隊：直接壓入主棧
    void push(int x) {
        s_main.push(x);
    }
    
    // 出隊：輔助棧為空時倒入，再彈出
    void pop() {
        if (s_aux.empty()) {
            while (!s_main.empty()) {
                s_aux.push(s_main.top());
                s_main.pop();
            }
        }
        s_aux.pop();
    }
    
    // 隊首：輔助棧為空時倒入，返回栈頂
    int peek() {
        if (s_aux.empty()) {
            while (!s_main.empty()) {
                s_aux.push(s_main.top());
                s_main.pop();
            }
        }
        return s_aux.top();
    }
    
    bool empty() {
        return s_main.empty() && s_aux.empty();
    }
};

優化版：Lazy Transfer（延遲轉移）

僅在 s_aux 為空時才轉移，每個元素最多進出兩次棧，攤銷時間複雜度 O(1)。

核心要點總結

• 雙棧反轉：利用兩次 LIFO 實現 FIFO
• 攤銷分析：單次操作可能 O(n)，但 n 次操作總共 O(n)
• 對比題目：LeetCode 225（用隊列實現棧）對稱問題，同理雙隊列模擬
• 工程應用：實際中可用 deque 直接實現隊列，本題純演練數據結構轉換思想

「用棧實現隊列」是數據結構轉換的經典教學題，掌握「主輔棧 + 延遲轉移」模式，舉一反三解決同類模擬問題。