第 1 章 算法概述
算法 (algorithm) 是一系列程序指令，用于处理特定的运算和逻辑问题。衡量算法优劣的主要标准是时间复杂度和空间复杂度。
数据结构 (data structure) 是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。数据结构都有哪些组成方式呢?
- 线性结构：最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、队列、哈希表。
- 树：相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。
- 图：更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。
- 其他数据结构：由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等。
时间复杂度 是对一个算法运行时间长短的量度，用大 O 表示，记作 T(n) = O(f(n))。
空间复杂度 是对一个算法在运行过程中临时占用存储空间大小的量度，用大 O 表示，记作 S(n) = O(f(n))。
第 2 章 数据结构基础
1. 数组
数组 (array) 是由有限个相同类型的变量所组成的有序集合。数组是最为简单、最为常用的数据结构。数组的物理存储方式是顺序存储，访问方式是随机访问。
数组的优势：利用下标就可以用常量时间 O(1) 找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。
数组的劣势：由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，其时间复杂度是 O(n)。
2. 链表
链表 (linked list) 是一种链式数据结构，由若干节点组成，每个节点包含指向下一节点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查找链表节点的时间复杂度是 O(n)，插入、删除节点的时间复杂度是 O(1)。
3. 栈
栈 (stack) 是一种线性数据结构，可以用数组实现，也可以用链表实现。栈包含 入栈 (push) 和 出栈 (pop) 操作，遵循 先入后出 (FILO) 的原则，最早进入的元素存放的位置叫作 栈底 (bottom)，最后进入的元素存放的位置叫作 栈顶 (top)。
栈的应用：栈的输出顺序和输入顺序相反，所以栈通常用于对「历史」的回溯。例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。
4. 队列
队列 (queue) 也是一种线性数据结构，可以用数组实现，也可以用链表实现。队列包含 入队 (enqueue) 和 出队 (dequeue) 操作，遵循 先入先出 (FIFO) 的原则。队列的出口端叫作 队头 (front)，队列的入口端叫作 队尾 (rear)。
队列的应用：队列的输出顺序和输入顺序相同，所以队列通常用于对「历史」的回放，也就是按照「历史」顺序，把「历史」重演一遍。例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。
物理结构：包括顺序存储结构（数组）和链式存储结构（链表）
逻辑结构：包括线性结构（顺序表、栈、队列）和非线性结构（树、图）
5. 散列表
散列表 也叫 哈希表 (hash table)，是存储 Key-Value 映射的集合。对于某一个 Key，散列表可以在接近 O(1) 的时间内进行读写操作。散列表本质上是一个数组，通过哈希函数实现 Key 和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。
开放寻址法：当一个 Key 通过哈希函数获得对应的数组下标已被占用时，我们可以「另谋高就」，寻找下一个空档位置。
链表法：Java 的集合类 HashMap 使用的就是链表法。HashMap 数组的每一个元素不仅是一个 Entry 对象，还是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需要插入到对应的链表中即可。
第 3 章 树
1. 二叉树
二叉树 (binary tree) 是树的一种特殊形式，每一个节点最多有 2 个孩子节点。二叉树包含完全二叉树和满二叉树两种特殊形式：
- 满二叉树：所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上。
- 完全二叉树：如果一个树所有 n 个节点和同样深度的满二叉树的 1 到 n 的节点位置相同，则这个二叉树为完全二叉树。
完全二叉树的条件没有满二叉树那么苛刻：满二叉树要求所有分支都是满的；而完全二叉树只需保证最后一个节点之前的节点都齐全即可。
二叉树的应用
1. 查找
二叉查找树 (binary search tree) 在二叉树的基础上增加了二个条件：左子树上所有节点的值均小于根节点的值；右子树上所有节点的值均大于根节点的值。
例如上图中查找值为 4 的节点，步骤如下：
- 访问根节点 6，发现 4 < 6。
- 访问节点 6 的左孩子节点 3，发现 4 > 3。
- 访问节点 3 的右孩子节点 4，发现 4 = 4，这正是要查找的节点。
对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是 n，那么搜索节点的时间复杂度就是 O(logn)，和树的深度是一样的。这种依靠比较大小来逐步查找的方式，和二分查找算法非常相似。
2. 排序
二叉排序树 (binary sort tree) 是二叉查找树的另一个名字，新插入的节点，同样要遵循二叉排序树的原则。例如插入新元素 5，由于 5 < 6，5 > 3，5 > 4，所以 5 最终会插入到节点 4 的右孩子位置。
这一切看起来很顺利，然而却隐藏着一个致命的问题。下面请试着在二叉查找树中依次插入 9、8、7、6、5、4，看看会出现什么结果。
不只是外观看起来变得怪异了，查询节点的时间复杂度也退化成了 O(n)。怎么解决这个问题呢？这就涉及二叉树的自平衡了。二叉树自平衡的方式有多种，如红黑树、AVL 树、树堆等。由于篇幅有限，本书就不 一一详细讲解了，感兴趣的读者可以查一查相关资料。
二叉树的遍历方式
| 遍历方式 | 输出顺序 | 宏观角度区分 |
|---|---|---|
| 前序遍历 | 根节点、左子树、右子树 | 深度优先遍历 |
| 中序遍历 | 左子树、根节点、右子树 | 深度优先遍历 |
| 后序遍历 | 左子树、右子树、根节点 | 深度优先遍历 |
| 层序遍历 | 广度优先遍历 |
深度优先遍历
绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解决，这种数据结构就是栈。因为递归和栈都有回溯的特性。
- 首先遍历二叉树的根节点 1，放入栈中。
- 遍历根节点 1 的左孩子节点 2，放入栈中。
- 遍历节点 2 的左孩子节点 4，放入栈中。
- 节点 4 既没有左孩子，也没有右孩子，我们需要回溯到上一个节点 2。栈已经存储了刚才遍历的路径。让旧的栈顶元素 4 出栈，就可以重新访问节点 2，得到节点 2 的右孩子节点 5。此时节点 2 已经没有利用价值，节点 2 出栈，节点 5 入栈。
- 节点 5 既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点 1。所以让节点 5 出栈。根节点 1 的右孩子是节点 3，节点 1 出栈，节点 3 入栈。
- 节点 3 的右孩子是节点 6，节点 3 出栈，节点 6 入栈。
- 节点 6 既没有左孩子，也没有右孩子，所以节点 6 出栈。此时栈为空，遍历结束。
广度优先遍历
二叉树同一层次的节点之间是没有直接关联的，如何实现这种层序遍历呢？这里同样需要借助一个数据结构来辅助工作，这个数据结构就是队列。
- 根节点 1 进入队列。
- 节点 1 出队，输出节点 1，并得到节点 1 的左孩子节点 2、右孩子节点 3。让节点 2 和节点 3 入队。
- 节点 2 出队，输出节点 2，并得到节点 2 的左孩子节点 4、右孩子节点 5。让节点 4 和节点 5 入队。
- 节点 3 出队，输出节点 3，并得到节点 3 的右孩子节点 6。让节点 6 入队。
- 节点 4 出队，输出节点 4，由于节点 4 没有孩子节点，所以没有新 节点入队。
- 节点 5 出队，输出节点 5，由于节点 5 同样没有孩子节点，所以没 有新节点入队。
- 节点 6 出队，输出节点 6，节点 6 没有孩子节点，没有新节点入 队。
二叉堆
二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。在最大堆中，任何一个父节点的值，都大于或等于它左、右孩子节点的值；在最小堆中，任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点叫作堆顶。最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。
优先队列
优先队列分为最大优先队列和最小优先队列。
在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。
在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的。