本資料夾裡已有 singly_linked_list.cpp、stack_array.cpp、queue_array.cpp、deque_array.cpp 等可編譯實作，README 也列了操作清單。缺的是「為什麼是這兩種順序、複雜度怎麼來、用錯會怎樣」。圖的 BFS/DFS、回溯、運算式括號，都只是這兩個抽象資料型別。

相關教材：Recursion_Teaching_Materials.md（呼叫堆疊）、Graph_Algorithms_Complete_Teaching_Materials.tex（BFS 用佇列、DFS 用堆疊）、Heap_Priority_Queue_Teaching_Materials.md（優先佇列不是這裡的 FIFO 佇列）。

目錄

  1. 抽象資料型別與實作分開
  2. 堆疊
  3. 佇列
  4. 雙端佇列
  5. 鏈結串列
  6. 環形緩衝
  7. 怎麼選
  8. 常見陷阱
  9. 練習題

1. 抽象資料型別與實作分開

堆疊規定的是操作的效果，不是記憶體長相：

操作 效果
push(x) 放進一個元素
pop() 移除並回傳最後放進的那個
top() 只看最後放進的，不移除

用陣列或用串列實作，只要效果相同，演算法就成立。複雜度要另外看實作。下面若沒有特別聲明，目標都是每次操作攤還或最壞 (O(1))。

空結構上 pop 或 top 是契約錯誤。回傳一個哨兵值會和「堆疊裡真的存了這個值」分不清，所以介面應以例外或 optional 表示失敗，而不是回傳 0。

2. 堆疊

後進先出。呼叫堆疊就是這個：函式進入時 push 一個框，返回時 pop。遞迴太深會堆疊溢位，因為框的數量是線性的，不是因為堆疊這個資料結構突然變慢。

括號配對。 掃描字串，左括號 push，右括號必須和堆疊頂端的種類配對，配對就 pop。掃完堆疊要是空的。

