线性表是n个数据元素（或结点）的有限序列，分为
- 顺序存储方式
- 链式存储方式
线性表的链式存储结构
- 不需要地址连续的存储单元，而是任意的，甚至是在存储空间中零散分布的存储单元存放线性表的数据；
- 方便进行插入和删除操作，不需要大量移动元素
- 不像顺序表可以随机存取
链表分为：
- 单链表：单链表又分为带头结点和不带头结点。在带头结点的单链表中，头结点不存放数据元素，其指针域指向首元素结点。
- 双链表
- 循环链表
- 循环双链表
数组和链表相比：
- 链表是链式存储结构，数组是顺序存储结构；
- 链表通过指针连接元素，而数组则是把所有元素按顺序进行存储；
- 链表插入和删除元素不需要移动元素，数组删除和增加元素需要移动元素。
- 数组所需存储空间小于链表
需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 ：静态链表
A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 需要分配较大的空间，故A,C排除，因为它们是动态结构，不需要提前分配空间，插入和删除不需要移动元素，而线性结构的插入，删除若是在中间，最极端的是在左边，需要移动右边的全部数据，而静态链表的插入，删除只需要改游标，添加元素方可实现
栈和队列是比价常见的受限的线性结构
栈只能在一端,即栈顶进行添加和删除操作，后进先出（LIFO）
插入元素：进栈、入栈，压栈
删除元素：出栈或退栈
栈的应用：
函数调用栈：如A调用B，B调用C，C调用D
有六个元素6,5,4,3,2,1的顺序进栈，下列哪一个不是合法的出栈顺序 C
A.5 4 3 6 1 2
B.4 5 3 2 1 6
C.3 4 6 5 2 1
D.2 3 4 1 5 6
A 6入栈，5入栈，5出栈，4入栈 4出栈，3入栈3出栈，6出栈，2,1入栈，1出栈，2出栈
B 6 5 4 入栈 ， 4 5 出栈 ， 3 入栈 3出栈， 2入栈 2出栈， 1入栈 1出栈 ， 6出栈
C 6 5 4 3入栈，6可能在5前面出钱 错误
D 6 5 4 3 2 入栈，2 3 4出栈，1入栈 1出栈，56出栈
1. 基于数组实现
2. 基于链表实现
栈的常见操作
1.push(element):添加一个新元素到栈顶位置
2.pop()：移除栈顶的元素，同时返回被移除的元素
3.peek(): 返回栈顶的元素，不对栈做任何的修改
4.isEmpty(): 如果栈里面没有任何元素就返回true，否则返回false
5.size(): 返回栈里的元素个数。和数组的length属性类似
6.toString()：将栈结构的内容以字符形式返回
<script>
//封装栈类
function Stack() {
//栈中的属性
this.items = []
// 栈的相关操作
// 1.push(element):添加一个新元素到栈顶位置
// this.push=function(){
// }
Stack.prototype.push = function(element) {
this.items.push(element)
}
// 2.pop()：移除栈顶的元素，同时返回被移除的元素
Stack.prototype.pop = function() {
return this.items.pop()
}
// 3.peek(): 返回栈顶的元素，不对栈做任何的修改
Stack.prototype.peek = function() {
return this.items[this.items.length - 1]
}
// 4.isEmpty(): 如果栈里面没有任何元素就返回true，否则返回false
Stack.prototype.isEmpty = function() {
return this.items.length == 0
}
// 5.size(): 返回栈里的元素个数。和数组的length属性类似
Stack.prototype.size = function() {
return this.items.length
}
// 6.toString()：将栈结构的内容以字符形式返回
Stack.prototype.toString = function() {
var resultString = ''
for (var i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ' '
}
return resultString
}
}
//栈的使用
var s = new Stack()
s.push(20)
s.push(10)
alert(s)
</script>十进制转二进制
//十进制转二进制 function dec2bin(decNumber) { //1定义一个栈对象 var stack = new Stack() //2循环 while (decNumber > 0) { //2.1 获取余数，并且放入到栈中 stack.push(decNumber % 2) //2.2 获取整除后的结果，作为下一次运行的数字 decNumber = Math.floor(decNumber / 2) } //3.从栈中取出 var binaryString = '' while (!stack.isEmpty()) { binaryString += stack.pop() } return binaryString } //测试 alert(dec2bin(100)) //1100100 alert(dec2bin(10)) //1010
解析XML时，需要校验节点是否闭合，如必须有与之对应，用（）数据结构实现比较好 D
链表 树 队列 栈栈是解决封闭对应问题的有效方法。
比如在解析XML中，遇到一个<demo>标签（左标签）就入栈，遇到其子标签的左标签（如<subdemo>）同样入栈。遇到右标签(如</subdemo>或</demo>)就校验栈顶标签是否与该右标签对应，能对应就出栈，不能对应则说明标签不对称，是无效的XML文件
先进先出（FIFO First in First Out）
只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作
队列的应用
打印队列：优先放入的文档，优先被取出
线程队列：开启多个线程，使用线程队列
基于数组实现
基于链表实现
1. enqueue(element):向队列尾部添加一个或多个新的
2. dequeue(): 移除队列的第一项（即排在队列最前面的项），并返回被移除的元素
3. front():返回队列中第一个元素，最先被添加，也将是最先被移除的元素。队列不做任何的变得（不移除元素，只返回元素信息，与Stack的peek方法类似）
4. isEmpty(): 如果队列中不包含元素，返回true，否则返回false
5. size(): 返回队列包含的元素个数，与数组的length类似
6. toString(): 将队列中的内容，转换成字符串的形式
<script>
function Queue() {
//属性
this.items = []
//方法
//1. enqueue(element):向队列尾部添加一个或多个新的
Queue.prototype.enqueue = function(element) {
this.items.push(element)
}
// 2. dequeue(): 移除队列的第一项（即排在队列最前面的项），并返回被移除的元素
Queue.prototype.dequeue = function() {
return this.items.shift()
}
// 3. front():返回队列中第一个元素
Queue.prototype.front = function() {
return this.items[0]
}
// 4. isEmpty(): 如果队列中不包含元素，返回true，否则返回false
Queue.prototype.isEmpty = function() {
return this.items.length == 0
}
// 5. size(): 返回队列包含的元素个数，与数组的length类似
Queue.prototype.size = function() {
return this.items.length
}
// 6. toString(): 将队列中的内容，转换成字符串的形式
Queue.prototype.toString = function() {
var resultString = ''
for (var i = 0; i < this.items.length; i++) {
resultString += this.items[i] + ' '
}
return resultString
}
}
//使用队列
var queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
alert(queue)
</script>面试题：击鼓传花
几个人围成一圈，开始数数，数到某个数字的人自动淘汰，最后剩下的是在原来哪个位置的人？
//面试题：击鼓传花
function passGame(nameList, num) {
var queue = new Queue()
//2. 将所有人依次加入到队列中
for (var i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
//3.开始数数字
while (queue.size() > 1) {
//不是num的时候，重新加入到队列的末尾
//是num这个数字的时候，将其从队列中删除
//3.1 num数字之前的人重新放入到队列的末尾
for (var i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue())
}
//3.2 num对应这个人，直接从队列中删除
queue.dequeue()
}
//4. 获取剩下的那个人
alert(queue.size())
var endName = queue.front()
alert('最终剩下的人' + endName)
return nameList.indexOf(endName)
}
//测试
names = ['Lily', 'Lucy', 'Tom', 'Lilei', 'why']
alert(passGame(names, 3))1. 集合通常是由一组无序的、不能重复的元素构成
2. 可看成特殊的数组，特殊之处在于没有顺序，意味着不能通过下标值进行访问；不能重复，意味着相同的对象在集合中只会存在一份
3. ES6中的Set类就是一个集合
1. add(value): 向集合添加一个新的项
2. remove(value): 从集合中移除一个值
3. has(value): 如果值在集合中，返回true，否则返回false
4. clear(value): 移除集合中的所有项
5. size(): 返回集合所包含元素的数量。与数组的length属性类似
6. values(): 返回一个包含集合中所有值得数组
function Set() {
//属性
this.items = {}
//方法
//1.has方法
Set.prototype.has = function(value) {
return this.items.hasOwnProperty(value)
}
//2.add方法
Set.prototype.add = function(value) {
//判断当前集合中是否已经包含了该元素
if (this.has(value)) {
return false
}
//将元素添加到集合中
this.items[value] = value
return true
}
//3.remove从集合中移除一个值
Set.prototype.remove = function(value) {
//1.判断该集合中是否包含该元素
if (!this.has(value)) {
return false
}
//2.将元素从集合中移除
delete this.items[value]
return true
}
//4.clear方法
Set.prototype.clear = function() {
this.items = {}
}
//5.size方法
Set.prototype.size = function() {
return Object.keys(this.items).length
}
//6.获取集合中所有元素的值
Set.prototype.values = function() {
return Object.keys(this.items)
}
}1.并集
2.交集
3.差集
4.子集
字典中的特点主要是一一对应的关系
字典中的key不是可以重复的，但value可以重复，且字典中的key是无序的