歡迎來到資料結構的世界！
有沒有想過手機是如何記錄你的「復原」歷史，或者印表機是怎麼決定哪份文件先列印的嗎？答案就在資料結構 (Data Structures)！在這一章，我們不只是單純處理資料，更要探索如何運用巧妙的方法來組織和儲存這些資料，以便更有效地使用它們。這就像在整理衣物，你是要把衣服亂堆成一團，還是把它們整齊地分類放進抽屜呢？選擇正確的結構，找東西時效率絕對會快得多！
如果有些概念初看覺得抽象，請別擔心。我們會用大量的現實生活類比，幫助你輕鬆理解。讓我們開始吧！
1. 堆疊與佇列：排隊好夥伴
堆疊 (Stack - LIFO)
堆疊 (Stack) 是一種線性資料結構，遵循 LIFO 原則：後進先出 (Last-In, First-Out)。
類比：想像一疊自助餐廳的餐盤。最後放上去的那一個餐盤，一定是第一個被拿走的。你不可能在不弄亂的情況下直接抽取最底下的餐盤！
核心操作：
1. 推入 (Push)： 將項目加入到堆疊的最上方。
2. 彈出 (Pop)： 將項目從堆疊的最上方移除。
3. 查看 (Peek/Top)： 查看最上方的項目而不將其移除。
佇列 (Queue - FIFO)
佇列 (Queue) 遵循 FIFO 原則：先進先出 (First-In, First-Out)。
類比：買珍珠奶茶排隊。第一個加入隊伍的人一定最先獲得服務。既簡單又公平！
線性佇列 vs. 環狀佇列：
- 線性佇列 (Linear Queue)： 當項目被移除時，前端的空間就「浪費」了，除非你將所有人向前移動（這會很慢）。
- 環狀佇列 (Circular Queue)： 當到達陣列末端時，下一個項目會「繞回」到前端（如果有空間的話）。這就像旋轉木馬，座位不斷循環移動！
核心操作：
1. 入列 (Enqueue)： 將項目加入到佇列的後端 (rear)。
2. 出列 (Dequeue)： 將項目從佇列的前端 (front) 移除。
快速複習：記住 S-L (Stack-LIFO) 和 Q-F (Queue-FIFO)。堆疊用於復原操作；佇列則用於等待名單！
2. 線性鏈結串列 (Linear Linked Lists)
鏈結串列 (Linked List) 是由多個節點 (nodes) 組成的集合。每個節點包含兩個部分：
1. 資料 (Data)： 實際儲存的資訊。
2. 指標 (Pointer)： 指向串列中下一個節點的箭頭。
類比：尋寶遊戲。每個線索（節點）告訴你寶藏是什麼（資料），並給你一張指向下一個線索的地圖（指標）。當線索顯示「沒有更多位置了」（空指標 null pointer）時，遊戲結束。
操作：
- 搜尋 (Search)： 你必須從「頭部 (Head)」開始，逐一跟隨箭頭直到找到目標。你不能直接「跳」到中間！
- 插入 (Insert)： 若要新增節點，只需「中斷連結」並重新導向指標即可。這比移動整個陣列快得多！
- 刪除 (Delete)： 修改前一個節點的指標，使其「跳過」你想刪除的那個節點即可。
常見錯誤：如果你在串列的最開頭進行插入或刪除操作，卻忘了更新頭部 (Head) 指標！
重點總結：與長度固定的陣列相比，鏈結串列的大小具有高度彈性。
3. 二元樹與二元搜尋樹 (BST)
二元樹 (Binary Tree) 是一種階層式結構，每個節點最多擁有兩個子節點（左子節點和右子節點）。
二元搜尋樹 (Binary Search Tree, BST)
BST 是一種特殊的二元樹，遵循特定規則：
- 左子節點 < 父節點
- 右子節點 > 父節點
例子：如果根節點是 50，所有小於 50 的數字都在左側分支，所有大於 50 的數字都在右側。這使得搜尋變得極快，因為每走一步都能排除掉一半的樹！
樹的遍歷 (Tree Traversals)
我們如何「造訪」樹中的每一個節點？主要有三種方法：
1. 前序遍歷 (Pre-order)： 根 -> 左 -> 右（用於複製樹）。
2. 中序遍歷 (In-order)： 左 -> 根 -> 右（小撇步：對於 BST，這會以升序造訪節點！）。
3. 後序遍歷 (Post-order)： 左 -> 右 -> 根（用於刪除樹或評估數學表達式）。
樹的搜尋方式
1. 廣度優先搜尋 (BFS)： 一層一層地探索（由上而下，由左至右）。
2. 深度優先搜尋 (DFS)： 在回溯之前，盡可能地向深處鑽研某一個分支。
總結：樹非常適合表示階層結構（例如電腦中的資料夾）以及進行快速搜尋 (BST)。
4. 雜湊表 (Hash Tables)
雜湊表 (Hash Table) 專為即時查找而設計。它利用雜湊函數 (Hash Function) 將鍵值（如學生 ID）轉換為索引（陣列中的特定位置）。
類比：專屬置物櫃。你不需要檢查每一個櫃子，只要用神奇公式：「你的櫃號就是你 ID 的後兩位數。」你就能直接找到對應櫃子！
問題：碰撞 (Collisions)
如果兩名學生的 ID 結尾都是「23」怎麼辦？這就是碰撞。
處理碰撞（線性探測 Linear Probing）：如果你的指定位置已滿，就尋找下一個可用的空位。這就像發現椅子上有人坐了，就坐到隔壁空位一樣。
重點總結：雜湊表追求的是速度。一個好的雜湊函數能均勻地分佈資料，避免「擠在一起」。
5. 文字檔案處理
程式需要在關閉後仍能「記住」資料，我們透過儲存資料到文字檔案 (Text Files) 來達成。
流程：
1. 開啟 (Open)： 以讀取 (r)、寫入 (w) 或附加 (a) 模式開啟檔案。
2. 處理 (Process)： 使用迴圈讀取檔案中的行，或是將新資料寫入其中。
3. 關閉 (Close)： 一定要關閉檔案！這就像掛斷電話一樣——如果不做，可能會遺失資料或「鎖死」檔案。
你知道嗎？ 在 Python 中，使用 with 關鍵字可以自動為你關閉檔案，即使發生錯誤也能確保檔案安全關閉！
總結檢查表
- 堆疊 (Stack)： LIFO（後進先出）。想想「復原」按鈕。
- 佇列 (Queue)： FIFO（先進先出）。想想「印表機佇列」。
- 鏈結串列 (Linked List)： 節點 + 指標。大小彈性，但搜尋較慢。
- BST： 左小右大。搜尋速度極快。
- 中序遍歷： 可從 BST 取得排序後的資料。
- 雜湊表： 使用函數達成接近即時的存取。留意碰撞！
- 檔案： 永久儲存的關鍵。開啟 -> 處理 -> 關閉。
如果起初覺得有點棘手，別擔心！ 資料結構就像工具箱裡的各種工具。你越常在程式碼中練習使用它們，就越能明白哪個工具才是完成任務的最佳選擇。繼續加油，保持編碼！