bittern.cn
4算法竞赛入门经典（第2版）

基础数据结构

常用数据结构

栈队列链表树

🎯 AI 时代的学习建议：不要只读理论。理解这一章的设计动机（为什么需要这个概念？）和边界条件（什么情况下会失效？）。当 AI 生成的代码涉及这些概念时，你能判断它是否用对了场景。AI 能帮你总结内容，但无法替代你亲手阅读、思考、建立直觉的过程。

第4章：基础数据结构（Fundamental Data Structures）

一、导读

4.1 本章学习目标

如果说前三章教给你的是编程的"语法"，那么从本章开始，你正式进入算法的"词汇"世界。数据结构是算法的基石——没有合适的数据结构，再精巧的算法也无从谈起。本章介绍四种最基础也最重要的数据结构：栈、队列、链表和树，以及 C++ STL 中对应的容器。

本章的核心学习目标包括：

  • 理解栈的原理和应用：后进先出（LIFO）的特性，以及在括号匹配、表达式求值、DFS 中的关键作用。
  • 掌握队列的原理和应用：先进先出（FIFO）的特性，以及在 BFS、拓扑排序中的核心地位。
  • 了解链表的基本操作：动态数据结构的插入、删除、遍历，以及与数组的对比。
  • 认识树的结构和遍历：二叉树、二叉搜索树的概念，前序、中序、后序遍历。
  • 熟练使用 STL 容器：stack、queue、priority_queue、vector、set、map 的用法和复杂度。
  • 学会选择合适的数据结构：根据问题的特点，选择最高效的数据结构来建模和求解。

4.2 为什么本章如此重要

数据结构的选择往往决定了一个算法的成败。同一个问题，用不同的数据结构来实现，时间复杂度可能相差几个数量级。例如：

  • 用数组维护有序集合，插入 O(n)；用 set（红黑树），插入 O(log n)。
  • 用数组模拟队列，需要手动管理头尾指针；用 STL queue，代码简洁且不易出错。
  • 用邻接矩阵存图，空间 O(V²)；用邻接表，空间 O(V+E)。

在算法竞赛中，STL 是你的好朋友。它提供了经过高度优化的数据结构实现，使用它们不仅能节省编码时间，还能获得接近最优的性能。熟练掌握 STL 容器，是竞赛选手的基本素养。

栈和队列看似简单，但它们的应用范围之广可能超出你的想象。从括号匹配到表达式求值，从 BFS 到拓扑排序，从单调栈到滑动窗口，栈和队列的变体贯穿了整个竞赛算法体系。

4.3 核心问题引导

在阅读本章时，请带着以下问题思考：

栈的"后进先出"特性在哪些问题中是优势？在哪些问题中是劣势？

队列和栈的核心区别是什么？BFS 为什么必须用队列而不能用栈？

链表相比数组的优势和劣势分别是什么？在竞赛中什么时候该用链表？

二叉搜索树的中序遍历有什么特殊性质？为什么它如此重要？

STL 的 priority_queue 默认是大顶堆还是小顶堆？如何改变优先级？

set 和 map 的底层实现是什么？它们的操作复杂度是多少？

二、核心概念详解

4.1 栈（Stack）

4.1.1 栈的原理

栈是一种后进先出（Last In, First Out, LIFO）的数据结构。就像一摞盘子：最后放上去的盘子最先被取走。

栈只允许在一端（栈顶）进行插入（push）和删除（pop）操作。核心操作：

操作功能时间复杂度
push(x)将 x 压入栈顶O(1)
pop()弹出栈顶元素O(1)
top()查看栈顶元素O(1)
empty()判断栈是否为空O(1)
size()返回栈中元素个数O(1)

4.1.2 STL stack 的使用

cpp
#include <stack>

stack<int> st;
st.push(1);    // 栈：[1]
st.push(2);    // 栈：[1, 2]
st.push(3);    // 栈：[1, 2, 3]

printf("%d\n", st.top());  // 3（栈顶）
st.pop();                   // 弹出 3，栈：[1, 2]
printf("%d\n", st.top());  // 2
printf("%d\n", st.size()); // 2

4.1.3 栈的应用：括号匹配

括号匹配是栈最经典的应用之一。遇到左括号入栈，遇到右括号检查栈顶是否匹配：

cpp
#include <cstdio>
#include <stack>
#include <cstring>

bool isValid(const char *s) {
    stack<char> st;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
            st.push(s[i]);
        } else {
            if (st.empty()) return false;
            if (s[i] == ')' && st.top() != '(') return false;
            if (s[i] == ']' && st.top() != '[') return false;
            if (s[i] == '}' && st.top() != '{') return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    char s[1005];
    scanf("%s", s);
    printf("%s\n", isValid(s) ? "YES" : "NO");
    return 0;
}

