佇列與堆疊

兩個只差在「從哪一端拿」的容器。 · ⏱ 約 30 分鐘

你會學到三件事

1. queue 先進先出、stack 後進先出
2. 它們故意不讓你看中間
3. 遞迴其實就是一個你看不見的 stack

開始之前

vector 什麼都能做——那為什麼還要這兩個？

因為限制本身是有價值的。看完這一課再回來想這句話。

一、兩個，一眼看完

queue<int> q;                  stack<int> st;
q.push(1);                     st.push(1);
q.push(2);                     st.push(2);
cout << q.front();  // 1       cout << st.top();  // 2
q.pop();                       st.pop();
cout << q.front();  // 2       cout << st.top();  // 1

⚠️ 名字不一樣：queue 用 front()，stack 用 top()。

⚠️ pop() 不回傳值——它只是拿掉。要值得先 front() / top()。

⚠️ 空的時候呼叫 front() / top() 是未定義行為，不會報錯。 用之前先 if (!q.empty())。

二、🔴 它們故意不讓你看中間

q[3] 是不合法的。這不是缺功能，是設計。

一個限制得剛好的工具，讓錯誤的用法寫不出來。

用 vector 模擬佇列的話，你可以不小心從中間拿東西—— 而那多半是一個 bug。queue 讓那個 bug 連編譯都過不了。

所以判準是：你的演算法只從兩端動嗎？ 是 → 用專門的那個。

三、它們各自在哪裡出現

四、🔴 遞迴就是一個看不見的 stack

C++ 入門第 16 課的階乘：

f(5) → f(4) → f(3) → f(2) → f(1)
                                 ↓ 回來
                        ← ← ← ← ←

那個「回來」的順序是後進先出——最後被叫的最先回來。

電腦就是用一個 stack 存這些「還沒回來的呼叫」，那叫呼叫堆疊。

⚠️ 所以「遞迴太深會 stack overflow」是字面意思：那個 stack 滿了。

而反過來：任何遞迴都可以改寫成用一個 stack 的迴圈。 遞迴太深時就是這樣改的。

完成的樣子

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    cout << q.front() << endl;
    q.pop();
    cout << q.front() << endl;
    stack<int> st;
    st.push(1);
    st.push(2);
    cout << st.top() << endl;
    return 0;
}

下一課

queue 和 stack 是標準函式庫給你的。下一課要自己做一個 ——那是 Linked List，而它也是後面「圖」和「樹」的地基。

換你了

用 stack 判斷一串括號有沒有配對好："(())" ✅、"(()" ❌。

提示：遇到 ( 就 push，遇到 ) 就 pop。 ⚠️ 兩個地方要小心：pop 之前 stack 空了（右括號太多）， 以及最後 stack 沒空（左括號太多）。

這一課你做了什麼

• 你用了兩個只差在「從哪一端拿」的容器
• 你知道它們的限制是設計，不是缺功能
• 你知道遞迴背後就是一個 stack

如果卡住了