🎯 什麼情境該想到我
當你「需要一個有明確存取順序的暫存區」的時候。
★ 概念簡單，但在 Go 裡「該用什麼型別」是有明確答案的——而且多數人第一次會選錯。
⚙️ 怎麼用（機制與 Go 實作）
兩種順序
| 規則 | 直覺 | 主要用途 | |
|---|---|---|---|
| 堆疊 Stack | LIFO 後進先出 | 疊盤子 | 遞迴、回溯、撤銷、括號匹配、DFS |
| 佇列 Queue | FIFO 先進先出 | 排隊 | BFS、工作排程、緩衝、速率限制 |
★ Go 的堆疊：直接用 slice，不要用 container/list
stack := []int{}
stack = append(stack, v) // push — 攤還 O(1)
top := stack[len(stack)-1] // peek
stack = stack[:len(stack)-1] // pop為什麼 slice 是對的：
append是攤還 （容量不足時倍增，見下方推導）- 連續記憶體 → 快取友善
- 零額外配置（pop 只是改長度）
⚠️ 持有指標時要手動清零，否則被 pop 掉的元素仍被 slice 的底層陣列引用，GC 收不掉：
stack[len(stack)-1] = nil // ★ 避免記憶體洩漏 stack = stack[:len(stack)-1]這是 Go 裡很典型的一個坑——slice 縮短不會清除底層陣列的內容。
★ Go 的佇列：slice 的天真做法有問題
// ❌ 錯誤示範
queue = append(queue, v)
head := queue[0]
queue = queue[1:] // ★ 看起來 O(1)，但底層陣列的頭部永遠不會被回收問題：queue[1:] 只是移動 slice 的起點，被丟掉的前綴仍然佔著底層陣列。
一個跑很久的佇列會讓底層陣列無限成長（雖然 len 很小），直到 append 觸發重新配置才釋放。
三個正確做法：
| 做法 | 適用 |
|---|---|
| ① 索引 + 定期壓縮 | 用 head 索引而非 reslice，head 超過一半時 copy 壓縮 |
| ② ★ 環形緩衝（ring buffer） | 固定容量、、無配置——高效能場景的標準答案 |
③ chan | ★ 需要跨 goroutine 時的正解：有界、執行緒安全、可搭配 select（見 工具-靠通訊共享記憶體） |
// ② 環形緩衝
type Ring[T any] struct {
buf []T
head, tail, n int
}
func (r *Ring[T]) Push(v T) bool {
if r.n == len(r.buf) { return false } // 滿了
r.buf[r.tail] = v
r.tail = (r.tail + 1) % len(r.buf) // ★ 取模繞回去
r.n++
return true
}
func (r *Ring[T]) Pop() (T, bool) {
var zero T
if r.n == 0 { return zero, false }
v := r.buf[r.head]
r.buf[r.head] = zero // ★ 清零，讓 GC 能回收
r.head = (r.head + 1) % len(r.buf)
r.n--
return v, true
}★ 不要用
container/list（雙向鏈結串列）。
它每個元素都是獨立配置的節點，快取極不友善、GC 壓力大，而且沒有泛型（存any要斷言）。
在 Go 裡它幾乎永遠是錯的選擇（見 鏈結串列）。
★ 為什麼 append 是「攤還 」
Go 的 slice 在容量不足時會配置一個更大的陣列並複製。單次可能是 ，但平均是 。
攤還分析（聚合法）：容量倍增時，插入 個元素的總複製成本是
（等比級數）→ 平均每次 。
★ 倍增是關鍵。 如果每次只
+1擴容，總成本會變成 ，
平均每次 。「倍增」把它壓成常數。
同樣的推導也解釋了 雜湊表 的 rehash 為什麼是攤還 。
幾個值得記住的應用
| 應用 | 用哪個 | 關鍵 |
|---|---|---|
| DFS | 堆疊 | 顯式堆疊可避免遞迴爆掉（見 深度優先搜尋） |
| BFS | 佇列 | 必須是 FIFO，用堆疊就變成 DFS 了（見 廣度優先搜尋） |
| 括號匹配／表達式求值 | 堆疊 | 經典題 |
| 撤銷／重做 | 兩個堆疊 | undo stack + redo stack |
| ★ 單調堆疊 | 堆疊 | 維持堆疊內單調遞增/遞減， 解決「下一個更大元素」「最大矩形」這類問題——一個很強的技巧 |
| 雙端佇列（deque） | 兩端都能進出 | 滑動視窗最大值的 解法 |
| 工作佇列／限流 | 佇列（chan） | 有界 channel 天然提供背壓 |
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- ★ Go 的 slice 佇列會洩漏底層陣列（見上）。長壽命佇列一定要用環形緩衝或定期壓縮。
- ★ 持有指標/介面時 pop 要清零，否則 GC 收不掉。
- 不要用
container/list。 - 跨 goroutine 一律用
chan，不要自己加鎖包 slice——chan已經處理好同步、阻塞與關閉語義。 - 無界佇列是生產事故的常見來源。生產者比消費者快時會吃光記憶體。用有界 channel 製造背壓（見 工具-降低在製品WIP、工具-MQ消費端防禦三原則）。
- 堆疊深度有限。遞迴 DFS 在深圖上會爆堆疊（Go 的 goroutine 堆疊會成長但有上限，預設 1 GB）。深度不可控時改用顯式堆疊。