对于数据结构，没有官方的一个定义。按照普遍的理解可以这样区分
- 数据结构就是在计算机中，存储和组织数据的方式。打个比方，在家里，有桌子，椅子，床等。
- 计算机中数据量是非常庞大，如何高效的方式去存储和组织数据。打个比方，如何布置家里，整理会让家里看起来更加宽敞。
- 打个更贴切的比喻，比如国家的图书馆，存放了上万本的书籍。我们需要通过标签，类别，在合适的时候，能快速的定位，取到一本书。
常见的数据结构
- 栈（Stack）
- 堆（Heap）
- 数组（Array）
- 链表（Linked List）
- 队列（Queue）
- 图（Graph）
- 散列表（Hash）
- 数（Tree）
每一种都有对应的应用场景，不通数据结构对应的不同操作，性能也都是不一样。有的查询特别快，插入头和尾速度很快，比如链表。有的做范围查找很快。因此开发中选型那种数据结构，是一个很关键的部分。
栈
- 关于栈，结合这么一个贴切的例子来理解，一条单车道的单行线，一端被堵住了，而另一端入口处没有任何提示信息，堵住之后就只能后进去的车子先出来，这时这个堵住的单行线就可以被看作是一个栈容器，车子开进单行线的操作叫做入栈，车子倒出去的操作叫做出栈。在车流量较大的场景中，就会发生反复的入栈、栈满、出栈、空栈和再次入栈，一直循环。所以，栈就是类似于一端被堵住的单行线，车子类似于栈中的元素，栈中的元素满足后进先出的特点。你可以参看下图：
栈示意图
先来看如下的代码，通过代码来体现出栈在JS中的应用。
var a = 2
function add(b, c) {
console.log(' == add ==');
return b + c
}
function addAll(b, c) {
console.log(' == addAll ==');
var d = 10
result = add(b, c)
return a + result + d
}
addAll(3, 6)
- 首先执行上下文
- 调用addAll的方法，把该函数压到栈上。
- 调用add方法，再把该函数压到栈上。
- add的方法执行完毕，出栈。
- addAll的方法执行完毕，出栈。
初始化上下文的时候，我们可以看出来，栈上已经压了一个初始化的，这时候看global的数据，a已经赋值为2，add方法和addall的方法也都初始化完成了。
初始化上下文
执行到addall的方法，可以看到，在stack中，也就是栈中，进入了一个函数addall，而且也看到了local开面数据已经赋值上去了。
image.png
执行到add的方法的时候，可以看到。add的方法也加入到了栈的队列中。并且当前这个方面的私有属性也都看到。
image.png
最后一次执行的时候，移除add的栈内存，在移除addall的栈内存，全部清空。这次程序就结束了运行。在面试中经常就会对把栈内存和堆内存，变量提升等作为考点。当开发中遇到死循环或者是递归一直调用没办法终结的时候，就会出现栈溢出。
栈溢出
- JS的基本类型就5种Undefined、Null、Boolean、Number和String，它们都是直接按值存储在栈中的，每种类型的数据占用的内存空间的大小是确定的，并由系统自动分配和自动释放。
- 如对象(Object)、数组(Array)、函数(Function) …，它们是通过拷贝和new出来的，这样的数据存储于堆中，但是它的引用对象是在栈中。就像上面的方法，可以看到add和addall的方法，都是存在栈内存中。需要先从栈中获得对象的地址指针。
堆
堆的特点就是无序，以key-value的方式存在。从上面栈的例子上看，栈中只是保存了一个引用的指针类型，具体的实现方法，其实是存在堆内存中。通过引用指针的key，可以快速找到堆内存中的具体方法。可以比喻成书架，可以随便放书本，但是我们通过书本的名字可以快速找到具体的哪本书。
数组
数组在不同语言中，都有各自的封装，在JS中封装的程度也是很好，数组的去重，遍历，查找，删除等都已经有封装。而且在开发中也是经常会使用到，这边就不做太多的说明。
var daysOfWeek = new Array()
var daysOfWeek = new Array(7)
var daysOfWeek = new Array('Sunday', 'Monday', 'Tuesday', 'Wednesday',
'Thursday', 'Friday', 'Saturday')
// 直接赋值数组内容
var daysOfWeek = ['Sunday', 'Monday', 'Tuesday', 'Wednesday',
'Thursday', 'Friday', 'Saturday'];
- 数组的创建通常需要申请一段连续的内存空间，并且大小是固定的。
- 当数据不能满足容量需求的时候，需要扩容。
- 数组的开头或者中间插入数据的成本很高，需要进行大量的元素位移。
链表
- 和数组一样，也是可以存储多个元素，但是链表的元素在内存中是不需要连续的空间。
- 链表的每个一个元素由一个存储元素的本身节点和一个指向下一个元素的引用（指针）组成
- 链表访问任何一个位置的元素的时候，需要从头开始访问，无法跳过任何一个元素。
- 无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素。
单向链表示例
图中示意的，地址指向的就是下一个节点的内存地址。双向链表的意思，就是可以在找到上一个节点。
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Title</title>
</head>
<body>
<script>
// 封装链表的构造函数
function LinkedList() {
// 封装一个Node类, 用于保存每个节点信息
function Node(element) {
this.element = element
this.next = null
}
// 链表中的属性
this.length = 0
this.head = null
// 链表尾部追加元素方法
LinkedList.prototype.append = function (element) {
// 1.根据新元素创建节点
var newNode = new Node(element)
// 2.判断原来链表是否为空
if (this.head === null) { // 链表尾空
this.head = newNode
} else { // 链表不为空
// 2.1.定义变量, 保存当前找到的节点
var current = this.head
while (current.next) {
current = current.next
}
// 2.2.找到最后一项, 将其next赋值为node
current.next = newNode
}
// 3.链表长度增加1
this.length++
}
// 链表的toString方法
LinkedList.prototype.toString = function () {
// 1.定义两个变量
var current = this.head
var listString = ""
// 2.循环获取链表中所有的元素
while (current) {
listString += "," + current.element
current = current.next
}
// 3.返回最终结果
return listString.slice(1)
}
// 根据下标删除元素
LinkedList.prototype.insert = function (position, element) {
// 1.检测越界问题: 越界插入失败
if (position < 0 || position > this.length) return false
// 2.定义变量, 保存信息
var newNode = new Node(element)
var current = this.head
var previous = null
index = 0
// 3.判断是否列表是否在第一个位置插入
if (position == 0) {
newNode.next = current
this.head = newNode
} else {
while (index++ < position) {
previous = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
// 4.length+1
this.length++
return true
}
// 根据位置移除节点
LinkedList.prototype.removeAt = function (position) {
// 1.检测越界问题: 越界移除失败, 返回null
if (position < 0 || position >= this.length) return null
// 2.定义变量, 保存信息
var current = this.head
var previous = null
var index = 0
// 3.判断是否是移除第一项
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
// 4.length-1
this.length--
// 5.返回移除的数据
return current.element
}
// 根据元素获取链表中的位置
LinkedList.prototype.indexOf = function (element) {
// 1.定义变量, 保存信息
var current = this.head
index = 0
// 2.找到元素所在的位置
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
// 3.来到这个位置, 说明没有找到, 则返回-1
return -1
}
// 根据元素删除信息
LinkedList.prototype.remove = function (element) {
var index = this.indexOf(element)
return this.removeAt(index)
}
// 判断链表是否为空
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
// 获取链表的长度
LinkedList.prototype.size = function () {
return this.length
}
// 获取第一个节点
LinkedList.prototype.getFirst = function () {
return this.head.element
}
}
// 测试链表
// 1.创建链表
var list = new LinkedList();
// 2.追加元素
list.append(15)
list.append(10)
list.append(20)
console.log(list);
