单链表 —— 模板题 AcWing 826. 单链表
用来写邻接表（用来存储图和树）
双链表 —— 模板题 AcWing 827. 双链表
用来优化某些问题
栈 —— 模板题 AcWing 828. 模拟栈
队列 —— 模板题 AcWing 829. 模拟队列
1. 普通队列：
2. 循环队列
单调栈 —— 模板题 AcWing 830. 单调栈
单调队列 —— 模板题 AcWing 154. 滑动窗口
KMP —— 模板题 AcWing 831. KMP字符串
Trie树 —— 模板题 AcWing 835. Trie字符串统计
高效存储和查询字符串
并查集 —— 模板题 AcWing 836. 合并集合, AcWing 837. 连通块中点的数量
- 将两个集合合并
- 询问两个元素是否在一个集合当中
问题1：如何判断树根：
if(p[x] == x)问题2：如何求x的集合编号:
while(p[x] != x) x = p[x] 问题3：如何合并两个集合：p[x] 是 x的集合编号，p[y]是y的集合编号
p[x] = y优化：采用路径压缩，按秩合并一般不用
堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
- 插入一个数
heap[++size]=x; up(size)
- 求集合当中的最小值
heap[1]
- 删除最小值
heap[1] = heap[size]; size--; down(1)
- 删除任意一个元素
heap[k] = heap[size]; size--; down(k); up(k)
- 修改任意一个元素
heap[k] = x; down(k); up(k)