数据结构
数据结构是指相互之间存在着一种或多种数据元素的集合和该集合中数据元素之间的关系组成。
常用的数据结构有：数组、栈、链表、队列、树、图、堆、散列表等，每一种数据结构都有独特的数据存储方式。
1、数组：数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。
* 优点、1、按照索引查询元素速度快，2、按照索引遍历数组方便。
* 缺点、1、数组的大小固定后就无法扩容了，2、数组只能存储一种类型的数据，3、添加-删除的操作慢、因为要移动其他的元素。
* 适用场景、频繁查询，对存储空间要求不大，很少添加和删除的情况。
* Java中，Array就是数组
2、栈：栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。栈的特点是：先进后出，或者说是后进先出，
* 从栈顶放入元素的操作叫入栈，取出元素叫出栈。
* 适用场景、实现递归功能方面的场景。
* Stack是继承自Vector，底层使用数组存储、用来模拟栈的一个java集合。同时也是线程安全的。
3、队列：队列与栈一样，也是一种线性表，不同的是队列先进先出，一端添加元素，另一端取出元素
* 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
* Java中，Queue就是队列,java.util.concurrent包包含一组同步的Queue接口和类
LinkedBlockingQueue — 由链节点支持的可选有界FIFO阻塞队列。
ArrayBlockingQueue — 由数组支持的有界FIFO阻塞队列。
PriorityBlockingQueue — 由堆支持的无界阻塞优先级队列。
DelayQueue — 由堆支持的基于时间的调度队列。
SynchronousQueue — 一个简单的集合机制，使用BlockingQueue接口。
在JDK 7中，TransferQueue是专门的BlockingQueue，其中将元素添加到队列中的代码可以选择等待（阻塞）另一个线程中的代码来检索该元素，
TransferQueue有一个实现：
LinkedTransferQueue — 基于链节点的无界TransferQueue。
*
4、链表：链表是物理存储单元上非连续的，非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，
* 一个是存储元素的数据域（内存空间），另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表。
* 优点、1、链表是一种很常用的数据结构，不需要初始化容量，可以任意加减元素；2、添加或删除元素时只要改变前两个元素结点的指针域指向地址即可，所以添加、删除很快；
* 缺点、1、因为含有大量指针域，占用空间大；2、查找时需要遍历链表来查找，比较耗时。
* 使用场景：数据量小，需要频繁增加、删除操作的场景。
* Java中，LinkedList
5、树：树是一种数据结构，它是由n（n>=1）个有限节点组成的有层次关系的集合。把它叫做“树”是因为它看起来像一颗倒挂的树，也就是说它根朝上叶朝下。
* 特点：每个节点都有0个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
* 二叉树是树的特殊一种，二叉树的扩展：平衡二叉树、红黑树、B+树等
* 二叉树特点：1：每个结点最多有两颗子树，结点的度最大为2；左子树和右子树是有顺序的，顺序不能颠倒；3：即时某结点只有一个子树，也要区分左右子树；
* Java中，需自定义
6、散列表：也叫哈希表，是根据关键码和值（key和value）直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
* 记录的存储位置=f(key)
* f成为散列函数，又称为哈希，而散列表就是把key通过一个固定的算法函数（哈希函数）转换成一个整型数字，然后将该数字对数组长度进行取余，取余结果作为数组下标，
* 将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找很快。
* 拉链法：拉链法是数组结合链表的一种结构，较早前的hashmap底层的存储就是采用这种结构。
* 应用场景：哈希表的应用场景很多，当然也要考虑很多问题，比如哈希冲突的问题，如果处理不好会浪费大量的时间，导致应用崩溃。
* Java中，hashmap、hashtable等
7、堆：堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有一下的性质：1、堆中某个节点的值总是不大于或不小于其父节点的值，2、堆总是一颗完全二叉树
* 将根节点最大的堆叫做最大堆，根节点最小的堆叫做最小堆。 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
* Java中，需自定义
8、图：图是由结点有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，有图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，
* 就表示这两个顶点具有相邻关系。按照顶点指向的方向可分为无序图和有序图。
* 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵、邻接表、十字链表、邻接多重表、边界数组等存储结构。
* Java中，需自定义