什么是数据结构？
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关
简单来说呢，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。
常见的数据结构有哪些？
数组
栈
队列
链表
树
图
字典树（高效的树形结构）
散列表（哈希表）
根据数据元素之间关系的不同特性，通常有下列4类基本结构：
集合：结构中的数据元素之间除了"同属于一个集合"关系外，别无其他关系
线性结构：结构中的数据元素之间存在一个对一个的关系
树形结构：结构中的数据元素之间存在一个对多个的关系
图状解构：结构中的数据元素之间存在多个对多个的关系
定义：
数据结构是由相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。记为：
Data_Structure=(D,R)
其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合
.Stack（栈）Stack的特点是后进先出（lastinfirstout），栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。
限制是仅允许在标的一端进行插入和删除操作，该位置是表的末端，叫作栈顶。不允许在其他任何位置进行添加、查找、删除等操作。
对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者相当于删除最后一个元素。栈有时又叫作LIFO(LastInFirstOut)表，即后进先出。
栈的提出，其实是为了解决一类特殊的问题的，即要求后入先出，常见的有浏览器的回退功能、有效括号的判断等。本质上来说栈其实是为一种算法而专门设计的数据结构，实际中可以由数组或者链表实现。
应用场景：函数调用栈、表达式求值、括号匹配。Stack一般具备以下方法：
push：将一个元素推入栈顶
pop：移除栈顶元素，并返回被移除的元素
peek：返回栈顶元素
length：返回栈中元素的个数
2.Queue（队列）如上图像一个大木桶，栈中含有3个元素，分别是A、B和C，从在栈中的状态可以看出A最先进的栈，然后B进栈，最后C进栈。根据“先进后出”的原则，3个元素出栈的顺序应该是：C最先出栈，然后B出栈，最后才是A出栈。Queue和Stack有一些类似，不同的是Stack是先进后出，而Queue是先进先出。但是队列又有它的特殊性，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头队列的提出，也是为了解决一类特殊的问题的。很容易想到就是需要排队的地方，也就是FIFO的思想——先到先得，不允许插队。本质上来说队也是为一种算法而专门设计的数据结构，可以由数组或者链表实现。Queue一般具有以下常见方法：
enqueue：入列，向队列尾部增加一个元素
dequeue：出列，移除队列头部的一个元素并返回被移除的元素
front：获取队列的第一个元素
isEmpty：判断队列是否为空
size：获取队列中元素的个数
3.LinkedList（链表）我们知道，使用顺序表（底层实现靠数组）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的，如图所示。
链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下一个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很高。
采用该结构的集合，对元素的存取有如下的特点：
多个结点之间，通过地址进行连接。
查找元素慢:想查找某个元素，需要通过连接的节点，依次向后查找指定元素。
增删元素快：
增加元素：只需要修改连接下个元素的地址即可。
删除元素：只需要修改连接下个元素的地址即可。
一个单向链表通常具有以下方法：
size：返回链表中节点的个数
head：返回链表中的头部元素
add：向链表尾部增加一个节点
remove：删除某个节点
indexOf：返回某个节点的index
elementAt：返回某个index处的节点
addAt：在某个index处插入一个节点
removeAt：删除某个index处的节点
4.数组(Array)
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表（LinearList）就是数据排成像一条线一样的结构。每个线性表上的数据最多只有两个方向。除了数组，链表、队列、栈也是线性表结构。
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
这里再引一下
为什么大多数编程语言中，数组要从0开始编号，而不是开始呢？从数组的存储模型上来看，“下标”最确切的定义应该是“偏移量（offset）”。
如果用a代表数组的首地址，a[0]就是偏移量为0的位置，也就是首地址，a[k]就表示偏移量k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式：
a[k]_address=base_address+k*type_size
但是，如果数组从开始计数，那我们计算数组元素a[k]的内存地址就会变为：
a[k]_address=base_address+(k-)*type_size
如果从开始编号，每次随机访问数组元素都多了一次减法运算，对CPU来说就是多了一次减法指令。
数据结构之数组