書籍資訊

  • 書名：《圖解演算法：使用 C#》
  • 類型：線性資料結構與經典題型整理

這篇在講什麼

這一篇主要整理幾個彼此很常一起出現的主題：

  • Stack 的操作方式
  • Queue 的操作方式
  • 雙端佇列與優先佇列
  • 河內塔與八皇后這類典型遞迴 / 回溯問題

堆疊 Stack

Stack 的規則很單純：

  • 後進先出，Last In First Out

最常見操作：

  • Push
  • Pop
  • Peek

它常出現在：

  • 函式呼叫堆疊
  • 括號匹配
  • DFS
  • 表達式處理

如果用一句話記：

Stack 適合處理「最近放進去的東西，最先拿出來」的問題。

佇列 Queue

Queue 則是另一套順序：

  • 先進先出，First In First Out

最常見操作：

  • Enqueue
  • Dequeue

它常用在：

  • 排程
  • 任務等待列
  • BFS
  • 訊息緩衝

和 Stack 對照很好記：

  • Stack：像疊盤子
  • Queue：像排隊

雙端佇列與優先佇列

雙端佇列 Deque

Deque 的特點是兩端都能進出。

它適合：

  • 需要從頭尾都操作資料
  • 滑動視窗
  • 單調佇列

優先佇列 Priority Queue

Priority Queue 不是按先後順序出隊，而是按優先級決定誰先出去。

也就是：

  • 高優先級先處理
  • 不一定遵守 FIFO

它很常用在：

  • 工作排程
  • Dijkstra
  • A*

這些結構和演算法的關係

很多演算法本身其實不複雜，複雜的是你有沒有選對容器。

例如：

  • DFS 常常配合 Stack
  • BFS 常常配合 Queue
  • 最短路徑常常配合 Priority Queue

所以資料結構不是配角，它會直接決定演算法的執行方式。

河內塔與遞迴

河內塔是很典型的遞迴題。
核心不是移動盤子，而是學會把大問題拆成更小的同型問題。

當有 n 個盤子時，可以拆成三步：

  1. 先把上面 n - 1 個移到中繼柱
  2. 再把最大那個移到目標柱
  3. 再把 n - 1 個移到目標柱
public static void Hanoi(int n, char from, char helper, char to)
{
    if (n == 1)
    {
        Console.WriteLine($"{from} -> {to}");
        return;
    }

    Hanoi(n - 1, from, to, helper);
    Console.WriteLine($"{from} -> {to}");
    Hanoi(n - 1, helper, from, to);
}

八皇后與回溯

八皇后問題的核心是回溯 Backtracking。

做法大致是：

  • 一列一列放皇后
  • 每次只放在目前合法的位置
  • 如果某一步無法再放，就退回上一層重選

這類題的本質不是暴力亂試，而是：

  • 嘗試
  • 檢查
  • 不行就撤回

也就是典型的搜尋樹思維。

我自己的整理

這一篇真正要記住的是：

  • Stack 和 Queue 不只是資料結構名詞
  • 它們其實對應兩種完全不同的處理順序

而像河內塔、八皇后這種題目，表面上在講盤子或棋盤，實際上是在訓練：

  • 遞迴拆解
  • 搜尋順序
  • 狀態回退

先記住的重點

  • Stack 是 LIFO，Queue 是 FIFO
  • Deque 兩端都能操作，Priority Queue 依優先級出隊
  • DFS 常和 Stack 配合，BFS 常和 Queue 配合
  • 河內塔是在練遞迴拆解
  • 八皇后是在練回溯與合法性檢查