第 2 章：核心概念
第 2 章：核心概念
1. 堆疊輸出順序
輸入：A → B → C
操作：push A，push B，pop B，push C，pop C，pop A
輸出：B，C，A
每次 pop 必定取走「尚未取出而且最後放入」的元素。遇到可否輸出的題目，逐步模擬，不要憑直覺。
2. 雜湊與線性探查
雜湊位置 → 被佔用？→ 檢查下一格 → 必要時繞回開頭
雜湊函數只決定第一個位置，不一定是最後儲存位置。先計算 hash，再按碰撞規則逐格檢查。
3. 樹、圖與生成樹
| 物件 | 是否連通 | 有沒有環 | 邊數規則 |
|---|---|---|---|
| Tree（樹） | 有 | 沒有 | E = V − 1 |
| Spanning tree（生成樹） | 連通原圖所有頂點 | 沒有 | 剛好 V − 1 條邊 |
| Euler graph（歐拉圖） | 有（忽略孤立點） | 可以有 | 每個頂點度數均為偶數 |
4. 最短路與最小生成樹
| 題目問甚麼 | 應選工具 |
|---|---|
| 由一個起點到各點的最短距離 | Dijkstra，前提是邊權非負 |
| 連通全部頂點的最小總權重 | Kruskal 或 Prim |
最短路樹與最小生成樹回答的是不同問題，不能互換。
5. 字串與樹狀結構
| 結構 | 核心想法 |
|---|---|
| Trie（前綴樹） | 多個字串共享前綴，節省結構 |
| KMP prefix array | 記錄可重用的前後綴，避免模式字串完全重頭比對 |
| Segment tree（線段樹） | 儲存區間資訊，快速回答區間查詢 |
每題先畫一個小例子，再選答案。
