Learning Objectives
- 說明堆疊（後進先出）與佇列（先進先出）的差別，各舉一個使用情境
- 用陣列和一個 size 變數實作堆疊，說明 push 與 pop 都是 O(1)
- 使用 Python、C++、Java 內建的堆疊與佇列
- 用堆疊解決括號配對與後序運算式求值
- 用陣列加 head、tail 實作環狀佇列，並用雙向佇列求滑動視窗的最大值
只能從一端或兩端進出的串列
編輯器的「復原」會先取消最後做的那個動作；餐廳排隊叫號則是最早來的人先入座。 兩者都是「一排資料」，差別只在從哪一端拿：
| 結構 | 規則 | 生活中的例子 | 程式裡的例子 |
|---|---|---|---|
| 堆疊（stack） | 後進先出（LIFO，last in first out） | 一疊盤子，只能從最上面拿 | 復原、瀏覽器的上一頁、函數呼叫（第 05 課的呼叫堆疊）、括號配對 |
| 佇列（queue） | 先進先出（FIFO，first in first out） | 排隊結帳 | 印表機工作、訊息排程、廣度優先搜尋（第 16 課） |
它們能做的事比串列少，為什麼還要特別學？因為「只能從固定一端存取」讓操作都是 O(1)，而且很多問題的處理順序剛好就是後進先出或先進先出， 用對結構，程式會變得很短。
堆疊的操作名稱：放進去叫 push，拿出最上面的叫 pop，只看不拿叫 peek 或 top。
用陣列實作堆疊
堆疊只需要一個陣列和一個 size：push 寫在 data[size] 再把 size 加 1，pop 把 size 減 1 再讀 data[size]。注意 pop 之後，舊的值還留在陣列裡，只是已經不在青綠色範圍內；下一次 push 就會把它蓋掉。
各語言內建的堆疊
push 和 pop 都只動到陣列的尾端，不需要搬動其他元素，所以都是 O(1)（陣列滿了要擴充時例外，攤銷後仍是 O(1)，見第 03 課）。實際寫程式時用內建的工具：
| 操作 | Python（list） | C++（stack<int>） |
Java（ArrayDeque<Integer>） |
|---|---|---|---|
| 建立 | st = [] |
stack<int> st; |
ArrayDeque<Integer> st = new ArrayDeque<>(); |
| push | st.append(x) |
st.push(x) |
st.addLast(x) |
| pop | st.pop()（會回傳值） |
st.top() 讀值，再 st.pop()（不回傳） |
st.removeLast()（會回傳值） |
| 看頂端 | st[-1] |
st.top() |
st.peekLast() |
| 是不是空的 | len(st) == 0 |
st.empty() |
st.isEmpty() |
幾個要注意的地方：
- C++ 的
pop()不回傳值，要先用top()讀再pop()。 - 對空堆疊 pop 是錯誤：Python 會丟出
IndexError，Java 的removeLast()丟出NoSuchElementException，C++ 則是未定義行為（程式可能直接當掉），所以 pop 前要先檢查是否為空。 - Java 有一個舊的
Stack類別，官方文件建議改用ArrayDeque。ArrayDeque兩端都能放入、取出；本課一律在尾端操作（addLast、removeLast、peekLast）， 所以三種語言在動畫裡的頂端都在右邊。ArrayDeque另外也有push／pop／peek，它們作用在前端，一樣是後進先出，只是頂端在左邊。
括號配對：最近的左括號先配對
{[()()]} 的括號是正確配對的，([)] 不是。檢查的關鍵是：遇到右括號時，它必須和最近一個還沒配對的左括號同類。
「最近放進去的先拿出來」正是堆疊：
- 遇到左括號：push 進堆疊
- 遇到右括號：堆疊是空的就錯（多了右括號）；否則 pop 出最近的左括號，類型不同就錯
- 全部看完，堆疊裡還有東西就錯（左括號沒有關閉）
下面的範例在堆疊裡存的是左括號的位置（索引），這樣出錯時可以指出是哪一個字元。
括號配對：堆疊存左括號的位置
{[()()]}：每遇到左括號就把它的索引放進堆疊，遇到右括號就拿出最近的一個比對，最後堆疊剛好清空。([)]：看到 ) 時拿出來的是索引 1 的 [，類型不同。(()：看完時堆疊裡還剩索引 0。
後序運算式：不需要括號的寫法
平常寫的 (3 + 4) * 2 - 7 叫中序（運算子在兩個運算元中間），需要括號和優先順序才知道先算什麼。
後序（postfix）把運算子寫在兩個運算元後面：
中序：(3 + 4) * 2 - 7
後序：3 4 + 2 * 7 -
後序不需要括號，而且用堆疊由左到右掃一遍就能算出來：
- 遇到數字：push
- 遇到運算子：pop 兩次，先 pop 出來的是右邊的運算元，計算後把結果 push 回去
- 掃完時，堆疊裡剩下的唯一一個數就是答案
減法和除法要特別注意順序：7 - 是「前面的結果減 7」，所以是 left - right。Python 和 Java 把程式編譯成的位元組碼（bytecode），也是用堆疊這樣計算運算式。
用堆疊計算 3 4 + 2 * 7 -
數字直接放進堆疊；遇到 + 時拿出 4 和 3，放回 7；遇到 * 拿出 2 和 7，放回 14；遇到 - 拿出 7 和 14，算 14 - 7，放回 7。
想一想：堆疊
下面的程式會印出什麼？
用本課的括號配對方法檢查，下面哪一個字串是正確配對的？
後序運算式 5 1 2 + 4 * + 3 - 的值是多少？
佇列：從後面進、從前面出
佇列的兩個操作是 enqueue（放到尾端）和 dequeue（從前端取出）。用 Python 的 list 實作時，append 放到尾端是 O(1)，
但 pop(0) 從前端取出要把後面每個元素往前搬一格，是 O(n)。
用陣列實作佇列、又要兩個操作都 O(1)，做法是環狀佇列（circular queue）：元素不搬動，改成用兩個索引記錄位置：
head：下一個要取出的位置tail：下一個要放入的位置- 往後移一格寫成
(index + 1) % cap：走到陣列最後一格之後，回到 0 繼續使用前面空出來的位置
另外用 count 記錄有幾個元素，才分得出「空」和「滿」（兩種情況下 head 都等於 tail）。
環狀佇列：head 和 tail 繞圈
放入 10、20、30 後取出 10、20，前兩格空了出來。接著放入 40 時 tail 走到最後一格，再放 50 時 tail 回到索引 0，繼續使用前面空出來的位置。放完 60 時佇列已滿（count = 4），70 放不進去。
各語言內建的佇列與雙向佇列
實際寫程式時用內建的佇列，內部已經做好 O(1) 的兩端操作：
| 操作 | Python（collections.deque） |
C++（queue<int>） |
Java（ArrayDeque<Integer>） |
|---|---|---|---|
| 放到尾端 | q.append(x) |
q.push(x) |
q.offer(x) |
| 從前端取出 | q.popleft() |
q.front() 讀值，再 q.pop() |
q.poll() |
| 看前端 | q[0] |
q.front() |
q.peek() |
| 是不是空的 | len(q) == 0 |
q.empty() |
q.isEmpty() |
雙向佇列（deque，double-ended queue）兩端都能放入和取出，都是 O(1)。堆疊和佇列都可以看成它的特例：
| 操作 | Python deque |
C++ deque<int> |
Java ArrayDeque |
|---|---|---|---|
| 前端放入／取出 | appendleft／popleft |
push_front／pop_front |
offerFirst／pollFirst |
| 尾端放入／取出 | append／pop |
push_back／pop_back |
offerLast／pollLast |
| 看前端／尾端 | dq[0]／dq[-1] |
front()／back() |
peekFirst()／peekLast() |
Java 的 ArrayDeque 同時有兩套名稱：當堆疊用時 push／pop 作用在前端，當佇列用時 offer 放到尾端、poll 從前端取出。
同一個物件混用兩套方法時，要清楚元素放在哪一端。
雙向佇列的應用：滑動視窗的最大值
給一串數字和視窗大小 k，求每個連續 k 個數裡的最大值，例如每 3 天的最高氣溫。直接對每個視窗找最大值要 O(n × k)。 用雙向佇列可以做到 O(n)，這叫單調佇列（monotonic queue）：
- 佇列裡存索引，對應的值從前端到尾端遞減
- 新元素
a[i]進來前，先從尾端移除所有不比它大的元素：它們比a[i]早離開視窗、又不比a[i]大，以後不可能再當最大值 - 前端的索引如果已經滑出視窗（
<= i - k），從前端移除 - 前端就是目前視窗的最大值
每個索引最多放入一次、移除一次，所以總共 O(n)。
單調佇列：每 3 個數的最大值
看 12（索引 2）進來時：尾端的索引 1（值 2）和索引 0（值 4）都比 12 小，全部移除，佇列只剩索引 2。之後 12 一直在前端，直到 i = 5 時索引 2 滑出視窗才被移除。印出的是 12 12 12 8 8 7。
想一想：佇列與雙向佇列
容量 5 的環狀佇列，目前 head = 3、tail = 1，而且佇列不是空的。佇列裡有幾個元素？
在 Python 裡用 list 當佇列，q.pop(0) 有什麼問題？
下面三段程式做的事情相同，會印出什麼？（Java 的 push 放在前端、offer 放在尾端、poll 從前端取出）
實作：傳球淘汰遊戲
7 個人編號 1～7 圍成一圈，從 1 號開始數，數到第 3 個人就淘汰，再從下一個人重新數，直到剩下一個人（這叫約瑟夫問題）。用佇列模擬：前面兩個人依序從前端取出、放回尾端，第三個人取出後淘汰並印出編號。請完成迴圈裡的 TODO。
重點整理
- 堆疊後進先出：push、pop、peek 都是 O(1)；用陣列加一個
size就能實作 - 內建堆疊：Python
list（append／pop）、C++stack（top讀值、pop不回傳）、JavaArrayDeque（本課用addLast／removeLast／peekLast，頂端在尾端） - 括號配對：左括號 push，右括號 pop 出最近的左括號比對；後序運算式：數字 push，運算子 pop 兩次（先出來的是右邊的運算元）
- 佇列先進先出；陣列實作用環狀佇列，
head、tail以% cap繞回開頭，另外記count分辨空和滿 - 內建佇列：Python
collections.deque（不要用list.pop(0)）、C++queue、JavaArrayDeque的offer／poll - 雙向佇列兩端都能 O(1) 進出；單調佇列用它在 O(n) 內求出每個滑動視窗的最大值
下一課：鏈結串列。堆疊和佇列也可以不用陣列，而用一個個以指標相連的節點來實作，插入和刪除不必搬動其他元素。