计算机处理问题时，常常要把一个大问题自上而下分解为很多小问题，一个个拆解开，分别解决后，再回过头得到整个问题的答案。堆栈能够记录这中间一步步分解的复杂过程，而且由于最后合并的过程和一开始拆解的过程正好相反，因此它后进先出的特点可以很自然的将分解的问题合并回去——《计算之魂》
数组与链表
数组
- 数组是有限个相同类型的变量组成的有序集合；物理上是要求连续的；
基本操作的时间复杂度：读取O(1)、更新O(1)、插入O(n)、删除O(n)、扩容O(n)；
链表
- 链表是一种物理上非连续、非顺序的数据结构。包含存放数据的data和指向下一节点的指针；
基本操作的时间复杂度：读取O(n)、更新O(1)、插入O(1)、删除O(1)；
堆栈与队列
- 堆栈是一种线性逻辑数据结构，栈元素只能后进先出，最早放入的元素在栈底，最晚放入的元素在栈顶。就像圆桶装的薯片，最先放入的在最底层，我们只能从最上层吃到底层；
- 队列是一种线性逻辑数据结构，队列只能后进后出，队列的出口处叫做队头，入口处叫做队尾。就像常见的排队，排在前面的先买票；
应用：
堆栈：回溯历史命令、实现简单计算器功能（边压入边处理）
队列：消息队列、树的广度优先算法实现、二叉树遍历实现
注：我们在使用堆栈的时候，可以全部压入后使用，也可以边压入边处理，根据具体情况进行分析。
哈希表
- 哈希表是一种逻辑数据结构，提供了键（key）和值（value）的映射关系
基本操作：写入O(1)、读取O(1)、扩容O(n)
优点：通过关键字实现一对一查找的速度非常快。常作为“空间换时间”的操作，应用非常广泛
缺点：存在冲突，解决冲突有开放寻址法（插入冲突位置后面）和链表法（链表next指向冲突值）
树
- 树是n个节点的有限集，具有如下特点：有且只有一个根（root）节点；当n>1时，其余节点可分为m个互不相交的有限集，每个集合本身又是一棵树，称为根的子树
树的遍历
深度优先
前序：根节点、左子树、右子树 | 中序：左子树、根节点、右子树 | 后序：左子树、右子树、根节点
上述取自参考内容的示意图
广度优先
层序遍历：一层层遍历，可以利用队列实现
Python代码实现：二叉树遍历实现
二叉树
二叉树：最多两个叶子节点
满二叉树：所有非叶子节点都有两个子节点
完全二叉树：层级顺序遍历，和满二叉树节点位置相同
二叉查找树
- 如果左子树不为空，则左子树上所有节点的值均小于根节点的值。
- 如果右子树不为空，则右子树上所有节点的值均大于根节点的值。
- 左、右子树也都是二叉查找树。
二叉堆
二叉堆是一种特殊的完全二叉树，它分为两个类型：最大堆和最小堆。
- 最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值。
- 最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆实现 & 应用：N个数中最小的k个数