([])：( 入、[ 入、] 與 [ 配對、) 與 ( 配對，空。合法。

([)]：] 出來時頂端是 [？字元是 ( 還在更下面，頂端是 [，] 對不上 (。不合法。這個字串的左右數量其實一樣，所以「只數個數」不夠，必須有堆疊。

DFS 的顯式堆疊用來取代遞迴，避免深圖把呼叫堆疊撐爆。走訪順序和遞迴版相同，前提是鄰居的推進順序也相同。

陣列實作：尾端當頂。push 在尾端插入，動態陣列的單次可能是線性，攤還 (O(1))（見攤還教材）。若容量固定，滿了就是溢位，不是攤還能救的。

3. 佇列

先進先出。BFS 用它：先發現的頂點先擴張，所以距離才會一層一層增加。若改用堆疊，走訪變成 DFS，最短路徑的性質消失。

陣列若在前端刪除，每次 pop 要把後面的元素往前挪，是 (O(n))。這是教學實作最常見的「功能對、複雜度錯」。修法有兩個：

  • 鏈結串列：頭刪、尾插，都是 (O(1))。要同時留頭尾指標。
  • 環形緩衝：頭尾兩個索引在固定陣列裡向前模容量，見第 6 節。

不要用 std::vector 的 erase(begin()) 當佇列。標準函式庫的 std::queue 預設底層是 deque，兩端都是 (O(1))。

4. 雙端佇列

兩端都可以進、都可以出。滑動視窗的單調佇列會在尾端插入、在兩端刪除。普通佇列做不到尾端刪除，堆疊做不到前端操作。

實作仍是環形緩衝或鏈結。四個操作都應是 (O(1))。若某一端是 (O(n))，單調佇列的總時間就不再是線性。

優先佇列不是雙端佇列。優先佇列依鍵值出列，不是依「哪一端」。名稱相近，介面不同。

5. 鏈結串列

節點是「值 + 下一節的指標」。位置已知時，插入或刪除該節點旁邊是 (O(1))，因為只改指標，不必搬移後段元素。代價是：

  • 沒有 (O(1)) 的索引。第 (i) 個要走 (i) 步。
  • 額外一個指標的記憶體，而且節點在堆積上散落，快取比陣列差。
  • 單向串列刪除「某個值」仍要先走到它，時間 (O(n))。指標指著節點時才能 (O(1)) 摘掉。

反轉單向串列。 三個指標 prev、curr、next。每個節點的 next 改指向 prev，然後三個一起前進。走完 prev 就是新的頭。漏掉先保存 next，鏈就斷了，後面的節點再也走不到。

雙向串列多一個 prev，可以往回走，刪除已知節點時不必從頭找前一個。環形串列的尾指向頭，走訪必須用「回到起點」當停止條件，不能等空指標。

哨兵節點（頭尾各放一個不含資料的節點）可以讓插入刪除少掉「是不是空串列」的分支。多兩個節點，換邊界案例變少。

本資料夾的 singly_linked_list.cpp、doubly_linked_list.cpp、circular_linked_list.cpp 是這些形狀的參考實作。讀的時候對照：哪幾行是 (O(1))，哪幾行其實先做了 (O(n)) 的搜尋。

6. 環形緩衝

容量 (C) 的陣列，head 是下一個要讀的位置，tail 是下一個要寫的位置。

push: 若已滿則失敗；a[tail] = x；tail = (tail+1) % C
pop:  若已空則失敗；x = a[head]；head = (head+1) % C

空與滿不能都用 head==tail 表示。兩種常見契約：

  • 多留一格：(tail+1) % C == head 表示滿，head==tail 表示空。可用容量是 (C-1)。
  • 另外記一個 size。head==tail 時用 size 分辨。可用容量是 (C)。

只寫 head==tail 又同時代表空和滿，會在最後一格時把有資料的佇列看成空的。

7. 怎麼選

需求 結構
後進先出、括號、回溯、DFS 堆疊
先進先出、BFS、工作佇列 佇列
兩端都要 (O(1)) 雙端佇列
已知節點、頻繁插刪、不需要索引 鏈結串列
需要索引、元素移動少 動態陣列
固定容量的生產消費 環形緩衝
每次取最小 堆積，不是佇列

8. 常見陷阱

  • 佇列用陣列頭刪。 功能對，總時間變二次。
  • 環形緩衝的空滿不分。 見第 6 節。
  • 反轉時先改 next 再保存。 串列斷裂。
  • 雙向串列只改一邊的指標。 往回走會指到已刪除的節點。
  • 把遞迴深度當成堆疊操作的複雜度。 push 仍是 (O(1))，框的數量才是問題。
  • BFS 誤用堆疊。 得到的是某種 DFS，層數不再是最短距離。

9. 練習題

  1. 用堆疊判斷 {[()]} 與 {[(])}。哪一個失敗，失敗在哪一個字元？
  2. 佇列依序 push 1、2、3，然後兩次 pop，再 push 4。第二次 pop 得到什麼？
  3. 環形緩衝容量 3、採用「多留一格」。最多能放幾個元素？head==tail 是空還是滿？
  4. 單向串列 1→2→3 反轉時，在改寫節點 2 的 next 之前必須先記住誰？
  5. 為什麼 BFS 的佇列若退化成每次 (O(n)) 的頭刪，整趟走訪會變成 (O(n^2))？

參考答案

  1. {[()]} 全部配對，結束時空堆疊，合法。{[(])} 在字元 ] 失敗：當時頂端是 (，不是 [。
  2. 第一次 pop 是 1，第二次是 2。4 還在佇列裡，尚未被 pop。
  3. 最多 2 個。head==tail 是空；滿是 (tail+1)%3==head。
  4. 節點 3。否則 2.next 被改指向 1 之後，再也沒有指標指向 3。
  5. 每個頂點進出佇列一次。若每次離隊都把陣列裡剩餘的頂點搬移一次，第 (i) 次搬移 (O(n-i))，總和是平方。環形緩衝或鏈結串列讓每次離隊是常數，整趟才是 (O(n+m))。

小結

堆疊後進先出，佇列先進先出。演算法要的是這個順序；陣列、鏈結或環形緩衝只是讓操作變成 (O(1)) 的手段。頭刪的陣列佇列、分不清空滿的環形緩衝、反轉時弄斷的 next，都是功能看起來還在、複雜度或正確性已經壞掉的寫法。優先佇列與這裡的佇列不是同一個介面。