演算法系列 · 第 8 關 · 資料結構

堆疊 Stack

後進先出,像一疊盤子 —— 只能從最上面放、從最上面拿。所有操作都 O(1)。

堆疊是一種只有一個開口的容器:放東西、拿東西都只能在頂端(top),底下的碰不到。最後放進去的,會最先被拿出來 —— 這叫後進先出(LIFO,Last In First Out)。正因為限制只能動頂端,push、pop、peek 全都是 O(1),超快。

核心觀念:後進先出 LIFO

只有一個開口 —— 所有動作都在頂端 top 發生,底下的動不到。

push(壓入) —— 放一個到最上面。

pop(彈出) —— 拿走最上面那個。

peek / top(看頂) —— 看一眼最上面是什麼,但不拿走。

後進先出(LIFO) —— 最後放進去的,最先被拿出來。就像一疊盤子。

為什麼要限制只能動頂端?正是這個限制,讓每個操作都超簡單、都 O(1),也剛好對應很多「最近的先處理」的真實情境 —— 復原、返回、遞迴呼叫。

↩️ 復原 / 重做(Undo / Redo) —— 每個動作壓進去,Ctrl+Z 就彈出最後一步。

🔙 瀏覽器上一頁 —— 每開一頁壓一層,按返回就彈掉最近那層。

📞 程式的呼叫堆疊(call stack) —— 函式一層層呼叫、再一層層回來,靠的就是堆疊。

🧩 括號配對、算式求值、深度優先搜尋(DFS) —— 都以堆疊為核心(範例區有)。

O(1)push(壓入) —— 放到最上面,不動別人。

O(1)pop / peek —— 彈出或看頂端,也只碰最上面那一個。

O(n)空間 —— n 個元素就要 n 格。

重點:堆疊的每個「動作」都是 O(1),因為永遠只碰頂端。但別想在堆疊裡「找中間某個值」—— 那得整疊倒出來,失去它的意義,該用別的結構。

🍽️

最後洗好放上去的那個,下次最先被拿走。只能從最上面動,不會去抽最底下那片。

🔙

每點一個連結就壓一層,按「上一頁」就彈掉最近那層,回到前一頁。

↩️

每個編輯動作壓進堆疊,復原時就把最後做的那一步彈出來取消。

按 push 把「待壓入」最左邊那個疊到最上面,pop 拿走最上面,peek 看一眼頂端但不拿。紫色永遠是頂端 top。試試看:不管怎麼按,你都只能動最上面那一個。

↓ 只能從這頭進出(top 頂端)

底 bottom · 碰不到

待壓入(push 拿最左邊)

從用 list 當堆疊、包成 class,到括號配對、逆波蘭求值、單調堆疊、兩個堆疊做佇列等經典題。

❌ pop / peek 前沒檢查空堆疊 —— 對空的 list 做 pop() 會 IndexError。先 if stack: 或 is_empty()。

❌ 用 pop(0) 當堆疊 —— pop(0) 是從頭拿、O(n);堆疊要用 pop()(尾端)才 O(1)。

❌ 搞混頂端在哪 —— 用 list 當堆疊,頂端是最右邊 [-1],不是 [0]。

❌ 需要先進先出卻用堆疊 —— 那要的是佇列(下一頁),別用堆疊。

把答案打到對話裡,我幫你對。