1. 基础数据结构概述

• 数组
• 链表
• 栈
• 队列
• 堆、加强堆
• 树
  • 二叉树
  • 完全二叉树
  • 搜索二叉树
  • 平衡二叉树
• 并查集
• 图
• 滑动窗口
• 单调栈
• 哈希表
• 有序表
• 红黑树

2. 基础数据结构详解

1. 数组

2. 链表

概念：

• 单向链表
• 双向链表

相关算法：

• 反转单链表和双链表
• 删除给定值
• 快慢指针
• 使用容器

3. 栈

相关算法：

• 使用数组和双向链表实现
• 实现特殊的栈，实现返回栈中最小元素的功能 O(1) push pop getMin

4. 队列

相关算法：

• 使用数组和双向链表实现

5. 堆

概念：

堆是完全二叉树

相关算法：

• heapinsert和heapify

6. 树

概念：

• 二叉树
• 完全二叉树：除最后一层外所有层的都是满的，且最后一层由左向右排列，可以不满，但不能有空位。
• 搜索二叉树：头节点的值大于左子节点，小于右子节点
• 平衡二叉树：所有节点的左右子树高度差不超过1

相关算法：

• 树形DP问题
• 前、中、后序遍历，递归序
• 判断二叉树是否是完全二叉树、搜索二叉树、平衡二叉树

7. 并查集

概念：

• 支持合并和查询的集合结构

相关算法：

• 并查集实现
• 并查集的应用

8. 图

相关算法：

• 图的实现
• 宽度优先遍历和深度优先遍历
• 两个最小生成树算法
• 拓扑排序

9. 滑动窗口

概念：

• 滑动窗口是一种想象出来的数据结构，有左边界L和右边界R
  • 在数组或者字符串或者一个序列上，记为S，窗口就是S[L...R]这一部分
  • L往右滑意味着一个样本出了窗口，R往右滑意味着一个样本进了窗口
  • L和R都只能往右滑

相关算法：

• 滑动窗口相关问题

10. 单调栈

概念：

• 准备一个栈，栈底往上由小到大
  • 数组压栈时，小于栈顶，栈顶弹出，栈顶元素形成信息：
    • 此时，栈下面的是左边离它距离近且小的值，数组的数是其右边离它近且小的值

相关算法：

• 单调栈的实现
• 单调栈相关问题

11. 哈希表

12. 有序表

13. 红黑树