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

題目描述

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

• push(x)：元素入棧頂
• pop()：移除棧頂元素
• top()：返回棧頂元素
• empty()：判斷棧是否為空

解題思路：雙隊列倒序

與「用棧實現隊列」對稱。隊列 FIFO，棧 LIFO。利用兩個隊列：

• q_main：主隊列，push 直接入隊
• q_aux：輔助隊列，pop/top 時將 q_main 除最後一個元素外全部倒入 q_aux，最後一個即為棧頂

操作細節：

1. push(x)：q_main.push(x) — O(1)
2. pop()：倒入 q_main.size()-1 個到 q_aux，彈出 q_main 最後一個，交換兩隊列 — O(n)
3. top()：同 pop 但將最後一個也入 q_aux 再交換 — O(n)
4. empty()：q_main.empty()

C++ 參考實現

class Stack {
public:
    std::queue q_main, q_aux;
    
    void push(int x) {
        q_main.push(x);
    }
    
    void pop() {
        if (q_main.size() == 1) {
            q_main.pop();
        } else {
            while (q_main.size() > 1) {
                q_aux.push(q_main.front());
                q_main.pop();
            }
            q_main.pop();
            while (!q_aux.empty()) {
                q_main.push(q_aux.front());
                q_aux.pop();
            }
        }
    }
    
    int top() {
        if (q_main.size() == 1) return q_main.front();
        while (q_main.size() > 1) {
            q_aux.push(q_main.front());
            q_main.pop();
        }
        int val = q_main.front();
        q_aux.push(q_main.front());
        q_main.pop();
        while (!q_aux.empty()) {
            q_main.push(q_aux.front());
            q_aux.pop();
        }
        return val;
    }
    
    bool empty() {
        return q_main.empty();
    }
};

核心要點總結

• 對稱性：LeetCode 232（棧→隊列）與 225（隊列→棧）互為鏡像
• 時間複雜度：push O(1)，pop/top O(n) — 無攤銷優化空間
• 單隊列優化：實際可用單隊列，push 後旋轉隊列使新元素到隊首，但本題要求雙隊列演示
• 工程意義：理解數據結構底層轉換本質，實際開發直接用 std::stack/deque

「用隊列實現棧」展示了 FIFO 如何模擬 LIFO，掌握「主輔隊列 + 保留最後一個」模式，深化數據結構操作本質理解。