佇列與堆疊

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

你會學到三件事

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

開始之前

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

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

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、兩個，一眼看完

同樣放進 1、2，再拿出來——差別只在拿出來的是哪一端：

1queue<int> q;2q.push(1);3q.push(2);4cout << q.front();  // 15q.pop();6cout << q.front();  // 2

1stack<int> st;2st.push(1);3st.push(2);4cout << st.top();  // 25st.pop();6cout << st.top();  // 1

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

積木盤上它們寫著「… 的前端元素」與「… 的頂端元素」 ——而放進去、拿出來那兩顆是「推 … 到 … 的頂端／尾端」 與「從 … 的頂端移除」（stack）／「從 … 的前端移除」（queue）。

⚠️ 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 的迴圈。 遞迴太深時就是這樣改的。

完成的樣子

1#include <iostream>2#include <queue>3#include <stack>4using namespace std;5int main() {6    queue<int> q;7    q.push(1);8    q.push(2);9    cout << q.front() << endl;10    q.pop();11    cout << q.front() << endl;12    stack<int> st;13    st.push(1);14    st.push(2);15    cout << st.top() << endl;16    return 0;17}

下一課

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

換你了

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

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

問「空了沒」那顆積木寫著「… 是否為空」。 🔴 pop 之前一定要先問它——對一個空的 stack 呼叫 pop() 不是錯誤，是未定義行為：它可能看起來好好的，直到換一台機器。

到編輯器做這一題：練習：用 stack 判斷括號有沒有配對好

做一個

7 個人圍成一圈（編號 1 到 7），從 1 開始報數，每數到第 3 個人就出局， 一直到剩一個人。印出他的編號。

🔴 用 queue：沒出局的就從前面拿出來、排到後面去。 這一題不用陣列也不用刪除，那正是佇列適合的形狀。

到編輯器做這一題：做一個：數到三就出局

這一課你做了什麼

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

如果卡住了