数据结构

数据结构：数据的存储（组织）方式。

一、数组。需要指定元素的地址

指多个相同的数据类型在内存中连续排列的一种形式。作为数组元素的各个数据会通过下标编号来区分，这个编号也叫索引。

存储同一种类型的多个元素的容器，有索引，方便我们获取。

特点：查询快，增删慢。

二、栈（stack）。不需要指定元素的地址

采用LIFO（last in first out）即后入先出的方式对内存进行操作。（像收纳箱）数据在存储时从内存的下层（大的地址编号）逐渐往上层（晓得地址编号）累积，读出时则是按照从上往下进行读取的。

位于后面的数据先入栈。

****压*入（push）入*栈****：向栈中存储数据。

****弹*出（pop）出*栈****：从栈中读出数据。

三、队列。不需要指定元素的地址

和栈相似，但先入先出（first in first out）

入列（EnQueue）入队

出列（DeQueue）出队

队列实现有两种：顺序队列和循环队列。

循环队列一般以环状缓冲区的方式实现，适合缓存数据流。

四、链表。不用考虑索引的顺序

高效的对数据元素进行添加和删除操作。

在实现数组的基础上，除了数据的值之外，通过为其附带下个元素的索引，即可实现链表。数据的值和下一个元素的地址（索引）就构成了一个链表元素。

由一个链子把多个结点连接起来组成的数据。结点：有数据和地址组成。（数据域和指针域组成）

链表的添加和删除不涉及数据的移动。

单向链表最后一个结点的地址是null。如果把头元素的地址给了最后一个元素的地址位置，就是循环链表。如果每个结点由3部分（地址、数据、地址）组成，就可以组成双向链表。如果再把前后的对应也连接起来，就成了双向循环链表。

特点：查询慢，增删快。

五、二叉树。不用考虑索引的顺序

高效的对数据元素进行检索操作

在链表的基础上往数组追加元素时，考虑数组的大小关系，将其分为左右两个方向的表现形式。

红黑树：是一种自平衡的二叉树

六、哈希表。是一个元素为链表的数组。综合了链表和数组的好处。

哈希值和什么值有关：和对象的成员变量值有关（有可能直接相加会出现相同的哈希值，所以可以适当的乘一个系数）

桶结构（相当于是链表的同一个索引下放了很多个元素）