🍽️
歡迎來到 Stack & Queue
這個單元你將學習兩種有「規矩」的資料結構。先完成 3 個小任務，感受它們的差異！
進度
高中資訊科 · 資料結構 · 第二單元

🥞 Stack & Queue

疊盤子 vs 排隊買便當——兩種有規矩的資料結構

🤔 開始之前，先說說你的直覺
你去自助餐廳拿盤子，最上面的盤子是最後被放上去的——這是 Stack 還是 Queue 的概念？
你在便利商店結帳排隊，先到的人先結帳——又是哪個？先選一個你「最搞不清楚」的：
時間複雜度一覽
操作 Stack Queue
Push / Enqueue（加入）O(1)O(1)
Pop / Dequeue（取出）O(1)O(1)
Peek / Front（看頂端）O(1)O(1)
搜尋特定值O(n)O(n)
隨機存取第 i 個❌ 不支援❌ 不支援
與 Array、Linked List 的關係
🔧 Stack 和 Queue 是「高階」結構 Array 和 Linked List 是儲存資料的方式；Stack 和 Queue 是限制存取規則的結構。
Stack / Queue 的底層，通常用 Array 或 Linked List 實作。
特性 Array Linked List Stack Queue
隨機存取 ✅ O(1) ❌ O(n) ❌ 不支援 ❌ 不支援
插入/取出規則 任意位置 任意位置 只能 top rear進/front出
Push/Enqueue — — O(1) O(1)
主要用途 大量讀取 頻繁插刪 Undo、遞迴 排程、BFS
💭 反思一下 後設認知練習
Stack 和 Queue 的操作都是 O(1)，為什麼還是不能「搜尋特定值」？
REFERENCE ANSWER
Stack 和 Queue 最核心的限制是：你只能操作特定的那一端——Stack 只能動 top，Queue 只能從 front 取出、rear 放入。

要搜尋特定值，就必須把資料一個一個取出來比對，這個過程需要 O(n) 步。而且「取出」會改變結構本身（資料就消失了），所以 Stack / Queue 本質上不適合拿來搜尋。

這就是為什麼說 Stack / Queue 是「限制存取規則」的結構——它們的強項是特定的操作模式，不是通用的資料查詢。
你覺得自己理解了多少？
📱 這些你每天都在用 Stack 和 Queue 不只是理論——它們是讓你的手機、電腦每天順暢運作的核心機制。
Stack 的應用（LIFO）
↩️
Ctrl+Z 復原
每次操作都 Push 進 Stack，按 Ctrl+Z 就 Pop 出最後一個動作並撤銷。一步一步往回退，就是因為 LIFO。
🌐
瀏覽器「上一頁」
每次跳轉頁面都 Push 當前網址，按上一頁就 Pop 出來。最近造訪的頁面最先回去——LIFO。
♟️
下棋悔棋
每一步棋 Push 進記錄，悔棋就 Pop 出最後一步，還原棋盤狀態。
🔤
字串反轉
把字元逐一 Push，再逐一 Pop，自然得到反轉結果——LIFO 的完美應用。
Queue 的應用（FIFO）
🖨️
印表機列印佇列
多人同時送出列印，進入 Queue 等待。先送出的先印，公平排隊——FIFO。
📞
客服電話排隊
打進來的電話排成 Queue，客服空了就接第一個等待的電話——先來先服務。
💻
CPU 行程排程
作業系統用 Queue 安排多個程式的 CPU 執行順序，確保每個程式公平獲得資源。
🗺️
BFS 廣度優先搜尋
圖的走訪演算法用 Queue 實作，把鄰居節點 Enqueue，依序 Dequeue 展開——是 Google Maps 等路徑搜尋的基礎。
💭 反思一下 後設認知練習
為什麼 Ctrl+Z 要用 Stack 而不是 Queue？如果用 Queue 的話會發生什麼事？
REFERENCE ANSWER
Ctrl+Z 的目的是「取消最近的那一個動作」——這正是 LIFO（後進先出）。

如果改用 Queue（FIFO，先進先出），那按下 Ctrl+Z 時，撤銷的會是最早的那個動作，而不是剛才做的那個。
舉例：你依序做了「打字 → 刪除 → 換行」三個動作，如果是 Queue，按 Ctrl+Z 會撤銷「打字」（最早的），而不是「換行」（最近的）。這顯然不符合使用者的預期！

結論：需要「還原到最近狀態」的問題 → Stack；需要「公平排隊按順序處理」的問題 → Queue。
你覺得自己理解了多少？
🎯 挑戰：每個情境，是 Stack 還是 Queue？ 點選情境卡片，再點右邊的 Stack 或 Queue。答對才有綠色勾，全對才算過關！
得分 0 / 8
📋 情境 — 點選或拖曳
📦 放到這裡
Stack
LIFO 後進先出
Queue
FIFO 先進先出

📊 你的學習前後對比

開始前不太懂的
—
連連看實際得分
—