数据结构基础：数组、栈、队列、树与哈希表

本文以教学为目的，示例刻意保持简单。实际 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 表达一般连接。

最好的数据结构不是最复杂的那一个，而是能让程序真正需要的操作清晰且可预测的那一个。