一、线性表基础定义

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

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

---

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

1. 底层原理

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

2. 核心 API 与时间复杂度

操作	接口	时间复杂度	说明
尾插	push_back(x)	均摊 O (1)	扩容时为 O (n)，均摊后为常数
尾删	pop_back()	O(1)	仅修改尾指针，无内存释放
随机访问	v[i] / at(i)	O(1)	at() 会做越界检查，[] 无检查
插入（指定位置）	insert(pos, x)	O(n)	需移动后续元素腾出位置
删除（指定位置）	erase(pos)	O(n)	需移动后续元素覆盖删除位置
扩容优化	reserve(n)	O(1)	预分配内存，避免多次扩容开销

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 与时间复杂度

操作	接口	时间复杂度	说明
入栈	push(x)	O(1)	栈顶插入
出栈	pop()	O(1)	栈顶删除，无返回值
取栈顶	top()	O(1)	仅读取栈顶元素
判空	empty()	O(1)	判断栈中是否有元素

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 与时间复杂度

操作	接口	时间复杂度	说明
入队	push(x)	O(1)	队尾插入
出队	pop()	O(1)	队头删除，无返回值
取队头	front()	O(1)	读取队头元素
取队尾	back()	O(1)	读取队尾元素
判空	empty()	O(1)	判断队列是否为空

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，避免空指针异常。

---

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

数据结构	存储方式	随机访问	插入 / 删除（指定位置）	核心特性	适用场景
数组 / Vector	连续内存	O(1)	O(n)	随机访问高效	数据规模已知、频繁查询、矩阵运算
栈	连续 / 非连续	不支持	O (1)（仅栈顶）	后进先出（LIFO）	括号匹配、递归模拟、表达式求值
队列	连续 / 非连续	不支持	O (1)（队头 / 队尾）	先进先出（FIFO）	BFS、排队模拟、进程调度
链表	非连续内存	O(n)	O(1)	插入删除高效	频繁增删、数据规模未知、动态任务管理

---

七、线性表学习进阶路线

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