232. Implement Queue using Stacks

📘 題目敘述

請只使用兩個 stack 來實作一個先進先出（FIFO）的 queue。

這個 queue 需要支援一般 queue 的所有功能：

push(x)：把元素 x 加到 queue 的尾端
pop()：移除並回傳 queue 前端的元素
peek()：回傳 queue 前端的元素
empty()：如果 queue 是空的回傳 true，否則回傳 false

注意：

只能使用 stack 的標準操作，也就是：
- push 到頂端
- peek/pop 從頂端
- size
- empty
如果語言本身沒有 stack，可以用 list 或 deque 模擬，但仍然只能使用 stack 的標準操作

條件限制

1 <= x <= 9
push、pop、peek、empty 最多總共呼叫 100 次
所有 pop 和 peek 呼叫都保證合法

🧠 解題思路

我這份寫法的想法是：

我只用一個主要 stack s 來保存 queue 的順序
並且讓 s.top() 永遠就是 queue 的前端

這樣的好處是：

pop() 很直接，直接把 s.top() 拿掉
peek() 也很直接，直接看 s.top()

但問題是：

queue 的新元素要加在尾端
stack 只能從頂端放東西

所以我在 push(x) 時，會先把原本 s 裡的元素全部搬到暫時的 stack t，讓 s 清空後先放入新元素 x，再把 t 裡的東西搬回來。

這樣做完之後，整個 s 從 top 到 bottom 的順序，就會對應 queue 從 front 到 back 的順序。

所有變數

s：主要的 stack，s.top() 永遠代表 queue 的前端
t：只在 push 裡暫時使用的 stack，用來搬運元素
x：要加入 queue 的元素，或 pop() 時拿出的前端元素

🪜 主要流程步驟

1. 用 stack `s` 直接保存 queue 順序

stack<int> s; // 頭是舊的

這裡的意思是：

s.top() 放的是 queue 最前面的元素
越下面就是越後面的元素

所以如果 queue 是：

[1, 2, 3]

那 stack s 的 top 到 bottom 就會是：

1, 2, 3

這樣之後：

pop() 拿 top 就等於 queue 出隊
peek() 看 top 就等於看 queue 前端

2. `push(x)` 時，先把原本元素全部搬走

因為 stack 只能從頂端放入新元素，但 queue 的 push 是要把新元素加在最後面。

所以我先開一個暫時的 stack t，把 s 裡原本的元素全部搬過去。

這樣搬完之後：

s 會清空
t 會暫時保存原本 queue 的所有元素

3. 把新元素先放進空的 `s`

s.push(x);

此時 s 是空的，所以我可以先把新元素 x 放進去。

因為它最後要變成 queue 的尾端，所以它在 stack 裡應該待在比較底下的位置。

4. 再把暫存的元素搬回來

把 t 裡的元素再搬回 s 後，順序就會變成：

最舊的元素回到最上面
新加入的 x 留在最下面

所以最後 s.top() 還是 queue 的前端，而新元素 x 則會排在 queue 的最後。

這樣就完成了 queue 的 push。

5. `pop()` 直接拿 `s.top()`

int x = s.top();
s.pop();
return x;

因為我一開始就設計成：

s.top() 永遠是 queue 的前端

所以 pop() 很直接：

先記下 s.top()
再把它 pop 掉
最後回傳這個值

這就等同於 queue 的出隊操作。

6. `peek()` 直接回傳 `s.top()`

return s.top();

同樣因為 s.top() 就是 queue 的前端，所以 peek() 不需要做任何搬運，直接回傳即可。

7. `empty()` 直接看 `s` 是不是空的

return s.empty();

如果 s 沒有元素，就代表 queue 是空的。所以這裡直接回傳 s.empty() 即可。

⏱️ 複雜度

設 queue 目前有 n 個元素。

push(x) 的時間複雜度：O(n)
因為要把原本元素搬到 t，再搬回來。
pop() 的時間複雜度：O(1)
直接取 s.top() 並 pop。
peek() 的時間複雜度：O(1)
直接看 s.top()。
empty() 的時間複雜度：O(1)
直接看 s.empty()。
空間複雜度：O(n)
主要 stack s 會存所有 queue 元素，push 時暫時的 t 最多也會搬運這些元素。

💻 程式碼實作

class MyQueue {
public:
    stack<int> s; // 頭是舊的
    MyQueue() {}

    void push(int x) {
        stack<int> t;
        while (!s.empty()) {
            t.push(s.top());
            s.pop();
        }
        s.push(x);
        while (!t.empty()) {
            s.push(t.top());
            t.pop();
        }
    }

    int pop() {
        int x = s.top();
        s.pop();
        return x;
    }

    int peek() { 
        return s.top(); 
    }

    bool empty() { 
        return s.empty(); 
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

🔗 題目連結

https://leetcode.com/problems/implement-queue-using-stacks/

232. Implement Queue using Stacks

📘 題目敘述

條件限制

🧠 解題思路

所有變數

🪜 主要流程步驟

1. 用 stack s 直接保存 queue 順序

2. push(x) 時，先把原本元素全部搬走

3. 把新元素先放進空的 s