线性表

线性表分类

概念

由一系列节点组成的线性数据结构，节点包含数据域和指针域（存储下一个 / 上一个节点的地址），节点在内存中不连续存储，通过指针关联

注：对于搜索的需求，可以参阅 “红黑树”、“散列表”等数据结构
特点
- 动态扩容（无需预分配内存）
- 插入 / 删除效率高（O (1)，需已知前驱节点）
- 访问效率低（O (n)，需从头遍历）
链表的分类
- 单向、双向
- 不带哨兵位、带哨兵位
- 循环、非循环
算法竞赛中的链表

new和delete是非常耗时的操作，在算法竞赛中，一般不会用list这个容器，也不会用new和delete去模拟实现一个链表，而是用静态数组模拟实现一个链表

概念

一种遵循“后进先出（LIFO，Last In First Out）”原则的线性数据结构，仅允许在一端（栈顶）进行插入和删除操作
核心术语
- 栈顶：允许操作的一端（数据进出的端口）
- 栈底：固定的一端（不允许直接操作）
- 压栈（Push）：在栈顶插入元素
- 弹栈（Pop）：从栈顶删除并返回元素
- 栈空：不含任何元素的状态
- 栈满：元素数量达到最大容量（仅固定大小栈有此概念）
栈的两种实现方式
- 顺序栈（数组实现）
  - 结构：用数组存储元素，通过栈顶指针（索引）标记栈顶位置
  - 特点：实现简单，访问效率高（O(1)）；容量固定，扩容成本高
- 链栈（链表实现）
  - 结构：用链表存储元素，头节点作为栈顶，每次操作头节点
  - 特点：动态扩容（无栈满问题）；内存开销略大（需存储指针）
基本操作及时间复杂度
- 压栈（Push）：O(1)
- 弹栈（Pop）：O(1)
- 查看栈顶元素（Top）：O(1)
- 判断栈空（IsEmpty）：O(1)
典型应用场景
- 函数调用栈（保存函数返回地址、局部变量）
- 表达式求值（如后缀表达式计算）
- 括号匹配校验（判断括号是否成对闭合）
- 撤销操作（如文本编辑器的Ctrl+Z）
- 深度优先搜索（DFS）的递归实现

概念

遵循 “先进先出（FIFO，First In First Out）” 的线性数据结构，仅允许在队尾插入元素、队头删除元素，类似现实中 “排队” 场景。
核心术语
- 队头（Front）：删除元素的一端（数据 “出队” 端口）
- 队尾（Rear）：插入元素的一端（数据 “入队” 端口）
- 入队（Enqueue）：队尾添加元素
- 出队（Dequeue）：队头删除并返回元素
- 队空：无元素状态；队满：元素达最大容量（仅固定大小队列有）
队列的两种实现方式
- 顺序队列（数组实现）
- 链队列（链表实现）
基本操作及时间复杂度
- 入队（Enqueue）：O (1)
- 出队（Dequeue）：O (1)
- 查看队头（GetFront）：O (1)
- 判断队空（IsEmpty）：O (1)
- 判断队满（IsFull）：O (1)（仅顺序队列）
典型应用场景
- 任务调度：操作系统进程调度、打印机任务队列（先提交先执行）
- 数据缓冲：网络数据包缓冲、IO 与 CPU 间缓冲（平衡速度差异）
- 广度优先搜索（BFS）：二叉树层序遍历、图的最短路径搜索
- 消息队列：分布式系统异步通信（消息按发送顺序消费）

与栈的核心区别