先問資料必須做什麼
別從"該用哪種結構？"出發。要從"我需要哪些操作快？"出發。按位置讀取？在某一端添加？按名字查找？每種結構天生就是某些操作快、某些操作慢。把結構匹配到你*最高頻*的那個操作上。
再問幾個問題也有幫助：大小是固定的，還是會增長？我在意元素到達的順序，還是只關心某個東西在不在？在這裡多想兩分鐘，能省下你日後把一個慢的 O(n) 迴圈改寫成快迴圈的功夫。把你的問題對照下面這張清單走一遍。
- 需要按索引讀寫（第 5 個元素）？-> 陣列（或 std::vector）。
- 需要後進先出（復原、呼叫堆疊、回溯）？-> 堆疊。
- 需要先進先出（公平排程、BFS）？-> 佇列。
- 需要按鍵快速查找/插入/刪除（名字 -> 值）？-> 雜湊表。
- 既要有序、又要快速查找？-> 樹（下文預告）。
代價速查表
整整一階的內容，濃縮成一張卡片。"平均"對雜湊表尤為關鍵——它最壞是 O(n)，但只要雜湊得當，你很少碰到。記住這張表的*形狀*，而非每個格子的精確值；形狀才是指引你選擇的東西。
structure access search insert delete ----------- ------- ------- -------- -------- array O(1) O(n) O(n)* O(n)* linked list O(n) O(n) O(1)** O(1)** stack O(1) top -- O(1) push O(1) pop queue O(1) ends -- O(1) enq O(1) deq hash table -- O(1) avg O(1) avg O(1) avg * array insert/delete is O(1) only at the very end ** linked list O(1) only once you HOLD a pointer to the spot
幾個真實的取捨
把這些問題套到真實任務上。"統計一本書裡每個單字出現的次數。"你需要查一個單字並給它的計數加一——按鍵快速查找——所以雜湊表（`std::unordered_map<std::string,int>`）勝出。
"按提交順序處理列印任務。"到達順序、從隊首服務——這是佇列。"實作復原。"最近的操作最先被回退——堆疊。"儲存 256 個固定像素值，會不斷按索引讀取。"純按索引存取——陣列。
那麼"一個總是在中間插入和刪除、從不按索引存取的清單"呢？這正是鏈結串列難得的用武之地——一旦握有指向那個位置的指標，修改就是 O(1)。
當線性結構不夠用：樹的預告
有一種組合是這四者都搞不定的：既保持元素有序、又能快速查找。雜湊表快但無序；有序陣列保持順序，但插入是 O(n)。答案是一種有分支、而非單一直線的結構——樹，尤其是二元搜尋樹，它能提供 O(log n) 的有序查找和插入。
(8)
/ \
(3) (10)
/ \ \
(1) (6) (14)
ordered + fast: each step halves the search -> O(log n)那是下一階的內容。眼下的收穫是一個習慣：動手寫程式碼前，先把你需要的操作一一點名，再挑出代價與之匹配的結構。結構是一個*決策*，而不是一個*預設值*。