背景
数据结构是我们开发过程中最常用到的基本知识，比如表，方法调用栈等等。熟练的掌握基本的数据结构，有助于提升我们对数据的增删查的效率。我在这里简单总结了我们常见的数据结构知识，包括表、栈、队列和二叉树。
表
表的有两种常见的实现方式：数组和链表
| 结构 | 优点 | 缺点 |
|---|---|---|
| 数组实现 | get和set调用常数时间 | 插入和删除代价昂贵 |
| 链表实现 | 插入和删除开下很小 | 不容易索引，get调用昂贵 |
栈
栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。
栈的实现
数组和链表均可实现栈，效率相当。
栈的应用
- 平衡符号
检验是否每件事情都能成对出现。序列[()]是合法的
做一个空栈。读入字符直到文件结尾。如果字符是一个开发符号，则将其推入栈中。如果字符是一个封闭符号，则当栈空时报错。否则，将栈元素弹出。如果弹出的符号不是对应的开发符号，则报错。在文件结尾，如果栈非空则报错。
- 后缀表达式
4.99*1.06+5.99+6.99*1.06=
可以书写如下:
4.99 1.06*5.99+6.00 1.06*+
例如: 6 5 2 3 + 8 + 3
读入前4个数字，栈中的值3 2 6 5(栈尾)；
下一个读到”+”号，所以3和2从栈中弹出并且它们的和5被压入栈中，栈中的值5 5 6(栈尾);
接着8进栈，栈中的值8 5 5 6(栈尾)
- 方法调用栈
当调用一个新方法时，主调例程的所有局部变量需要由系统存储起来，否则被调用的新方法将会重写由主调例程的变量所使用的内存。
需要存储的所有重要信息，诸如寄存器的值(对应变量的名字)和返回地址等信息称为活动记录或叫作栈帧
队列
像栈一样，队列也是表。队列是插入在一端进行而删除则在另一端进行。
队列的基本操作是入队，在表的末端插入一个元素。和出队它是删除在表的开头元素
实现
数组和链表均可实现，效率相当。链表实现比较简单。
应用
- 打印机的实现
- 排队买票
二叉树
对于大量的输入数据，链表的线性访问时间太慢，不宜使用，而二叉树的大部分操作运行时间平均为O(logN)。
二叉树是一个树，其中每个节点都不能多于两个的儿子
树的实现是通过链表
二叉树的一种重要的应用是查找
二叉查找树
对于树中的每个节点，它的左子树中所有项的值小于X中的项，而它的右子树中所有的值大于X中的项
此树对于查找效率比较高。
AVL树
AVL树是带有平衡条件的二叉查找树。
一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树
如果打破了平衡，则通过旋转来解决平衡
- 单旋转
- 双旋转
B树
减少高度，增加分支，从而能够减少深度。
阶为M的B树。如5阶B树，即是5个分叉
应用场景:磁盘数据的查找
二叉堆
堆是一棵完全填满的二叉树。例外就是底层，底层上的元素从左到右填入。又称完全二叉树。
完全二叉树可以用一个数组表示而不需要使用链
插入：上滤
删除：下滤
最小堆
最小元素在根上。任意子树也是一个堆，任意节点都小于它的所有后裔。
最大堆
左式堆
对于堆中的每一个节点X，左儿子的零路径长不小于右儿子的零路径长
任一节点X的零路径长npl(X)定义为从X到一个不具有两个儿子的节点的最短路径的长。具有0个或一个儿子的节点的npl为0。
左式堆的基本操作是合并
红黑树
红黑树是AVL树的一种变种。
红黑色是具有下列着色性质的二叉查找树：
- 每一个节点或者着成红色，或者着成黑色
- 根是黑色的
- 如果一个节点是红色的，那么它的子节点必须是黑色的
- 从一个节点到一个null引用的每一条路径必须包含相同数目的黑色节点。