什麼是資料結構
資料結構是資料在記憶體中的組織方式，包含資料的集合、彼此之間的關係，以及可以對這些資料進行的操作。
資料結構很像「收納」。
記憶體就像收納空間，資料是被收納的物品，而資料結構就是收納的方式。
在有限的空間下，不同的收納方式，會影響我們找資料的速度、使用的空間大小，以及新增或移除資料的成本。
資料結構的選擇，本質上就是在「找得快」和「用得省」之間做取捨。
Array｜座位表式的管理
比喻情境
在公司剛成立、人數還不多的時候，人資最喜歡做的一件事就是「排座位表」。每個人都有固定座位，第 1 位、第 2 位、第 3 位清清楚楚。主管只要說：「幫我找第 15 位同事」，行政立刻知道要走到哪一排、哪一個位置。這種管理方式的優點非常明確：找人快。
因為位置是固定的，不用問、不用查關係，只看編號就好。但當問題來了，如果中間突然多了一位新人，或某個人離職，整排座位就要重排。不是不能改，只是改動成本很高。
Array 就像這樣的座位表：用「固定、連續的位置」，換取最快的存取速度。
圖解概念
- 存取：數據以連續方式存於記憶體中，可用索引計算位置 → 隨機存取 O(1)
- 新增：確保後方有空間 → 後方元素依次後移 → 插入新元素 (O(n))
- 新增一個空間，在位置 1 加入黃色，後面的球會向後移動
- 刪除：移除元素 → 後方元素依次前移 → 收尾 (O(n))
- 移除綠色的球後，藍色球會向前移動，並把多餘的空間移除
Linked List｜交接清單式的流程
比喻情境
有些公司不排座位表，而是用「工作交接清單」。每一位負責人只知道兩件事：
1. 我現在負責什麼
2. 下一棒是誰
事情要找誰，就從第一位開始，一個一個往下問。這樣找人不算快，但有一個很大的好處：流程很容易調整。如果中間要插入一個新角色，只要改交接對象就好；某個人離開，也只需要重新接上下一棒。
Linked List 就是這種概念：不追求快速定位，而是讓結構保持彈性。
圖解概念
- 每個資料都會有對應的指標，指標會指向下一個數據的記憶體位置（數據不一定會以連續的方式存在記憶體，可能會分散在不同的領域）
- 存取：只能依序從頭跟著指標存取（sequential access）O(n)
- 存取藍球，需從紅球開始
- 新增：只需要把新數據前後指標轉向即可 O(1)
- 將黃球加入並指向綠球，紅色指標改指黃球
- 刪除：只需要把指標轉向即可 O(1)
- 綠球可能還在記憶體中，但已變成無法存取的狀態，可不用特地移除
Stack｜主管桌上的待辦事項
比喻情境
想像主管桌上有一疊文件。新的事情來了，就直接放在最上面；要處理事情，也一定是從最上面那一份開始。為什麼？因為那通常是「剛剛才發生、最需要立刻回應的事」。舊的事情沒有不重要，只是要等最新的處理完，才輪得到。
Stack 就像這疊文件：你永遠只處理「最後進來的那一件」。
圖解概念
- 推入：只能加在最上面，將數據加到堆疊的操作稱為 Psuh
- 將黃球推入 stacks 中
- 彈出：只能從在最上面， 將數據移出到堆疊的操作稱為 Pop
- 將黃球彈出 stack
Queue｜客服或簽核流程
比喻情境
客服中心的電話不可能讓人插隊。誰先打進來，就先被服務；新來的，只能乖乖排在後面。這樣做也許不是最快，但最公平、最穩定，也最容易讓整個系統持續運作。
Queue 就是這樣的流程：順序比速度更重要。
圖解概念
- 輸入：只能加在最後端，將數據加到佇列的操作稱為 enqueue
- 將黃球加入佇列
- 輸出：只能從在最前端，將數據移出到佇列的操作稱為 dequeue
- 輸出時，只能存最前端的紅球先輸出
Hash Table｜用員工編號找人
比喻情境
如果公司已經有上百、上千人，還要一個一個翻名冊找人，效率一定很差。所以公司會給每個人一個員工編號。只要輸入編號，系統立刻知道這個人是誰、在哪個部門。你不需要知道他在第幾頁、排第幾個，只要 key 正確，就能直接命中。
Hash 解決的就是這件事：不用照順序，只求快速對應。
圖解概念
- Hash Table
- 數據為鍵值對（key-value pairs）
- Hash Function： 計算出雜湊值，再計算出索引（index）
- 會在記憶體先準備一定長度的空陣列
- 碰撞：
- 放入資料的過程中，可能會發生計算出相同索引的狀況，稱為碰撞Collision
- Bob 與 Amy 因為計算出雜湊值相同而發生碰撞
- 使用列表（ Linked List）接續在已存入的數據後面。這裡用鏈結法（chaining）
- 存取：將輸入值（key）使用雜湊函式計算出雜湊值，計算出索引，找到對應資料的位置
- 如果找 Amy 則會多一個線性搜尋的步驟
Heap｜老闆的優先事項清單
情境比喻
老闆每天收到一堆事情，但他其實只在乎一件事：「現在最重要的是什麼？」
他不會把事情全部排好順序，而是確保「最重要的那一件，隨時都在最前面」。處理完一件，再看看下一件最重要的是誰。
Heap 就像這個清單：不排序全部，只確保優先權正確。
圖解概念
- Heap
- 樹狀結構，最多有兩個子節點
- 順序規則，由上方開始加入，位處同階層時，由左方開始加入（灰色數字）
- 堆疊規則，父節點永遠小於子節點（最小二元堆積）
- 新增：
- 依照規則填到最下面階層的空位
- 將 5 加入到位置 7
- 不符合堆積規格，與父節點對調（bubble up）
- 將 6 與 5 互換
- 取值：
- 最上面為最小的數值
- 將最尾端的數值移到最上方
- 將位置 7 回補到位置 1
- 開始下沉(sink down)，與較小的一邊對調
- 6 比子節點 3 大，所以互換。6 還是比子節點 4 大，所以再互換
Binary Tree｜會自己長大的分類系統
比喻情境
當公司要管理越來越多資料時，與其每次新增就重新整理，不如先訂好分類規則。
例如：金額小的放左邊，大的放右邊；再在各自底下，繼續細分。
每一筆新資料進來，只要照著規則一路往下，自然就會找到屬於自己的位置。當你要找資料時，也只要走同樣的路，每走一層，就排除一半不可能。
Binary Search Tree 描述的正是這總結：一邊成長，一邊維持搜尋與插入的效率。
圖解概念
- Binary Tree
- 將數據從存到節點內，每個節點最多兩個子節點
- 所有節點的數值都會大於連結在其左邊的節點的數值
- 從根節點往左的最尾端，即為此二元樹的值最小的節點
- 所有節點的數值都會小於連結在其右邊的節點的數值
- 從根節點往右的最尾端，即為此二元樹的值最大的節點
- 新增：一路從根節點尋找應該追加的位置，直到最末端（小往左，大往右）
- 當加入 1 時，比 15 小往左，以此類推
- 當加入 4 時，其中比 3 大，所以往右，其他都是往左
- 刪除：
- 如果沒有子節點，直接移除即可
- 如果有子節點，移除節點後，從子樹狀圖找到最大節點，移到父樹狀結構
- 搜尋：按照規則小往左，大往右