解析：如果括号序列合法，最终栈一定为空。如果任何时候栈为空却遇到了右括号，或者最后栈不为空，都说明括号不匹配。

4.1.4 单调栈

单调栈是栈的一个重要变体：栈中元素保持单调递增或递减。它常用于解决"下一个更大元素"问题：

cpp
#include <cstdio>
#include <stack>
using namespace std;

int a[100005], ans[100005];
int n;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    stack<int> st;  // 存下标，栈中下标对应的值单调递减
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] <= a[i])
            st.pop();
        ans[i] = st.empty() ? -1 : a[st.top()];
        st.push(i);
    }
    
    for (int i = 0; i < n; i++)
        printf("%d%c", ans[i], " \n"[i == n - 1]);
    return 0;
}

4.2 队列（Queue）

4.2.1 队列的原理

队列是一种先进先出（First In, First Out, FIFO）的数据结构。就像排队买票：先来的先服务。

操作功能时间复杂度
push(x)将 x 加入队尾O(1)
pop()弹出队首元素O(1)
front()查看队首元素O(1)
empty()判断队列是否为空O(1)
size()返回队列中元素个数O(1)

4.2.2 队列的应用：BFS

广度优先搜索（BFS）是队列最经典的应用。BFS 按层次遍历图或树，天然需要 FIFO 的顺序：

cpp
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

vector<int> adj[1005];
int dist[1005];
int n;

void bfs(int start) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

4.2.3 双端队列（Deque）

双端队列允许在两端进行插入和删除操作。STL 的 deque 以及 priority_queue 都是基于它：

cpp
#include <deque>

deque<int> dq;
dq.push_back(1);    // 尾部插入
dq.push_front(0);   // 头部插入
dq.pop_back();       // 尾部弹出
dq.pop_front();      // 头部弹出

双端队列在滑动窗口问题中有重要应用，可以在 O(n) 时间内求出每个窗口内的最大值/最小值。

4.3 优先队列（Priority Queue）

4.3.1 原理

优先队列不是按 FIFO 顺序出队，而是按优先级出队——优先级最高的元素最先出队。默认实现是堆（heap）。

操作功能时间复杂度
push(x)插入元素O(log n)
pop()弹出最高优先级元素O(log n)
top()查看最高优先级元素O(1)

4.3.2 STL priority_queue

cpp
#include <queue>
#include <vector>

// 默认大顶堆（最大值在顶部）
priority_queue<int> pq1;
pq1.push(3); pq1.push(1); pq1.push(4);
printf("%d\n", pq1.top());  // 4

// 小顶堆（最小值在顶部）
priority_queue<int, vector<int>, greater<int>> pq2;
pq2.push(3); pq2.push(1); pq2.push(4);
printf("%d\n", pq2.top());  // 1

4.3.3 应用：Top-K 问题

从 n 个数中找出最大的 k 个，使用小顶堆维护当前最大的 k 个元素：

cpp
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    priority_queue<int, vector<int>, greater<int>> pq;  // 小顶堆
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();  // 维护大小为 k
    }
    printf("Top %d:\n", k);
    while (!pq.empty()) {
        printf("%d\n", pq.top());
        pq.pop();
    }
    return 0;
}

复杂度分析：每次 push/pop 是 O(log k)，总共 n 次操作，总时间复杂度 O(n log k)，远优于排序的 O(n log n)。

4.4 链表

4.4.1 链表的原理

链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的元素在内存中不必连续存储：

cpp
struct Node {
    int data;
    Node *next;
    Node(int d) : data(d), next(nullptr) {}
};
操作数组链表
按位置访问O(1)O(n)
在头部插入O(n)O(1)
在尾部插入O(1)O(1)（有尾指针）
在中间插入O(n)O(n)（需找到位置）
删除元素O(n)O(1)（已知位置）

4.4.2 竞赛中的链表

在竞赛中，链表的使用频率不如数组和 STL 容器高。但在某些场景下，链表不可替代：

  • 需要频繁在中间插入/删除，且已有指向该位置的指针
  • 实现邻接表存储图（用数组模拟的"链表"更常见）
cpp
// 数组模拟链表（竞赛中更常用，避免指针）
int head[1005], nxt[1005], val[1005], cnt = 0;

void insert(int head_idx, int v) {
    val[++cnt] = v;
    nxt[cnt] = head[head_idx];
    head[head_idx] = cnt;
}

void traverse(int head_idx) {
    for (int i = head[head_idx]; i; i = nxt[i])
        printf("%d ", val[i]);
    printf("\n");
}

4.5 树

4.5.1 二叉树

