数据结构

[生产常用 数据结构](https://totoro-jam.github.io/battle-tested-patterns/zh/patterns/ring-buffer/)

# ADT
| 底层数据结构 | 常构建的 ADT | 核心操作（查询 / 插入 / 删除等） |
| :--- | :--- | :--- |
| 数组 / 动态数组 | List | 按索引查询、按值查询、尾部插入、任意位置插入、按索引删除、按值删除 |
| 数组 / 动态数组 | Stack | 查询栈顶、插入（push）、删除（pop） |
| 数组 / 动态数组 | Queue | 查询队首/队尾、尾部插入（enqueue）、头部删除（dequeue） |
| 数组 / 动态数组 | Deque | 查询两端、两端插入、两端删除 |
| 数组 / 动态数组 | Buffer | 查询当前读写位置、插入（写）、删除（读 / 覆盖） |
| 链表 | List | 按值查询、按位置查询、任意位置插入、任意位置删除 |
| 链表 | Stack | 查询栈顶、头部插入、头部删除 |
| 链表 | Queue | 查询队首/队尾、尾部插入、头部删除 |
| 链表 | Deque | 查询两端、两端插入、两端删除 |
| 链表 | Adjacency List | 查询某顶点的所有邻接点、插入边、删除边 |
| 哈希表 | Map | 按键查询、插入键值对、删除键值对 |
| 哈希表 | Set | 查询元素是否存在、插入元素、删除元素 |
| 哈希表 | Multiset | 查询计数、插入元素、删除一个或全部重复元素 |
| 哈希表 | Cache | 查询缓存项、插入 / 更新、按淘汰策略删除 |
| 二叉搜索树 / 平衡树 | Ordered Map | 按键查询、范围查询、插入、删除、前驱 / 后继查询 |
| 二叉搜索树 / 平衡树 | Ordered Set | 查询元素、范围查询、插入、删除、前驱 / 后继 |
| 二叉搜索树 / 平衡树 | 优先队列（理论） | 查询最值、插入、删除最值 |
| 堆 | Priority Queue | 查询最值（top）、插入（push）、删除最值（pop） |
| 并查集 | Union-Find | 查询所属集合（find）、合并两个集合（union）、判断是否连通 |

## 定长数组
```c
int a[5] = {1,2,3,4,5};
```
## 动态数组

上一篇

下一篇