👋 歡迎來到 HL 主題 5：抽象數據結構 (ADS)！
這一章將帶領大家跨越簡單的變量和陣列，探索組織數據的高階結構與強大方法。別擔心，聽起來可能有點嚇人，但其實 抽象數據結構 (Abstract Data Structure, ADS) 只是一個規範數據應如何組織與存取的「藍圖」。
你可以把 ADS 想成程式開發工具箱裡的專用工具。如果你需要處理等待列表，就使用 Queue（佇列）；如果需要追蹤函式呼叫，就使用 Stack（堆疊）。理解這些結構，對於編寫高效且優雅的高階電腦科學程式碼至關重要。
主題 5 的重點學習目標
- 理解「抽象化 (Abstraction)」與「實作 (Implementation)」的區別。
- 掌握堆疊 (Stack, LIFO) 與佇列 (Queue, FIFO) 的行為及用途。
- 理解連結串列 (Linked List) 等動態結構的概念。
- 探索非線性結構，特別是二元搜尋樹 (Binary Search Trees, BSTs)。
1. 抽象化的概念
什麼是抽象數據結構 (ADS)？
ADS 定義了數據、數據之間的關係，以及可以在數據上執行的操作，但不會指定這些數據在記憶體中是如何儲存的。
這種區隔稱為抽象化 (Abstraction)。
比喻：遙控器
當你按下電視遙控器上的「音量加」按鈕時，你並不在意內部的電路、紅外線訊號或是電視內部的程式運作（這是實作）。你只在乎那個操作（「音量加」）能達到預期的效果（這是抽象化）。
同樣地，當我們使用 Stack ADS 時，我們只定義了操作（PUSH 和 POP）。我們不需要擔心該堆疊在內部是用固定的陣列實現的，還是用靈活的連結串列實現的。
抽象化 vs. 實作
- 抽象化 (Abstraction)： 邏輯視角。數據結構做什麼？（例如：Queue 按順序保存等待項目。）
- 實作 (Implementation)： 物理視角。數據結構是怎麼構建的？（例如：使用陣列，或是使用物件組成的連結串列。）
為什麼要這樣分？ 這能讓我們優先專注於問題定義。如果軟體工程師需要一個等待列表，他們直接取用 Queue ADS 藍圖即可。隨後，系統程式設計師再決定哪種構建方式最適合該電腦系統。
快速總結
ADS = 做什麼 (What)。
實作 = 怎麼做 (How)。
2. 堆疊 (Stacks)：後進先出 (LIFO)
定義與行為
堆疊 (Stack) 是一種線性 ADS，所有的添加和刪除操作都在同一端進行，稱為頂部 (Top)。
這導致了 LIFO (Last-In, First-Out，後進先出) 行為。最後放入堆疊的項目，永遠是第一個被取出的項目。
比喻：自助餐廳的托盤堆
想像自助餐廳的托盤架。你只能把新托盤加在最上面，也只能從最上面拿走托盤。最近放入的托盤，就是你最先取出的那一個。
堆疊的關鍵操作
- PUSH： 將項目放入堆疊頂部。
- POP： 移除並返回位於堆疊頂部的項目。
- PEEK (或 TOP)： 查看位於頂部的項目，但不移除它。
- isEmpty： 檢查堆疊是否為空。
你知道嗎？（現實應用）
堆疊是電腦管理程式運作的基礎。執行堆疊 (Run-Time Stack)（或稱呼叫堆疊）會追蹤函式的呼叫。當函式 A 呼叫函式 B 時，B 會被 PUSH 進堆疊。當 B 執行完畢時，它會被 POP 出來，程式便能精確回到 A 之前中斷的地方繼續執行。
常見錯誤： 不要搞混 PEEK 和 POP。POP 會改變堆疊內容；而 PEEK 只是讀取堆疊。
快速複習：堆疊記憶法
LIFO：後進的 (Last In)，先出 (First Out)。
3. 佇列 (Queues)：先進先出 (FIFO)
定義與行為
佇列 (Queue) 是一種線性 ADS，插入操作發生在一端（稱為尾部/後端, Rear/Tail），而刪除操作發生在另一端（稱為頭部/前端, Front/Head）。
這導致了 FIFO (First-In, First-Out，先進先出) 行為。第一個進入佇列的項目，就是第一個離開的項目。
比喻：排隊
想像超級市場結帳的隊伍或音樂會購票的人龍。先來的人先得到服務。新來的人總是加入到隊伍的最後面（尾部）。
佇列的關鍵操作
- ENQUEUE： 將項目加入佇列尾部 (Tail)。
- DEQUEUE： 從佇列頭部 (Head) 移除並返回項目。
- PEEK (或 FRONT)： 查看頭部的項目而不移除。
- isEmpty： 檢查佇列是否為空。
現實應用：列印工作
如果你傳送三個文件到共享印表機，它們不會同時列印。它們會在列印佇列中等待。第一個發送的文件 (FIFO) 會最先被列印。
實作筆記 (HL 重點)
雖然佇列可以用簡單的陣列實現，但這通常效率很低，因為 DEQUEUE 操作需要將剩餘的每個項目向前移動。為了更高的效率，佇列通常使用環形陣列 (Circular Array) 或 連結串列 (Linked List) 來實現。
4. 連結串列 (Linked Lists)：動態儲存
陣列的缺點
陣列（靜態數據結構）有兩個主要限制：建立時大小已固定，且在中間插入或刪除項目很慢，因為需要移動大量的後續元素。
定義與結構
連結串列 (Linked List) 是一種動態 ADS，元素在記憶體中不一定是連續儲存的。每個元素稱為一個節點 (Node)，包含兩個部分：
- 數據 (Data)： 本身的值。
- 指標 (Pointer)： 指向下一個節點的連結。
串列總是從一個稱為頭部 (Head) 的特殊指標開始，指向第一個節點。當某個節點的指標為 Null 時，代表串列結束。
比喻：尋寶遊戲
想像一個尋寶遊戲，每個線索（節點）都會告訴你「下一個」線索的位置（指標）。你只需要知道第一個線索（Head）在哪裡，就能找到所有後續線索，即使這些線索在物理上分散在很廣的範圍（非連續記憶體）。
連結串列的主要優點
- 動態大小： 隨需增加或減少，有效利用記憶體。
- 高效插入/刪除： 要插入或刪除節點，只需修改相鄰節點的指標即可，不需要移動大量數據！
連結串列的類型 (課程範圍)
- 單向連結串列 (Singly Linked List)： 每個節點只指向下一個節點。（單行道）。
- 雙向連結串列 (Doubly Linked List)： 每個節點有兩個指標：一個指向下一個節點，另一個指向前一個節點。（雙行道，使反向遍歷成為可能，且刪除操作更簡單）。
快速總結：效率
連結串列犧牲了陣列擅長的快速順序存取，換取了在串列中間進行快速插入與刪除的優勢。
5. 樹 (Trees)：非線性結構
定義與術語
樹 (Tree) 是一種用於呈現層次結構數據的非線性 ADS，由節點 (Nodes) 與連接它們的邊 (Edges) 組成。
關鍵術語：
- 根節點 (Root)： 樹的最頂端節點。（它沒有父節點。）
- 子節點 (Child)： 從根節點往下連接的節點。
- 父節點 (Parent)： 子節點的上一層節點。
- 葉節點 (Leaf)： 沒有子節點的節點。（處於分支的末端。）
- 子樹 (Subtree)： 樹的一部分，其本身也是一棵樹。
二元搜尋樹 (Binary Search Trees, BSTs)
二元樹 (Binary Tree) 是一種樹，其中每個節點最多只有兩個子節點（左與右）。
二元搜尋樹 (BST) 強制執行一項組織規則，以實現高效的搜尋、插入與刪除：
- 左子樹中的所有值必須小於父節點的值。
- 右子樹中的所有值必須大於父節點的值。
為什麼 BST 很有用？
如果你想在 BST 中尋找數字 15，從根節點開始。如果根節點是 20，你立刻知道只需要往左子樹找，這將搜尋範圍減少了一半。這種速度對於大規模數據處理至關重要！
步驟說明：插入節點到 BST
要插入一個值（例如 55）：
- 從根節點開始。
- 55 小於根嗎？往左走。55 大於根嗎？往右走。
- 重複步驟 2，沿著樹往下找，直到遇到一個 Null 指標。
- 將新節點 (55) 插入到那個空位。
樹的遍歷 (Traversal) 方法
遍歷是指將樹中每個節點恰好訪問一次的過程。根據根節點 (Root) 相對於左右子節點的訪問順序，有三種主要的遞迴方法。
遍歷記憶法：根節點 (Root, R) 的位置
我們總是先訪問左 (L) 再訪問右 (T)。區別在於根節點 (R) 的訪問時機。
1. 中序遍歷 (In-order, L R T)：
順序： 左子樹 -> 根節點 -> 右子樹
- 效果： 若對 BST 進行中序遍歷，結果會是由小到大的排序序列。這是 BST 最著名的特性。
2. 前序遍歷 (Pre-order, R L T)：
順序： 根節點 -> 左子樹 -> 右子樹
- 效果： 用於建立樹的副本或重建樹的結構。
3. 後序遍歷 (Post-order, L T R)：
順序： 左子樹 -> 右子樹 -> 根節點
- 效果： 主要用於刪除或處理樹木，確保在處理/刪除父節點之前，子節點已被處理/刪除完畢。
快速複習：ADS 概覽
Stack (堆疊)： LIFO (後進先出)。想想托盤堆。
Queue (佇列)： FIFO (先進先出)。想想排隊。
Linked List (連結串列)： 動態記憶體，透過指標實現靈活的插入/刪除。
BST (二元搜尋樹)： 層次結構 (Tree)，基於規則組織 (左 < 根 < 右) 以實現快速搜尋。