【数据结构精讲】线性表四大核心：数组 / Vector、栈、队列、链表（原理 + 模板 + 避坑 + 选型）

一、线性表基础定义

线性表是n 个数据元素的有限序列，元素之间满足「一对一」的前驱后继关系，除首尾元素外，每个元素有且仅有一个前驱和一个后继。

本文聚焦线性表的四大核心实现：数组 / Vector、栈、队列、链表，从底层原理、工程模板、典型应用、避坑要点四个维度系统梳理，内容均为可直接落地的干货。

二、数组与动态数组（Vector）

1. 底层原理

• 静态数组：编译期分配连续内存，长度固定，支持O(1)随机访问，但无法动态扩容。
• 动态数组（std::vector）：C++ 标准库实现的动态数组，底层为连续内存，支持自动扩容（扩容因子通常为 1.5/2 倍），兼顾随机访问与动态存储。

2. 核心 API 与时间复杂度

3. 工程模板（含二维数组）

#include <vector> using namespace std; // 一维vector基础操作 vector<int> v; v.reserve(100); // 预分配100个元素空间，优化扩容 v.push_back(1); // 尾插 v.pop_back(); // 尾删 for (int x : v) { /* 范围for遍历 */ } // 二维vector（模拟表格/矩阵） vector<vector<int>> grid(5, vector<int>(5, 0)); // 5×5初始化为0 grid[0][1] = 10; // 随机访问二维元素

4. 典型应用与避坑

• 应用场景：点名问题、寄包柜模拟、批量数据存储与遍历、矩阵运算。
• 避坑要点：
  1. 越界访问：v[i]需保证i < v.size()，否则行为未定义。
  2. 迭代器失效：insert/erase操作会使后续迭代器失效，需更新迭代器。
  3. 扩容开销：频繁push_back大数据时，务必先reserve预分配内存。

三、栈（Stack）

1. 底层原理

栈是受限线性表，遵循「后进先出（LIFO）」原则，仅允许在栈顶进行插入（入栈）和删除（出栈）操作，底层可由数组 / Vector 或链表实现。

2. 核心 API 与时间复杂度

3. 手动实现模板（数组版・静态）

const int MAXN = 1005; int st[MAXN]; int top = 0; // 栈顶指针，初始为0表示空栈 // 入栈 void push(int x) { st[++top] = x; } // 出栈 void pop() { if (!empty()) top--; } // 取栈顶 int get_top() { return st[top]; } // 判空 bool empty() { return top == 0; }

4. 动态数组实现栈（Vector・推荐）

优点：无容量上限、自动扩容、代码极简、竞赛 / 教学首选

#include <vector> using namespace std; vector<int> st; // 入栈 void push(int x) { st.push_back(x); } // 出栈 void pop() { if (!st.empty()) st.pop_back(); } // 获取栈顶 int top() { return st.back(); } // 判空 bool empty() { return st.empty(); } // 获取元素个数 int size() { return st.size(); }

5. 典型应用与避坑

• 应用场景：
  1. 括号匹配：判断字符串中括号是否成对合法。
  2. 后缀表达式求值：逆波兰表达式的计算核心结构。
  3. 递归转非递归：模拟函数调用栈，实现 DFS 等递归算法。
• 避坑要点：
  1. 空栈访问：top()/pop()前必须判断!empty()，否则程序崩溃。
  2. 栈溢出：数组实现的栈需控制最大容量，避免栈顶指针越界。

四、队列（Queue）

1. 底层原理

队列是受限线性表，遵循「先进先出（FIFO）」原则，仅允许在队尾插入（入队）、队头删除（出队），底层可由数组 / Vector 或链表实现。

2. 核心 API 与时间复杂度

3. 手动实现模板（循环队列版・静态）

const int MAXN = 1005; int q[MAXN]; int front = 0, rear = 0; // 入队 bool push(int x) { if ((rear + 1) % MAXN == front) return false; rear = (rear + 1) % MAXN; q[rear] = x; return true; } // 出队 bool pop() { if (empty()) return false; front = (front + 1) % MAXN; return true; } // 判空 bool empty() { return front == rear; } // 取队头 int get_front() { return q[(front + 1) % MAXN]; }

4. 动态数组实现队列（Vector 版）

适合教学演示，直观易懂

#include <vector> using namespace std; vector<int> q; // 队尾入队 void push(int x) { q.push_back(x); } // 队头出队 void pop() { if (!q.empty()) q.erase(q.begin()); } // 获取队头 int front() { return q[0]; } // 获取队尾 int back() { return q.back(); } // 判空 bool empty() { return q.empty(); }

5. 高效动态队列（deque 版・工程推荐）

#include <deque> using namespace std; deque<int> q; // 入队 O(1) q.push_back(x); // 出队 O(1) q.pop_front(); // 队头 q.front(); // 队尾 q.back();

6. 典型应用与避坑

• 应用场景：
  1. 广度优先搜索（BFS）：树 / 图的层序遍历核心结构。
  2. 模拟排队问题：超市结账、进程调度、消息队列。
  3. 约瑟夫问题：循环队列的经典应用。
• 避坑要点：
  1. 空队列访问：front()/pop()前必须判断!empty()，否则程序崩溃。
  2. 假溢出问题：普通数组队列易出现「队尾满但队头有空」的假溢出，循环队列通过取模运算解决。

五、链表（Linked List）

1. 底层原理

链表是非连续内存存储的线性表，通过指针连接节点，每个节点包含数据域和指针域。核心优势为插入 / 删除操作O(1)时间复杂度，劣势为随机访问需O(n)遍历。常见分类：单链表、双向链表、循环链表。

2. 核心操作模板（单链表）

struct Node { int data; Node* next; Node(int x) : data(x), next(nullptr) {} }; Node* head = nullptr; // 头插法（O(1)） void insert_head(int x) { Node* newNode = new Node(x); newNode->next = head; head = newNode; } // 指定值删除（O(n)） void delete_node(int x) { Node *cur = head, *pre = nullptr; while (cur && cur->data != x) { pre = cur; cur = cur->next; } if (!cur) return; if (!pre) head = cur->next; else pre->next = cur->next; delete cur; } // 遍历 void traverse() { Node* cur = head; while (cur) { // 处理 cur->data cur = cur->next; } }

3. 典型应用与避坑

• 应用场景：
  1. 频繁插入删除场景：排队记录、动态任务调度。
  2. 多项式运算：用链表存储多项式的项，实现加减运算。
  3. 优化约瑟夫问题：循环链表实现，无需移动元素。
• 避坑要点：
  1. 内存泄漏：手动实现链表需用delete释放删除的节点。
  2. 断链问题：插入 / 删除操作时指针指向错误，导致链表断裂。
  3. 空指针访问：遍历链表时需判断cur != nullptr，避免空指针异常。

六、四大线性表对比与选型指南

七、线性表学习进阶路线

1. 基础阶段：掌握数组 / Vector 的 API 与迭代器，理解线性表的基本概念。
2. 受限线性表：通过栈和队列的生活化案例，理解 LIFO/FIFO 特性，掌握 STL 实现与手动实现。
3. 进阶阶段：掌握链表的节点定义、插入删除操作，理解链表与数组的优劣对比。
4. 应用阶段：结合 BFS、DFS、括号匹配、约瑟夫问题等真题，巩固四大线性表的实际应用。