数据结构

栈

• js 中没有栈，我们要使用一个数组来模拟一个栈。
• 先进后出的场景。
• js 中的任务栈。

---

队列

• js 中没有队列，我们要使用数组来模拟一个队列。
• 先进先出的场景。
• js 中的任务队列。

---

链表

• js 中没有链表，我们要使用 object 来模拟一个链表。
• js 中的原型链

---

集合

• ES6 中存在集合，为 Set。
• 一种无序且唯一的结构。

---

字典

• ES6 中存在字典，为 Map。
• 存储唯一值，用键值对表示。

---

树

• 一种分层数据的抽象模型。
• js 中的：DOM 树，级联选择...
• 对应的遍历
  • 深度遍历——先序，中序，后序。
  • 广度遍历。

---

图

• 图是网络结构的抽象模型。
• js 中没有图，可以使用 object 和 Array 来模拟。
  • 邻接矩阵。
  • 邻接表。
• 对应的遍历
  • 深度优先。
  • 广度优先。

---

堆

• 堆是一种特殊的完全二叉树
• 所有节点都大于等于（最大堆）或者小于等于（最小堆）他的子节点。
• js 通常用数组表示堆
  • 左侧子节点的位置为 2 * index + 1
  • 右侧子节点的位置为 2 * index + 2
  • 父节点的位置是 （index - 1） / 2

• 对应的方法
  • 实现最小堆

---

排序

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序

---

搜索

• 顺序搜索
• 二分搜索

---

算法思想

• 分而治之
  • 他将问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题。
• 动态规划
  • 它将一个问题分解为相互重叠的子问题，通过反复求解子问题，来解决原来的问题。
• 贪心算法
  • 期盼通过每个阶段的局部最优选择，从而达到全局的最优，结果并不一定是最优
• 回溯算法
  • 回溯算法是一种渐进式寻找并构建问题解决方式的策略。 回溯算法会先从一个可能的动作开始解决问题，如果不行，就回溯、