Data Structure

photo by John Cameron 剛好昨天看了小Lin老師的影片，提到委內瑞拉這個國家，天天都在排隊 加油排隊、去超市也排隊 排隊這件事，其實跟系統處理工作的順序一樣 順序一亂，待季就大條了，這時候使用Queue來管理執行順序，是一個很好的方法 什麼是 Queue Queue 是一種 先進先出 (First-In，First-Out，FIFO) 的資料結構 Queue跟Stack一樣，定義了使用者只能用那些操作 換來一致性的時間複雜度 Queue的時間複雜度 操作 Queue 時間複雜度 push 插入資料到最後位置 O(1) pop 刪除最前面的資料 O(1) front 取得最前面的資料 O(1) 使用Queue最佳場景 假設現在有三個Job依序執行，而執行中很可能因為系統當機導致需要重做 這時候應該把Job放在哪種資料結構中： A：List搭配index B：Queue 看起來A、B都可以，實際上會造成很大的落差 情境A List搭配index list = [A, B, C] i = load_index() // 持久化的進度 while i < list.length: job = list[i] do_side_effect(job) // 例如：寄信 / 扣款 / 發送檔案 // 這裡可能成功、也可能一半成功、也可能成功但你還沒來得及記錄 i = i + 1 save_index(i) // 持久化進度 crash可能發生在： ...

photo by Jessica Johnston 什麼是 Hash Table Hash Table 是一種透過 hash function 將 key 映射到 bucket, 以達成 平均 O(1) 查找效率 的資料結構 資料通常以 key–value 的形式儲存, 使用者只需要提供 key,就能快速取得對應的 value 在實作上,Hash Table 內部會維護一組 bucket array, 每個 bucket 可以儲存一個或多個元素 當資料量持續增加、bucket 內元素變得過於擁擠時, Hash Table 會透過 resize / rehash 重新分配資料, 以維持查找效能 為什麼 Hash Table 可以快速查詢資料？ Hash Table 能快速查詢資料的關鍵,在於 hash function 當一個 key 被插入或查詢時, Hash Table 會先對 key 計算 hash 值, 再將 hash 值映射成一個 bucket index, 用來決定資料應該存放或查找的位置 ...

photo by Reed Mok 玩過河內塔嗎? 這是是一個只能從一個桿子中拿最上面圓盤的遊戲, 然後再把圓盤放到另一個桿子的最上方 看到Stack的結構馬上就想到這個例子 什麼是 Stack 一個定義好行為的資料結構 使用者只能把資料一層一層疊在最上方 使用者一次只能取最上方的資料 為什麼要定義行為 先看看Array跟Stack的差異 操作 Array Stack Search 可以查詢指定index 只能看最上方資料 Insert 可以Insert指定index 只能push資料到最上方 Remove 可以Remove指定index 只能pop最上方資料 可以看到Array跟Stack的差異在於限制了行為:新增、刪除、查詢的位置, 為的是換來操作的一致性, 跟較好的時間複雜度 Stack 的時間複雜度 操作 複雜度 說明 讀取 (Seek) O(1) 讀取最上方資料 插入 (Push) O(1) 插入資料到最上方 刪除 (Pop) O(1) 刪除最上方資料 使用 Stack 的最佳場景 後進先出的場景 剪貼簿的Undo, Redo功能 Rollback 實作Undo, Redo功能 #include <iostream> #include <stack> #include <string> using namespace std; int main() { stack<string> undoStack; stack<string> redoStack; while (true) { cout << "\nChoose:\n" << "1) Add data\n" << "2) Undo\n" << "3) Redo\n" << "4) Exit\n" << ">> "; int choice = 0; if (!(cin >> choice)) break; if (choice == 1) { cout << "Enter data (one word): "; string x; cin >> x; undoStack.push(x); while (!redoStack.empty()) redoStack.pop(); // 清空 redo cout << "Added: " << x << endl; } else if (choice == 2) { if (undoStack.empty()) { cout << "Nothing to undo." << endl; } else { string x = undoStack.top(); undoStack.pop(); redoStack.push(x); cout << "Undo: " << x << endl; } } else if (choice == 3) { if (redoStack.empty()) { cout << "Nothing to redo." << endl; } else { string x = redoStack.top(); redoStack.pop(); undoStack.push(x); cout << "Redo: " << x << endl; } } else if (choice == 4) { cout << "Bye." << endl; break; } else { cout << "Invalid choice." << endl; } cout << "Undo size: " << undoStack.size() << ", Redo size: " << redoStack.size() << endl; if (!undoStack.empty()) cout << "Undo top: " << undoStack.top() << endl; if (!redoStack.empty()) cout << "Redo top: " << redoStack.top() << endl; } return 0; } 程式碼說明: ...

photo by Shubham Dhage 你玩過心理測驗嗎? 有些心理測驗的題目是這樣的 你是男生, 請跳到第 8 題, 妳是女生請跳到第 3 題… 這樣照著前一個指令跳到下一個指定位置的遊戲真的很像 Linked List 的結構 什麼是 Linked List 一個資料結構, 每一筆資料除了自己的值外, 還知道下一筆資料是誰, 因此所有操作都必須照順序進行 Linked List 的時間複雜度 操作 複雜度 說明 讀取 (Read) O(n) 必須從頭開始遍歷資料 插入 (Insert) O(1) 在已知插入的位置時, 只需調整前後關係 刪除 (Delete) O(1) 在已知刪除的位置時, 只需修改前後關係 使用 Linked List 的最佳場景 已知要在某個元素的位置, 並且在元素前後頻繁操作插入刪除 這也是 LRU Cache 常使用 Linked List 的原因之一

photo by Reed Mok 想像你是一位老師，要管理一個新班級的學生名單 人數少的時候，你可以直接用名字來記住每一位學生，但當學生人數一多，要快速找到某一位學生就變得困難 情境 A：變數分散管理 如果我們像這樣單獨宣告變數來存學生名字： string student1 = "Alice"; string student2 = "Bob"; string student3 = "Charlie"; // ... 如果有 50 個學生，變數會多到無法管理 這種方式的問題在於： 沒有順序性：變數之間沒有邏輯上的關聯 無法索引：不能用「第 3 個學生」這種方式來存取 難以自動化：無法用迴圈（Loop）來批次處理這群資料 情境 B：使用 Array 統一管理 這時候，如果替每位學生分配一個固定的「座號」，並依照座號的順序將學生資料排排站（存放起來），只要知道座號，就能直接找到對應的學生 struct Student { string name; }; // 學生名單 (Array) Student students[] = { {"Alice"}, // index 0 (座號 1) {"Bob"}, // index 1 (座號 2) {"Charlie"} // index 2 (座號 3) }; const int numStudents = 3; Student* findStudentBySeatNumber(int seatNumber) { // 檢查座號是否合法 if (seatNumber < 1 || seatNumber > numStudents) { return nullptr; } // 透過索引直接取得資料 (Array Index 從 0 開始) return &students[seatNumber - 1]; } 這就是 Array 的核心精神 ...