232. 用棧實現隊列

思路

建立兩個棧，一個叫in，一個叫out，每次加入新數字時，就將數字放到in當中，
當需要輸出數字時，將in的資料傾倒到out當中，再從out取第一個數字，就能依照當初加入的順序去輸出。

假如此時out不為空，表示裡面還有數字沒輸出，不能將in倒入，因為會把原先要輸出的數字往下壓。

程式碼

stack

class MyQueue {
private:
    stack<int> in, out;
private:
    void inToOut() {
        if(out.empty()) {
            while(!in.empty()) {
                out.push(in.top());
                in.pop();
            }
        }
    }
public:
    MyQueue() {}

    void push(int x) {
        in.push(x);
        inToOut();
    }

    int pop() {
        inToOut();
        int res = out.top(); out.pop();
        return res;
    }

    int peek() {
        inToOut();
        return out.top();
    }

    bool empty() {
        return in.empty() && out.empty();
    }
};

複雜度分析

• 時間複雜度：$O(1)$ 在最糟的情況，每筆資料都會進入in，倒到out，從out取出。
• 空間複雜度：$O(n)$，in，out的存放的元素數量最多為 $n$