資料結構基礎：陣列、堆疊、佇列、樹與雜湊表

本文以教學為目的，範例刻意保持簡單。實際 C++ 專案應先考慮標準函式庫容器，只有在需求與測量結果充分時才自行實作。

學資料結構看起來像是在背 push、pop 和 linked list node。真正重要的能力，是根據程式最常做的工作安排資料，讓那些操作變得簡單、便宜而且可預測。

同樣十個值，若常依索引讀取就適合陣列；要復原最近操作可用堆疊；先處理最早請求可用佇列；依 key 查找則可考慮雜湊表。

資料結構與抽象資料型別

堆疊是一項規則：最後放入的值最先取出。內部可以用連續陣列，也可以用連結串列。使用者看見的操作與規則是抽象資料型別，實際儲存方式則是它的實作。

• push 把值放到頂端。
• pop 移除頂端值。
• top 或 peek 只查看，不移除。
• empty 判斷是否為空。
• size 回報元素數量。

C++ 的 std::stack 是 container adapter，預設底層容器為 std::deque。

最少需要知道的複雜度

Big O 不是全部。記憶體量、cache locality、配置成本、iterator 失效與實作複雜度都會影響實際結果。

陣列使用連續記憶體

int scores[5] = { 10, 20, 30, 40, 50 };

知道起始位址與元素大小後，可直接算出索引 i 的位址。

address(i) = base + i × sizeof(element)

所以索引存取是 O(1)，連續走訪通常也有良好 cache 效果。中間插入需要搬動後方元素，最壞為 O(N)。固定長度的 C++ 容器可使用 std::array。

動態陣列與 std::vector

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

vector 管理連續儲存區、目前 size 和不重新配置時能容納的 capacity。有空間時尾端加入是常數時間；空間不足時會配置更大的區塊並搬移元素。單次重新配置為 O(N)，但大量 push_back 的平均分攤成本為 O(1)。

預先知道大概數量時可呼叫 reserve。重新配置後，舊元素的 pointer、reference 與 iterator 可能失效。

連結串列

struct Node
{
    int value;
    Node* next;
};

已知某個節點時，在它後方插入只需改幾個 link，因此是 O(1)。但找第 100 個元素必須從前面逐一走訪，隨機存取為 O(N)。

串列還需要額外指標空間，節點分散可能降低 cache 效率，手寫實作也容易出現所有權錯誤。不能只因為「插入很多」就認定串列比 vector 快，還要包含尋找位置的成本。

堆疊先移除最後放入的值

堆疊遵守 LIFO，Last In First Out。

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

top 為 30，之後堆疊留下 10 和 20。

pop 不會回傳值

C++ 的 std::stack::pop() 只移除元素，回傳型別是 void。要先讀取再移除。

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

不可對空堆疊呼叫 top 或 pop。

用 vector 實作小型堆疊

template <typename T>
class SimpleStack
{
public:
    void push(const T& value) { values_.push_back(value); }

    void pop()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty()) throw std::underflow_error("empty stack");
        return values_.back();
    }

    bool empty() const { return values_.empty(); }

private:
    std::vector<T> values_;
};

堆疊常用於函式呼叫、復原紀錄、括號配對、DFS、後序表示式，以及把遞迴改成迭代。

佇列先移除最早放入的值

佇列遵守 FIFO，First In First Out。

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

first 為 101。佇列適合排程、訊息處理、列印工作、BFS 與封包緩衝。

環形緩衝區

不必在移除陣列第一項時搬動所有元素，可以分別管理 head 與 tail。索引到達實體末端後用餘數回到 0。

tail = (tail + 1) % Capacity;
head = (head + 1) % Capacity;

固定容量 ring buffer 適合音訊、遊戲事件和有上限的 producer-consumer 流程。多執行緒仍需要同步或專用 concurrent queue。

Deque 與 priority queue

std::deque 能在前後兩端插入與移除，適合 work stealing、sliding window 與雙向等待列。它不像 vector 一樣保證整體位於單一連續區塊。

優先佇列不是照到達順序，而是先提供優先度最高的值。

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);
int highest = scores.top();
scores.pop();

通常以 heap 實作。查看頂端是 O(1)，插入與移除頂端為 O(log N)。

雜湊表

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

雜湊函式由 key 選擇 bucket。分布和 load factor 合理時，搜尋、插入、刪除平均為 O(1)。碰撞無法避免，最壞情況可變成 O(N)。

自訂 key 的相等判斷與 hash 必須一致。被判定相等的 key 一定要有相同 hash。

樹與二元搜尋樹

樹適合檔案系統、UI、scene graph 與文件階層。root 沒有 parent，leaf 沒有 child，depth 是到 root 的距離，height 是到最深 leaf 的距離。

二元搜尋樹每個節點最多有兩個 child，常見規則是較小 key 放左邊、較大 key 放右邊。平衡時搜尋、插入、刪除為 O(log N)；把已排序資料放入簡單樹可能退化成長鏈並變為 O(N)。

std::map 保留 key 順序並提供 O(log N) 操作。不需要順序而更重視平均常數搜尋時，可考慮 std::unordered_map。

Heap

max-heap 中 parent 不小於 child，min-heap 則相反。整體並沒有完全排序。

完整二元樹可以有效存入陣列。索引從 0 開始時：

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

heap 適合重複取出最小或最大值，但搜尋任意值通常仍為 O(N)。

Trie 與 graph

trie 以 key 的字元或 bit 作為路徑，可共享前綴。搜尋通常以 key 長度 L 表示為 O(L)，常用於自動完成、字典和路由。

graph 由 vertex 和 edge 組成。adjacency matrix 的連線查詢為 O(1)，記憶體為 O(V²)；adjacency list 約用 O(V + E)，適合 sparse graph。

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

BFS 使用佇列，DFS 使用呼叫堆疊或明確的堆疊。

代表性複雜度

如何選擇

先確認最常見操作、是否保留順序、是否需要索引、依 key 查找或反覆取極值、最大數量、pointer 穩定性、外部 API 是否要求連續記憶體，以及是否多執行緒存取。一般值序列可先從 std::vector 開始，等具體需求出現再更換。

常見錯誤

• 對空 stack 或 queue 呼叫 top、front、pop。
• 認為 C++ pop 會回傳被移除的值。
• vector 重新配置後繼續使用舊 pointer。
• 忽略尋找插入位置的成本，認為 list 永遠較快。
• 把雜湊表操作說成保證 O(1)。
• 忽略遞迴 DFS 的呼叫深度。
• 用沒有明確所有權的 raw pointer 建立樹。

總結

陣列與 vector 提供快速索引和良好 locality。連結串列在已知位置改 link 很快，但走訪與分散記憶體有成本。stack 先處理最新值，queue 先處理最舊值，deque 使用兩端，priority queue 提供最重要的值。雜湊表擅長平均 key 搜尋，平衡樹維持順序，heap 提供極值，graph 表達一般連線。

最好的資料結構不是最複雜的那一個，而是能讓程式真正需要的操作清楚且可預測的那一個。