LeetCode Implement Queue using Stacks：雙棧模擬隊列

題目簡介

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

解題思路

使用兩個棧 inStack（入隊棧）和 outStack（出隊棧）：

• push(x)：直接壓入 inStack。
• pop()：若 outStack 為空，將 inStack 所有元素彈出壓入 outStack（順序反轉），再彈出 outStack 栈頂。
• peek()：同 pop 邏輯，但只查看 outStack 栈頂不彈出。
• empty()：兩棧均空才為真。

均攤時間 O(1)。

代碼實現

class Queue {
    stack<int> inStack, outStack;
public:
    void push(int x) { inStack.push(x); }
    void pop() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        outStack.pop();
    }
    int peek() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    bool empty() { return inStack.empty() && outStack.empty(); }
};

複雜度分析

每個元素最多進出兩次棧，均攤 O(1)。空間 O(n)。