基础数据结构

概述

在算法竞赛中，数据结构是算法的基础，合理选择和使用数据结构可以极大地提升解题效率。本文介绍ACM竞赛中最常用的基础数据结构，包括数组、链表、栈、队列以及它们在STL中的实现和应用。

数组

基本概念

【数组】是最基本的数据结构，它在内存中连续存储相同类型的元素，通过索引可以快速访问任何位置的元素。

特点

  • 随机访问：O(1)时间复杂度
  • 插入/删除操作：O(n)时间复杂度（需要移动元素）
  • 内存连续，空间局部性好，缓存命中率高

实现示例

// 一维数组
int arr[100]; // 声明一个大小为100的整型数组

// 二维数组
int matrix[10][10]; // 声明一个10×10的二维数组

// 动态数组
vector<int> v; // C++ STL中的动态数组
v.push_back(10); // 向末尾添加元素
int x = v[0]; // 通过索引访问元素

应用场景

  1. 存储有序数据，如排序算法
  2. 实现其他数据结构（栈、队列等）
  3. 动态规划中的状态存储
  4. 图的邻接矩阵表示

常见易错点

  • 数组越界：访问超出数组范围的元素
  • 未初始化：使用前未初始化数组元素
  • 内存限制：静态数组过大可能导致栈溢出

链表

基本概念

【链表】是由节点组成的线性集合，每个节点包含数据和指向下一个节点的指针。

特点

  • 随机访问：O(n)时间复杂度（需要遍历）
  • 插入/删除操作：O(1)时间复杂度（如果已知位置）
  • 内存不连续，动态分配，空间利用更灵活

实现示例

// 简单链表节点定义
struct Node {
    int data;
    Node* next;
    Node(int x) : data(x), next(nullptr) {}
};

// 创建链表
Node* createList() {
    Node* head = new Node(1); // 头节点
    Node* p = head;

    for (int i = 2; i <= 5; i++) {
        p->next = new Node(i);
        p = p->next;
    }

    return head;
}

// C++ STL中的链表
list<int> lst;
lst.push_back(10); // 添加到末尾
lst.push_front(5); // 添加到开头

应用场景

  1. 需要频繁插入/删除操作的场景
  2. 实现其他数据结构（如邻接表表示图）
  3. 内存不够连续时的数据存储
  4. 某些特殊算法（如多项式加法）

常见易错点

  • 空指针访问：未检查链表是否为空
  • 内存泄漏：删除节点时未释放内存
  • 丢失链表：修改指针时断开链接

栈

基本概念

【栈】是一种后进先出(LIFO)的数据结构，只允许在一端（栈顶）进行插入和删除操作。

特点

  • 插入/删除：O(1)时间复杂度
  • 只能访问栈顶元素
  • 具有"记忆"功能，常用于需要回溯的场景

实现示例

// 数组实现栈
class ArrayStack {
private:
    int data[1000];
    int top;
public:
    ArrayStack() : top(-1) {}

    void push(int x) {
        if (top < 999) data[++top] = x;
    }

    int pop() {
        if (top >= 0) return data[top--];
        return -1; // 栈空
    }

    bool empty() {
        return top == -1;
    }
};

// C++ STL中的栈
stack<int> s;
s.push(10);  // 入栈
int x = s.top();  // 获取栈顶元素
s.pop();  // 出栈

应用场景

  1. 函数调用与递归实现
  2. 表达式求值与语法解析
  3. 深度优先搜索(DFS)
  4. 括号匹配问题
  5. 单调栈解决直方图最大矩形等问题

常见易错点

  • 栈溢出：超出栈容量限制
  • 空栈操作：在栈为空时执行pop或top操作
  • 忘记清空栈：多次使用同一个栈时未清空

队列

基本概念

【队列】是一种先进先出(FIFO)的数据结构，允许在一端（队尾）添加元素，在另一端（队首）删除元素。

特点

  • 插入/删除：O(1)时间复杂度
  • 只能访问队首和队尾元素
  • 适合处理需要按顺序处理的任务

实现示例

// 数组实现循环队列
class CircularQueue {
private:
    int data[1000];
    int front, rear, size;
public:
    CircularQueue() : front(0), rear(0), size(0) {}

    void push(int x) {
        if (size < 1000) {
            data[rear] = x;
            rear = (rear + 1) % 1000;
            size++;
        }
    }

    int pop() {
        if (size > 0) {
            int x = data[front];
            front = (front + 1) % 1000;
            size--;
            return x;
        }
        return -1; // 队列空
    }

    bool empty() {
        return size == 0;
    }
};

// C++ STL中的队列
queue<int> q;
q.push(10);  // 入队
int x = q.front();  // 获取队首元素
q.pop();  // 出队

