数据结构

哈希hash（键：值）

Hash表也称散列表，也有直接译作哈希表，Hash表是一种特殊的数据结构，它同数组、链表以及二叉排序树等相比较有很明显的区别，它能够快速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比较来进行查找。
这个源于Hash表设计的特殊性，它采用了函数映射的思想将记录的存储位置与记录的关键字关联起来，从而能够很快速地进行查找。
也就是说，哈希表的结构就是以键-值(key-value)这样一种映射来存储数据，这样当我们需要查找时只要输入key，就可以查找到相对应的值。

队列（Queue）

• 先进先出
• 可以用数组实现
• 在队尾插入元素，在队首删除元素
• push(入队),shift（出队）
• 举例：排队;在队列中先进来排队的人也就是队首的先出去，而新来的人想要排队也只能从队尾开始。

var q = []  //空队
// 进队
q.push('刘备')
1
q.push('关羽')
2
q.push('张飞')
3
// 出队
q.shift()
'刘备'
q.shift()
'关羽'
q.shift()
'张飞'

栈(Stack)

• 先进后出

• 可以用数组实现

• 入栈（push），出栈 (pop)

• 限定仅在表尾进行插入和删除操作

• 我们把允许插入和删除的一端成为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。

• 举例：盗梦空间，我们依次进入第一层梦，第二层梦，第三层梦，退出时也只能先退出第三层梦，再退出第二层，第一层。

var stack = []
// 进栈
stack.push('第一层梦')
1
stack.push('第二层梦')
2
stack.push('第三层梦')
3
// 出栈
stack.pop()
"第三层梦"
stack.pop()
"第二层梦"
stack.pop()
"第一层梦"

链表（Linked List）

• 链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。
• 结点包括两个部分：一、存储数据元素的数据域（内存空间），二、存储指向下一个结点地址的指针域。
• 实现数据元素的存储按一定顺序储存，允许在任意位置插入和删除结点。
• 数组无法直接删除中间的一项，链表可以

• 用哈希（JS里面用对象表示哈希）实现链表
  1.数组缺点：删除一项特别麻烦 但是想取到数组第n项比较简单 （a[n-1]）
  2.列表 ：可以随便删除一项 但是想取到列表第n 项 比较复杂 (.next.next...)

  
  
• 删除第二项

• a1的下一项变成a3，这样就可以删除a2

  
  

树(tree)

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；

• 除了根节点外，每个子节点可以分为多个不相交的子树。

  
  

二叉树:每个节点最多只分两个分支

完全二叉树：从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

• 完全二叉树和满二叉树都可以用数组来存储。

• 这种就不是完全二叉树 左边没有连续