上一篇談 Priority Queue 時，我們看到了一件很重要的事：

資料不一定按照進來的時間被處理，「誰先被拿出來」本身就是問題的一部分。

• Queue 的規則是： 誰先來 → 誰先處理
• Priority Queue 則變成：誰比較重要 → 誰先處理

今天再看另一個每天都可能遇到的例子 復原（Undo）。

假設你正在編輯一份文件，依序做了這些事情：

輸入文字
→ 改字體
→ 插入圖片
→ 刪除段落

現在你發現最後一步刪錯了，按下復原時，你期待發生什麼？
想當然應該要是：

撤銷「刪除段落」

再按一次復原，才會撤銷：

插入圖片

希望的是：

最後發生的操作，要最先被撤銷。

不是所有資料都應該「先來先處理」

如果把剛才的操作按照發生順序排出來：

輸入文字
改字體
插入圖片
刪除段落

最早發生的是 輸入文字，最後發生的是 刪除段落。
但復原要處理的，應該要是最後的操作，所以它的規則是：

最後加入
↓
最先取出

這種規則稱為：

LIFO — Last In, First Out (後進先出)

而最典型用來描述這種規則的資料結構，就是Stack。

Stack 像什麼？

英文中 stack of... 指的就是一疊...，那麼你就可以類比一疊什麼的運作機制；
假設想像桌上有一疊盤子，你依序放上：

盤子 A
盤子 B
盤子 C
盤子 D

最後會變成：

┌───────┐
│   D   │ ← 最上面
├───────┤
│   C   │
├───────┤
│   B   │
├───────┤
│   A   │
└───────┘

現在如果要拿一個盤子，通常會先拿 D，並不是把最下面的 A 硬抽出來。
所以：

最後放進去的 D
↓
最先被拿出來

這就是 Stack 的語意。

Stack 最重要的兩個操作

Stack 最常見的兩個操作叫做：

• push
• pop

push 的意思是：

把一筆資料放到 Stack 的最上方。

pop 則是：

把 Stack 最上方的資料拿出來。

例如：

push(A)
push(B)
push(C)

Stack 會變成：

C ← top
B
A

接著 pop() 拿到的是 C，再一次 pop() 拿到的是 B，順序會是：

加入：
A → B → C

取出：
C → B → A

這就符合 Last In, First Out(後進先出) 的機制。

JavaScript 可以怎麼表示 Stack？

JavaScript 的 Array 本身就提供了適合模擬 Stack 的操作。
例如：

const stack = []

stack.push('輸入文字')
stack.push('改字體')
stack.push('插入圖片')
stack.push('刪除段落')

現在：

console.log(stack)

概念上可以想成：

[
  '輸入文字',
  '改字體',
  '插入圖片',
  '刪除段落'
]

最後加入的是 '刪除段落'，所以：

const lastAction = stack.pop()

console.log(lastAction)

會得到 '刪除段落'。
再執行一次：

stack.pop()

就會拿到 '插入圖片'。
這已經是一個非常簡單的復原紀錄。

復原功能真正保存的是「操作歷史」

當然，真正的文字編輯器不會只保存幾個字串。
它可能保存的是某種操作描述，例如：

const history = []

history.push({
  type: 'insert-image',
  imageId: 'image-001'
})

history.push({
  type: 'delete-paragraph',
  paragraphId: 'paragraph-003'
})

當使用者按下復原：

const action = history.pop()

系統拿到最近的一個操作 delete-paragraph，接著才根據這筆紀錄決定：

要怎麼把這個操作復原？

所以 Stack 解決的是一個淺顯易懂的問題：

如果我要復原，下一個應該處理哪一筆歷史紀錄？

用膝蓋想也知道是最後發生的那一筆，這就是資料結構正在描述的規則。

為什麼不能從第一步開始復原？

回到剛才的操作：

輸入文字
→ 改字體
→ 插入圖片
→ 刪除段落

假設我們真的從第一步開始撤銷：

先撤銷「輸入文字」

問題馬上就來了。
後面的：

改字體
插入圖片
刪除段落

可能全部都是建立在前面的狀態上，你卻用月光寶盒飛去修改很久以前的歷史。

相反地，如果從最後一步開始：

刪除段落
↓
插入圖片
↓
改字體
↓
輸入文字

我們是在沿著原本操作的反方向，一步一步走回去。
原本是：

A → B → C → D

復原順序則是：

A ← B ← C ← D

這正是 Stack 特別適合處理的情況。

Stack 不只用在復原功能

這種「沿著剛才走過的路往回走」的需求，其實非常常見。
例如你走進一座迷宮：

入口
↓
路口 A
↓
路口 B
↓
路口 C