应用场景

  1. 广度优先搜索(BFS)
  2. 任务调度
  3. 缓冲区实现
  4. 树的层序遍历
  5. 双向队列实现滑动窗口算法

常见易错点

  • 队列满/空判断错误：尤其是循环队列中
  • 空队列操作：在队列为空时执行pop或front操作
  • 数组实现时的索引计算错误

STL容器的使用技巧

C++的STL提供了高效实现的数据结构，在ACM竞赛中广泛使用：

vector (动态数组)

vector<int> v = {1, 2, 3};
v.push_back(4);  // 添加元素
v.pop_back();    // 移除最后一个元素
sort(v.begin(), v.end());  // 排序
int size = v.size();  // 获取大小

list (双向链表)

list<int> lst;
lst.push_back(1);   // 在尾部添加
lst.push_front(0);  // 在头部添加
lst.insert(++lst.begin(), 5);  // 在指定位置插入

stack (栈)

stack<int> s;
s.push(1);      // 入栈
s.push(2);
int top = s.top();  // 查看栈顶
s.pop();        // 出栈

queue (队列)

queue<int> q;
q.push(1);          // 入队
q.push(2);
int front = q.front();  // 查看队首
q.pop();            // 出队

deque (双端队列)

deque<int> dq;
dq.push_back(1);    // 在尾部添加
dq.push_front(0);   // 在头部添加
dq.pop_back();      // 从尾部移除
dq.pop_front();     // 从头部移除

性能对比与选择建议

数据结构 随机访问 头部插入/删除 尾部插入/删除 中间插入/删除 内存开销
数组 O(1) O(n) O(1)/O(n) O(n) 低
链表 O(n) O(1) O(1) O(1)* 高
vector O(1) O(n) O(1)均摊 O(n) 中
list O(n) O(1) O(1) O(1) 高
deque O(1) O(1)均摊 O(1)均摊 O(n) 中

*前提是已知插入/删除位置的指针

选择建议

  1. 频繁随机访问，较少修改：使用数组或vector
  2. 频繁在两端操作：使用deque
  3. 频繁在中间插入/删除：使用list
  4. 需要频繁查找特定值：考虑使用set或map
  5. 栈操作：使用stack
  6. 队列操作：使用queue
  7. 优先队列：使用priority_queue

竞赛中的实用技巧

  1. 数组预分配：在使用数组时，预估并分配足够大的空间，避免运行时重新分配

    const int MAXN = 1e5 + 5;  // 常见竞赛做法，+5是为了避免边界问题
int arr[MAXN];

  2. 加速输入输出：

    ios::sync_with_stdio(false);
cin.tie(nullptr);

  3. 二维数组使用一维表示：减少缓存未命中

    int arr[MAXN * MAXN];
// 访问(i,j)位置：arr[i * n + j]

  4. 循环不变量的提前计算：

    for(int i = 0; i < n; ++i) {
    // 如果v.size()不变，提前计算
    int size = v.size();
    for(int j = 0; j < size; ++j) {
        // ...
    }
}

典型题目分析

题目1：括号匹配

问题描述：给定一个只包含'('和')'的字符串，判断是否是有效的括号匹配。

思路分析：使用栈，遇到左括号压入栈，遇到右括号时检查栈顶是否为匹配的左括号。

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') {
            st.push(c);
        } else if (!st.empty() && st.top() == '(') {
            st.pop();
        } else {
            return false;
        }
    }
    return st.empty(); // 所有括号都匹配完毕
}

时间复杂度：O(n)，其中n是字符串长度 空间复杂度：O(n)，最坏情况下栈的大小

题目2：滑动窗口最大值

问题描述：给定一个数组和一个窗口大小k，求滑动窗口在数组上移动时的最大值序列。

思路分析：使用双端队列，保持队列中的元素单调递减。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // 存放索引，而非数值

    for (int i = 0; i < nums.size(); i++) {
        // 移除超出窗口范围的元素
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 移除队列中所有小于当前元素的值（保持单调性）
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // 当窗口形成后，记录最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

时间复杂度：O(n)，每个元素最多入队出队一次 空间复杂度：O(k)，双端队列的大小

小结

基础数据结构是算法竞赛的基石，掌握了数组、链表、栈和队列的特性和应用场景，以及C++ STL中相关容器的使用，可以帮助你高效地解决许多问题。在实际比赛中，要根据问题特点选择合适的数据结构，这往往是解题的关键一步。

记住：没有最好的数据结构，只有最适合当前问题的数据结构。理解它们的时间复杂度和空间特性，才能在竞赛中游刃有余。