Learning Objectives
- 說明資料結構是「資料的排列方式＋可以對它做的操作」
- 比較陣列與鏈結串列：讀取第 k 個元素、在中間插入各要幾步
- 說明堆疊（後進先出）與佇列（先進先出）的差別，並各舉一個生活中的例子
- 認識樹、二元搜尋樹與圖，知道它們適合表示哪一類資料
- 依照最常做的操作，為問題挑選合適的資料結構
資料怎麼放，決定了找得多快
一櫃排好的書和一箱亂丟的書，數量一樣，但要找某一本，前者只要看書背的編號，後者可能要整箱翻過。 電腦裡也一樣：同一批資料用不同方式排列，有些操作會變得很快，有些會變得很慢。
資料結構（data structure）就是「資料的排列方式」加上「可以對它做哪些操作」。這一課要回答的問題是： 常見的資料結構有哪些？各自擅長什麼、不擅長什麼？
| 資料結構 | 一句話描述 | 生活中的例子 |
|---|---|---|
| 陣列（array） | 一排連續、編了號的格子 | 電影院一排座位 |
| 鏈結串列（linked list） | 每個元素記得下一個在哪裡 | 尋寶遊戲的線索紙條 |
| 堆疊（stack） | 只能從最上面放、從最上面拿 | 一疊盤子 |
| 佇列（queue） | 從後面排進來，從前面離開 | 排隊結帳 |
| 樹（tree） | 有上下層級的分支 | 資料夾、族譜 |
| 圖（graph） | 點和點之間任意連線 | 捷運路線圖、社群好友 |
上一課學到用 Big-O 數步驟，這一課會用它來比較每種結構的操作。
陣列：一排連續的格子
陣列把元素一個緊接一個放在記憶體裡，每一格大小相同，從 0 開始編號，這個編號叫索引（index）。
因為格子是連續的，第 i 格的位置可以直接算出來：
第 i 格的位址 = 第 0 格的位址 + i × 每一格的大小
所以不管陣列有多長，讀第 0 格和讀第 99,999 格都只要一步，是 O(1)。
代價是：要在中間插入一個元素，後面的元素全部要往後挪一格，騰出空位；刪除中間的元素也要把後面的往前補。 最壞情況要挪 n 個，是 O(n)。Python 的串列（list）在記憶體裡就是用陣列的方式存放。
在陣列中間插入：後面的人都要挪
一排 5 個座位，前 4 個坐了 A、C、D、E，要把 B 插到索引 1。為了不蓋掉別人，要從最後面開始，一格一格往右挪。看上方格子的變化與 moves 最後是多少。最後一行用索引直接讀 seats[3]，一步就拿到。
鏈結串列：每個元素記得下一個在哪
鏈結串列的每個元素叫做節點（node），節點裡放兩樣東西：自己的值，以及指向下一個節點的指標（在 Python 裡就是一個參考）。
節點不必在記憶體裡相鄰，散在各處都可以，靠指標串成一條鏈；最後一個節點的指標是空的（None）。
head → [A | •] → [B | •] → [C | •] → [D | None]
它的優缺點剛好和陣列相反：
| 操作 | 陣列 | 鏈結串列 |
|---|---|---|
| 讀第 k 個元素 | O(1)：用索引直接算位址 | O(k)：只能從 head 一個一個走過去 |
| 在已知的位置插入或刪除 | O(n)：後面的都要挪 | O(1)：只要改兩個指標 |
下面的範例先建立 A → C → D，把 B 插在 A 後面，再從頭走到第 3 個節點。
鏈結串列：插入只改兩個箭頭
上方畫出從 head 開始的鏈。插入 B 時，先讓 B 指向 C，再讓 A 改指向 B，其他節點完全不用動。最後的迴圈用 cur 一個一個往後走，走兩步才到第 3 個節點。
堆疊與佇列：限制存取的位置
有些資料結構故意只允許從固定的一端存取，反而讓程式更簡單，而且放入、取出都只要 O(1)：
| 結構 | 規則 | 例子 |
|---|---|---|
| 堆疊（stack） | 後進先出（LIFO，last in first out）：最後放進去的最先拿出來 | 一疊盤子、文書軟體的「復原」、瀏覽器的「上一頁」 |
| 佇列（queue） | 先進先出（FIFO，first in first out）：最早排進來的最先離開 | 排隊結帳、印表機的列印工作、客服來電排隊 |
堆疊的放入叫 push、取出叫 pop；佇列的放入叫 enqueue、取出叫 dequeue。
在 Python 裡，串列的 append() 與 pop() 就能當堆疊用。佇列可以用 append() 加 pop(0) 示範，
不過 pop(0) 會讓後面的元素全部往前挪（就是剛才陣列的 O(n)），實際寫程式時改用 collections.deque，兩端進出都是 O(1)。
堆疊做復原，佇列排列印
上半段：你依序做了「打字」「加粗」「插入圖片」，按兩次復原，先取消的是最後做的動作。下半段：三份文件依序送去列印，先送的先印。比較兩個 pop 拿走的分別是哪一端。
想一想：陣列、串列、堆疊、佇列
瀏覽器的「上一頁」按鈕要回到最近看過的頁面，用哪一種資料結構記錄最合適？
下面的程式把串列當堆疊用，會印出什麼？
s = []
s.append(1)
s.append(2)
s.append(3)
s.pop()
s.append(4)
print(s.pop(), s.pop())
下面的程式把串列當佇列用，會印出什麼？
q = []
for x in ["A", "B", "C"]:
q.append(x)
first = q.pop(0)
q.append("D")
print(first, q)
樹：有層級的分支
電腦裡的資料夾就是一棵樹（tree）：最上面的磁碟是根（root），裡面的資料夾是它的子節點（child）， 沒有再往下分的檔案叫葉節點（leaf）。每個節點只有一個上層（父節點），根沒有父節點。
C:
/ \
文件 相片
/ \ \
報告 講義 旅行
每個節點最多只有兩個子節點的樹叫二元樹。如果再加上一條規則：每個節點左邊的值都比它小、右邊的都比它大， 就是二元搜尋樹（binary search tree，BST）。找一個值時，從根開始比較，比較小就往左、比較大就往右，每比一次就往下一層。
樹長得「矮胖」時，n 個節點只有大約 log₂n 層，搜尋很快；可是如果資料剛好依大小順序插入，每個新值都比前面的大， 只能一直往右掛，樹就退化成一條線，搜尋又變回 O(n)。下面的小工具可以親眼看到這兩種情況。
圖：點與點之間任意連線
樹的每個節點只能有一個上層，但很多關係不是這樣：捷運的一個站可以連到好幾個站，繞一圈還會回到原點； 你的朋友也有他自己的朋友，彼此交錯。這種「點和點之間任意連線」的結構叫做圖（graph）：
- 節點（node，或稱頂點）：站、人、網頁
- 邊（edge）：兩個節點之間的連線，例如兩站之間的軌道、兩個人是朋友
- 有向圖：邊有方向，例如網頁 A 連到網頁 B，不代表 B 也連到 A
- 加權圖：邊上有數字，例如兩站之間的距離或車程
程式裡常用鄰接串列（adjacency list）存一張圖：每個節點記下它的鄰居。
friends = {
"小安": ["小明", "小華"],
"小明": ["小安", "小芳"],
"小華": ["小安", "小芳"],
"小芳": ["小明", "小華"],
}
print(friends["小安"]) # 小安的朋友：['小明', '小華']
導航軟體找最短路線、社群網站推薦「你可能認識的人」、搜尋引擎分析網頁之間的連結，背後都是圖的演算法。
怎麼選資料結構？先想清楚最常做的操作：
| 最常做的事 | 適合的結構 |
|---|---|
| 依編號讀取第 k 個 | 陣列 |
| 常常在中間插入、刪除 | 鏈結串列 |
| 最後來的最先處理（復原、上一頁） | 堆疊 |
| 先來的先處理（排隊、工作排程） | 佇列 |
| 有上下層級，或要快速找出某個值 | 樹（二元搜尋樹） |
| 任意的連線關係（路線、社群） | 圖 |
想一想：選哪一種結構
一個程式最常做的事是「讀取第 k 筆成績」，k 每次都不一樣。用陣列還是鏈結串列比較快？
要在程式裡表示捷運路線（站與站之間的連接，有些路線會繞成一圈），最適合的資料結構是？
把 1、2、3、…、1000 依序插入一棵（不做平衡的）二元搜尋樹，再搜尋 1000，大約要比較幾次？
實作：用堆疊檢查括號有沒有成對
程式編輯器會幫你檢查括號有沒有配好，用的就是堆疊：讀到左括號就 push；讀到右括號時，堆疊最上面必須是對應的左括號，配上了就 pop 掉。全部讀完，堆疊要剛好是空的。請完成兩個 TODO，讓四個式子印出正確的 True 或 False。
重點整理
- 資料結構＝資料的排列方式＋可以做的操作；沒有一種結構每件事都最快，要看最常做的操作來選
- 陣列：連續的格子，用索引讀取 O(1)；在中間插入、刪除要挪動後面的元素，O(n)
- 鏈結串列：節點用指標串起來，已知位置的插入、刪除 O(1)；讀第 k 個要從頭走，O(k)
- 堆疊後進先出（復原、上一頁）；佇列先進先出（排隊、列印）；放入取出都是 O(1)
- 樹表示層級；二元搜尋樹左小右大，平衡時搜尋約 log₂n 次，退化成一條線時變成 n 次
- 圖由節點和邊組成，表示任意的連線關係，常用鄰接串列存放
下一課：排序與搜尋。會用到這一課的陣列，看資料排好之後，搜尋可以快多少。 想實作更多資料結構，可以接著上演算法軌（第 10～17 課）。