結果在 C 發現 死路。
你下一步會去哪？
通常不是直接跳回入口，而是先回 路口 B。
如果 B 的其他方向也不行，再回 路口 A。
也就是：

最後走到 C
→ 最先退回 C

再來 B
再來 A

這與復原操作的結構其實非常相似。

這就是回溯的直覺

之後我們會遇到一類很重要的演算法思考方式：

Backtracking（回溯）

現在不需要記它的完整演算法。
先記住它非常直覺的想法：

做一個選擇
↓
再做一個選擇
↓
再做一個選擇
↓
發現走不通
↓
退回上一個選擇

例如：

A
↓
選 B
↓
選 C
↓
選 D
↓
發現 D 不行

那就：

D ← 回去
C ← 找其他可能

所以你可以先把回溯想像成：

替選擇按下復原鍵

而因為復原操作天然具有 LIFO(Last In, First Out) 的特性，所以 Stack 也經常出現在這類問題裡。

Function Call 其實也是類似概念

Stack 另一個常見例子，就是 function call stack。
例如：

function a() {
  b()
}

function b() {
  c()
}

function c() {
  console.log('Hello')
}

a()

概念上發生的是：

a()
↓
b()
↓
c()

當 c() 執行完，程式要回去哪裡？
不是直接跳回最外層，是先回到 b()。
b() 結束後，再回 a()。
也就是：

進入：

a
→ b
→ c

離開：

c
→ b
→ a

又是一個 LIFO 的結構，這也是為什麼我們會聽到 Call Stack 這個講法。
至於 JavaScript Engine 到底怎麼管理執行環境、execution context 又是什麼，現在先不用展開。
這裡只需要掌握：

函式呼叫也存在「最後進入的函式先結束」這種 Stack 式的 ordering。

Queue 和 Stack 到底差在哪？

現在回頭看前幾篇，就會發現一件很有趣的事情。
假設我們都有四筆資料：

A
B
C
D

資料本身完全沒有改變。
真正改變的只是：

下一個應該拿誰？

Queue

最早加入的先處理。

加入：

A → B → C → D

下一個：

A

也就是 FIFO(First In, First Out)

Priority Queue

不一定看誰先來，而是看誰的 priority 比較高。

例如：

A(2)
B(5)
C(1)
D(4)

如果數字越大代表 priority 越高：

下一個：

B(5)

所以它關心的是誰最重要？

Stack

最後加入的先處理。

加入：

A → B → C → D

下一個：

D

也就是 LIFO(Last In, First Out)

三種資料結構，其實是三種不同規則

把目前看到的三個例子放在一起：

• Queue：最早加入的先處理
• Priority Queue：最重要的先處理
• Stack：最晚加入的先處理

它們全部都可以「保存很多筆資料」。
如果只是從「能不能把資料存起來？」這個角度看，好像沒有太大的差別。
甚至在 JavaScript 裡，我們都可能先用 Array 模擬它們。

這正好再次說明了第一篇談過的觀念：

資料結構不只是拿來裝資料的容器。

更重要是去想：

我們希望資料之間遵守什麼規則？

Queue 描述時間順序。
Priority Queue 描述優先程度。
Stack 描述最近加入的順序。

「下一個換誰」就是問題的一部分

假設今天有：

A
B
C
D

四筆資料。
如果問題是說：

最早來的先處理

你開始想到 Queue。
如果問題改方向成：

最重要的先處理

你會想到 Priority Queue。
如果問題又改方向成：

最近發生的先處理

你會直覺想到 Stack。
所以：

同樣都是保存一組資料，光是「下一個要換誰」不同，就會形成不同的資料結構。

這也是學資料結構時，比背 API 更重要的一件事。
不要只顧著記 Stack 有哪些 method？
是先去問這個問題要求什麼樣的順序？
當問題順序的需求不同，適合的資料結構也會跟著改變。

但如果我根本不想管順序呢？

到目前為止，我們的討論圍繞在下一個是誰？

• Queue 說：最早的。
• Priority Queue 說：最重要的。
• Stack 說：最新來的。

但現實中還有另一種非常常見的問題。
假設系統裡有幾十萬個使用者。
現在我不是想知道第一個使用者是誰？
也不是最後一個使用者是誰？
更不是優先級最高的使用者是誰？

我只想問 userId = 12345 的人在哪裡？

這時候誰先誰後，可能根本不重要。

我們真正想要的是：

直接根據某個 key 找到那筆資料

如果問題變成這樣，我們是不是也應該換一種描述資料的方法？
下一篇就來看看：

如果我們根本不在乎順序，只想直接找到某一筆資料呢？