Learning Objectives
- 分辨抽象資料型別（ADT）和它的實作：ADT 只規定有哪些操作、結果是什麼，不規定資料怎麼存
- 用陣列和鏈結節點各實作一次堆疊，說明兩者對外的行為相同、內部的記憶體不同
- 對同一個集合 ADT 的兩種實作（無序陣列、有序陣列），數出查詢與加入各要幾步
- 說明什麼是不變條件（invariant），以及為什麼要用介面保護它
資料要放在哪裡、怎麼放
寫程式時，資料總要有個地方放：通訊錄裡的聯絡人、瀏覽器的上一頁紀錄、排隊等候列印的檔案。 資料結構（data structure）研究的就是兩件事：資料在記憶體裡怎麼擺，以及每一種操作（加入、刪除、查詢）怎麼做、要做幾步。
同樣是「存一堆數字」，擺法不同，成本就不同：
- 排成一整排連續的格子（陣列），想看第 500 個可以直接跳過去，但要在最前面插入一個，後面全部都得往後挪
- 每個數字各自放在一個小盒子裡、盒子之間用指標串起來（鏈結串列），插入只要改兩個指標，但想看第 500 個只能從頭數過去
沒有哪一種擺法在所有操作上都最快。這一軌的 18 課會一個一個把常見的資料結構親手做出來：看它在記憶體裡長什麼樣、每個操作改了哪裡、怎麼維持結構的規則。 演算法軌著重「怎麼用、多快」，這一軌著重「怎麼做出來」，兩條軌道可以分開學。
這一課先建立一個觀念：對外承諾的行為和內部的做法是兩回事。
每個範例都有 Python、C++、Java 三種寫法，可以用動畫上方的按鈕切換；三種寫法的輸出完全相同。
抽象資料型別：只說能做什麼
抽象資料型別（abstract data type，ADT）是一份「規格」：列出有哪些操作、每個操作的結果是什麼，不說資料怎麼存。 以堆疊（stack）為例，它的 ADT 是：
| 操作 | 結果 |
|---|---|
push(x) |
把 x 放到最上面 |
pop() |
拿走並回傳最上面的元素（也就是最後一個放進去、還沒被拿走的） |
peek() |
回傳最上面的元素，但不拿走 |
size |
目前有幾個元素 |
這份規格沒有提到陣列、指標或記憶體。只要行為符合規格，用什麼方法存都可以，那些方法叫做實作（implementation）。 用的人只需要知道規格，這份規格也叫做介面（interface）。
在程式裡，介面可以明白寫出來：
interface Stack { // Java：只列出方法，沒有內容
void push(int x);
int pop();
int peek();
}
struct Stack { // C++：純虛擬函數（= 0）表示「子類別一定要實作」
virtual void push(int x) = 0;
virtual int pop() = 0;
virtual int peek() = 0;
virtual ~Stack() {}
};
Python 通常不寫出介面，而是約定「有 push、pop、peek 這幾個方法就能當堆疊用」；需要時可以用 abc 模組寫抽象類別。
接下來用兩種完全不同的方法實作同一個堆疊 ADT，再用同一段主程式去測試。
堆疊的第一種實作：陣列
物件裡有一個長度 4 的陣列 data 和一個整數 size。push 寫進 data[size] 再把 size 加 1；pop 先把 size 減 1 再讀 data[size]。注意 pop 之後舊的值還留在格子裡，只是落在 size 之外，已經不算堆疊的元素；下一次 push 會蓋掉它。
不變條件：每個操作前後都要成立的規則
陣列版堆疊之所以正確，靠的是一條規則：
data[0] 到 data[size - 1] 就是堆疊裡的元素，由底到頂排列；data[size - 1] 是頂端。
這種「每個操作開始前成立，操作結束後也一定成立」的規則叫做不變條件（invariant）。 寫每個操作時，你可以假設它一開始成立，只要負責在結束時讓它仍然成立：
- push 寫進
data[size]再把 size 加 1：新元素剛好接在原本的頂端上面，規則仍然成立 - pop 把 size 減 1：原本的頂端被排除在範圍外，下面那個成為新頂端，規則仍然成立
data[size] 以後的格子放什麼都無所謂，因為規則根本不看它們。這也解釋了為什麼 pop 不需要把格子清成 0。
這一軌的每個資料結構都有自己的不變條件：堆積的「父節點不大於子節點」、二元搜尋樹的「左小右大」、AVL 樹的「左右高度差不超過 1」。 理解一個資料結構，最重要的就是先說出它的不變條件。
堆疊的第二種實作：鏈結節點
這一次沒有陣列。每個元素放在一個節點（node）裡，節點的 next 指向它下面的那個元素；物件只記得最上面那個節點 head。push 建立新節點、讓它的 next 指向原本的頂端，再把 head 改成新節點；pop 把 head 移到下一個節點。主程式和上一個範例一模一樣，輸出也完全相同：用的人分不出這是哪一種實作。C++ 版的 pop 用 delete 歸還節點的記憶體，Python 和 Java 由垃圾回收自動處理。
兩種實作的比較
兩種堆疊對外完全相同，差別在內部：
| 陣列版 | 鏈結版 | |
|---|---|---|
| push、pop、peek 的步數 | 各 1～2 步，O(1) | 各 1～3 步，O(1) |
| 記憶體 | 一開始就配置整個陣列，沒用到的格子也占著 | 有幾個元素就有幾個節點，但每個節點多存一個 next 指標 |
| 元素在記憶體裡 | 連續排在一起 | 分散在各處，靠指標串起來 |
| 放滿了 | 容量固定，要換一個更大的陣列（第 03 課） | 沒有容量上限，記憶體夠就能一直 push |
| 不變條件 | data[0..size-1] 是由底到頂的元素 |
從 head 沿著 next 走到空指標，就是由頂到底的元素 |
注意本課的陣列版沒有檢查「滿了」：容量 4 的堆疊 push 第 5 個時，Python 與 Java 會丟出索引超出範圍的例外，C++ 則會寫到陣列外面，結果無法預期（未定義行為）。 真正的實作要嘛檢查並回報錯誤，要嘛自動換成更大的陣列，第 03 課會做後者。
選哪一種，要看程式最常做什麼操作、元素數量能不能事先估計、記憶體夠不夠。這就是資料結構這門課反覆在做的事：列出每個操作的成本，再依需求選擇。
想一想：ADT 與實作
下列哪一項屬於堆疊 ADT 的規格，而不是某一種實作的細節？
這段程式會印出什麼？（Python 的串列 append／pop() 就是堆疊的 push／pop）
st = []
for x in [4, 1, 7]:
st.append(x)
a = st.pop()
st.append(a * 2)
st.append(2)
print(st.pop(), st.pop(), len(st))
本課的陣列版堆疊容量是 4。如果連續 push 5 次，第 5 次會發生什麼事？
第二個例子：集合 ADT
集合（set）的 ADT：存放一群不重複的值，支援
| 操作 | 結果 |
|---|---|
contains(x) |
x 在不在集合裡 |
add(x) |
加入 x；已經在裡面就什麼都不做 |
remove(x) |
移除 x；不在裡面就什麼都不做 |
規格裡沒有順序：集合 {3, 7} 和 {7, 3} 是同一個集合。用陣列實作時，有兩種直覺的做法：
- 無序陣列：加入時直接放在最後面。查詢只能從頭一個一個比。
- 有序陣列：一直保持由小到大。查詢可以用二分搜尋，每比一次排除一半（演算法軌第 04 課）；但加入時要把比 x 大的元素往右挪，空出位置。
下面用同一組 10 個數，比較兩種做法查詢要比幾次。
同一組數，兩種擺法的查詢次數
找 61：無序陣列要一路比到第 6 格；有序陣列第一次比中間的 33，就知道左半邊不用看了，3 次就找到。找 90（不在集合裡）：無序陣列要把 10 個全部比完才能確定沒有，有序陣列只要 4 次。元素越多，差距越大：100 萬個元素時，前者最多 100 萬次，後者最多 20 次。
有序陣列的代價：加入要挪位置
查詢變快不是免費的。有序陣列的不變條件是
data[0..size-1] 由小到大，而且沒有重複。
add(x) 必須維持這條規則：先用 contains 確認 x 不在裡面，再從最後一個元素往前看，比 x 大的就往右挪一格，挪到不能再挪時，空出來的位置就是 x 的位置。
最壞情況（x 比所有元素都小）要挪 n 個元素。
下面的範例依序加入 30、10、50、20、10（第二個 10 重複，不會加入），之後繞過 add、直接改陣列，看看不變條件被破壞會怎樣。
維持不變條件，以及破壞它的後果
加入 10 時，30 往右挪一格；加入 20 時，50 和 30 各挪一格。第二次加入 10，contains 先找到它，直接結束。最後主程式把 data[0] 改成 60：陣列變成 60、20、30、50，不再由小到大。60 明明在陣列裡，二分搜尋卻一路往右找，回答「沒有」。程式沒有報錯，只是給出錯的答案。
封裝：只能透過介面修改
剛才的錯誤不是 contains 寫錯，而是有人繞過介面直接改了內部的陣列。只要所有修改都經過 add、remove，不變條件就由這幾個方法負責維持；
一旦外面的程式可以隨意改 data，就沒有人能保證規則還成立。
所以實作通常把內部資料藏起來，這叫封裝（encapsulation）：
| 語言 | 寫法 |
|---|---|
| Java | 欄位宣告成 private int[] data;，類別外面存取會編譯錯誤 |
| C++ | 放在 private: 底下（class 預設就是 private） |
| Python | 沒有強制的 private，慣例是名稱前加底線 self._data，表示「這是內部細節，請不要直接用」 |
本課的範例為了讓動畫看得到內部，把欄位都留成公開的；之後的課也一樣。寫正式的程式時，記得把它們藏起來。
兩種集合實作的成本整理如下（n 是元素個數）：
| 操作 | 無序陣列 | 有序陣列 |
|---|---|---|
contains(x) |
O(n)：一個一個比 | O(log n)：二分搜尋 |
add(x) |
O(n)：先確認不重複，再放到最後 | O(n)：二分搜尋確認不重複，但要挪動元素 |
remove(x) |
O(n)：找到後把最後一個搬過來補洞（下面的實作題） | O(n)：右邊的元素要往左補 |
| 依序列出全部元素 | 要另外排序 | 本來就排好了 |
如果查詢遠比加入多（例如字典），有序陣列比較划算；加入和刪除都很頻繁時，兩者都不理想，第 08 課的雜湊表和第 10～12 課的平衡樹會做得更好。
想一想：成本與不變條件
這段程式模擬本課的兩種查詢，會印出什麼？
def find_unsorted(a, x):
steps = 0
for v in a:
steps += 1
if v == x:
break
return steps
def find_sorted(b, x):
lo, hi, steps = 0, len(b) - 1, 0
while lo <= hi:
mid = (lo + hi) // 2
steps += 1
if b[mid] == x:
break
if b[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return steps
print(find_unsorted([5, 3, 9, 1], 1), find_sorted([1, 3, 5, 9], 1))
有序陣列集合目前是 [10, 20, 30, 50]，呼叫 add(5) 時要把幾個元素往右挪？
關於不變條件（invariant），下列敘述何者正確？
實作：無序集合的 remove
無序陣列實作的集合，規格沒有要求順序。所以刪除時不必把右邊的元素一個一個往左挪：把最後一個元素搬到被刪掉的位置補洞，再把 size 減 1，就維持了不變條件，只要 O(1) 步（找到 x 的那一段仍是 O(n)）。請完成 remove；x 不在集合裡時什麼都不做。預期輸出在右邊，可以切換成你熟悉的語言。
重點整理
- 抽象資料型別（ADT）規定有哪些操作、結果是什麼；實作決定資料怎麼存、操作怎麼做。用的人只需要介面
- 同一個堆疊 ADT 可以用陣列（
data＋size）或鏈結節點（head＋next）實作，對外的輸出完全相同，記憶體的樣子與限制不同 - 同一個集合 ADT，無序陣列查詢 O(n)、有序陣列查詢 O(log n)，但有序陣列加入要挪元素；沒有一種實作在所有操作上都最好
- 不變條件是每個操作前後都成立的規則；每個操作只要負責「開始時成立 → 結束時仍成立」
- 封裝讓外面的程式只能透過介面修改資料，不變條件才保得住
- 集合的規格沒有順序，所以無序陣列的刪除可以「拿最後一個補洞」
下一課：陣列與記憶體。這一課反覆用到「陣列可以直接跳到第 i 格」，下一課就來看陣列在記憶體裡到底怎麼排、位址怎麼算。