树是层次化的数据结构。二叉树是每个节点最多有两个子节点的树：

cpp
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

4.5.2 二叉搜索树（BST）

二叉搜索树满足：对于每个节点，左子树中所有值 < 该节点值 < 右子树中所有值。

中序遍历 BST 会得到一个有序序列——这是 BST 最重要的性质。

操作平均复杂度最坏复杂度
查找O(log n)O(n)
插入O(log n)O(n)
删除O(log n)O(n)

4.5.3 STL 中的树

STL 的 set 和 map 底层都是红黑树（一种平衡 BST），保证操作在 O(log n) 内完成：

cpp
#include <set>
#include <map>

set<int> s;
s.insert(3); s.insert(1); s.insert(4); s.insert(1);  // 重复元素被忽略
for (int x : s) printf("%d ", x);  // 1 3 4（自动有序）

map<string, int> m;
m["alice"] = 90;
m["bob"] = 85;
printf("%d\n", m["alice"]);  // 90

三、实战案例

3.1 案例一：用栈实现表达式求值

问题描述：计算只包含 +、-、*、/ 和括号的表达式。

cpp
#include <cstdio>
#include <stack>
#include <cctype>
#include <cstring>
using namespace std;

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

double apply(double a, double b, char op) {
    if (op == '+') return a + b;
    if (op == '-') return a - b;
    if (op == '*') return a * b;
    if (op == '/') return a / b;
    return 0;
}

double evaluate(const char *s) {
    stack<double> nums;
    stack<char> ops;
    int i = 0;
    while (s[i]) {
        if (isdigit(s[i])) {
            double num = 0;
            while (isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            nums.push(num);
        } else if (s[i] == '(') {
            ops.push(s[i]);
            i++;
        } else if (s[i] == ')') {
            while (ops.top() != '(') {
                double b = nums.top(); nums.pop();
                double a = nums.top(); nums.pop();
                char op = ops.top(); ops.pop();
                nums.push(apply(a, b, op));
            }
            ops.pop();
            i++;
        } else {
            while (!ops.empty() && precedence(ops.top()) >= precedence(s[i])) {
                double b = nums.top(); nums.pop();
                double a = nums.top(); nums.pop();
                char op = ops.top(); ops.pop();
                nums.push(apply(a, b, op));
            }
            ops.push(s[i]);
            i++;
        }
    }
    while (!ops.empty()) {
        double b = nums.top(); nums.pop();
        double a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        nums.push(apply(a, b, op));
    }
    return nums.top();
}

int main() {
    char s[1005];
    scanf("%s", s);
    printf("%.2f\n", evaluate(s));
    return 0;
}

3.2 案例二：BFS 求无权图最短路

cpp
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

vector<int> adj[1005];
int dist[1005], prev_node[1005];
int n, m;

void bfs(int s) {
    memset(dist, -1, sizeof(dist));
    memset(prev_node, -1, sizeof(prev_node));
    queue<int> q;
    dist[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                prev_node[v] = u;
                q.push(v);
            }
        }
    }
}

void print_path(int t) {
    if (t == -1) return;
    print_path(prev_node[t]);
    printf("%d ", t);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs(1);
    printf("Distance to %d: %d\n", n, dist[n]);
    printf("Path: ");
    print_path(n);
    printf("\n");
    return 0;
}

四、本章小结

本章介绍了四种基础数据结构及其 STL 实现：

栈（LIFO）：括号匹配、表达式求值、单调栈、DFS 的模拟。

队列（FIFO）：BFS、拓扑排序、滑动窗口。

优先队列：按优先级出队，用于 Top-K 问题、Dijkstra 最短路、Huffman 编码。

链表：动态插入删除，数组模拟链表是竞赛中的常用技巧。

树：层次化结构，BST 的中序遍历有序，STL 的 set/map 基于红黑树。

选择合适的数据结构是解决问题的第一步。在竞赛中，STL 容器是你的利器——熟练掌握它们，才能在算法实现时游刃有余。

五、思考与练习

思考题

如何用两个栈实现一个队列？如何用两个队列实现一个栈？

为什么 priority_queue 默认是大顶堆？这与堆的实现有什么关系？

vector 和 list（双向链表）各自的优缺点是什么？在竞赛中如何选择？

为什么 BST 在最坏情况下会退化为 O(n)？如何避免？

编程练习

最小栈：设计一个支持 push、pop、top 和 getMin（获取最小值）操作的栈，所有操作 O(1)。

用队列实现栈：仅使用队列的基本操作实现栈的所有功能。

合并 K 个有序链表：使用优先队列高效合并 k 个有序链表。

二叉树的层序遍历：使用队列实现二叉树的按层遍历。

4/8基础数据
0%