数组结构

1. js数组长度不固定，可以自动扩容
2. 可以从任意位置删除、取出、插入
3. 数组进行中间插入和删除操作性能较低

• 插入需要将位置后边的依次向后移动
• 删除需要将位置后边的依次向前移动

4. 通过下标修改、取出效率很高

栈结构

1. 栈结构也是一种线性结构
2. 栈是一种受限的线性结构，只能在栈顶添加或删除元素
3. 栈后进先出（后进来的先出去）LIFO
4. 向一个栈插入新元素又称作进栈、入栈或压栈，他是把新元素放到栈顶元素的上边
5. 从一个栈删除元素又称出栈或退栈，他是把栈顶元素删除
6. 栈的应用

• 函数调用栈---函数A内部调用另一个函数B，B放在栈顶，A放在栈底，必须先执行完B，及B退栈以后才会执行A
• 递归栈溢出---递归不断调用函数本身，本身都未进行执行，不会出栈，所以不断叠加

7. 栈结构面试题

• C 6、5 6需要在5后边出栈

8. 封装栈结构

function Stack(){
  //数据
	this.item=[]
  //插入元素
	Stack.prototype.push=function(element){
    	this.item.push(element)
    }
  //取出栈顶元素，改变原数据
  	Stack.prototype.pop=function(){
    	return this.item.pop()
    }
  //查看栈顶元素，不改变原数据
  	Stack.prototype.peek=function(){
    	return this.item[this.item.length-1]
    }
  //判断栈是否为空
  	Stack.prototype.isEmpty=function(){
    	return this.item.length==0
    }
  //获取栈中元素个数
  	Stack.prototype.size=function(){
    	return this.item.length
    }
  //toString 方法
  	Stack.prototype.toString=functin(){
    	var resultString=''
        this.item.forEach(item=>{
        	resultString+=item
        })
      return resultString
    }
}

9. 栈的应用 十进制转二进制

function dec2bin(decNUmber){
	var stack=new Stack()
    //获取余数
    while(decNumber>0){
    	stack.push(decNumber%2)
    }
  //从栈中取出值
  	var binNumber=''
    while(!stack.isEmpty()){
    	binNumber+=stack.pop()
    }
  return binNumber
}

队列结构

1. 队列也是一种线性结构
2. 对列是一种受限的线性结构，只能在表的前端删除，后端插入
3. 先进先出FIFO
4. 对列应用

• 打印对列
• 线程对列 5.封装队列结构

function Queue(){
  //属性
	this.item=[]
 //加入元素到队列 
 	Queue.prototype.enqueue=function(element){
  	this.item.push(element)
  }
  //从队列删除前端元素
  Queue.prototype.dequeue=function(){
  	return this.item.shift()
  }
  //查看前端的元素
  Queue.prototype.front=function(){
  	return this.item[0]
  }
  // 查看队列是否为空
  Queue.prototype.isEmepty=function(){
  	return this.item.length==0
  }
  //查看队列元素个数
  Queue.prototype.size=function(){
  	return this.item.length
  }
  //toString方法
  Queue.prototype.toString=function(){
  	var resultString=''
    this.item.forEach(e=>{
    	resultString+=e
    })
    return resultString
  }
}

6. 队列的应用--击鼓传花

function passGame(nameList,num){
	var queue=new Queue()
    for(var i=0;i<nameList.length;i++){
    	queue.enqueue(nameList[i])
    }
  while(queue.size>1){
  	for(var j=0;j<num-1;j++){
    	queue.enqueue(queue.dequeue())
    }
  }
  var endName=queue.front()
  return nameList.indexOf(endName)
}

优先级队列

1. 和队列类似的线性结构
2. 在插入元素时会考虑该数据的优先级和其他数据进行比较，比较完成后得出元素在队列正确位置
3. 优先级队列应用

• 登机顺序
• 医院急诊科挂号
• 计算机排序队列顺序

4. 优先级队列封装

function PriorityQueue(){
  //重新创建一个类
	function QueueElement(element,priority){
    	this.element=element
      	this.priority=priority
    }
  	this.item=[]
  PriorityQueue.prototype.enqueue=function(element,priority){
    //创建queueElement对象
  	var queueElement=new QueueElement(element.priority)
    if(this.item.length==0){
    	this.item.push(queueElement)
    }else{
    	var add=false
        for(var i=0;i<this.item.length;i++){
        	if(queueElement.priority<this.item[i].priority){
            	this.item.splice(i,0,queueElement)
              add=true
              break
            }
          if(!add){
          	this.item.push(queueElement)
          }
        }
    }
  }
  //从队列删除前端元素
  PriorityQueue.prototype.dequeue=function(){
  	return this.item.shift()
  }
  //查看前端的元素
  PriorityQueue.prototype.front=function(){
  	return this.item[0]
  }
  // 查看队列是否为空
  PriorityQueue.prototype.isEmepty=function(){
  	return this.item.length==0
  }
  //查看队列元素个数
  PriorityQueue.prototype.size=function(){
  	return this.item.length
  }
  //toString方法
  PriorityQueue.prototype.toString=function(){
  	var resultString=''
    this.item.forEach(e=>{
    	resultString+=e.element
    })
    return resultString
  }
}

链表结构

1. 不同于数组，链表中元素在内存中不必是连续的空间，可以充分利用计算机的内存实现灵活的内存动态管理
2. 链表的每个元素由一个存储元素本身的节点和指向下一个元素的引用（指针）组成
3. 链表在插入和删除数据时，时间复杂度可以达到O（1），相对数组效率高很多
4. 链表访问任何一个位置的元素时，都需要从头访问，无法通过下标直接访问元素，需要通过从头一个一个访问
5. 链表封装

function LinkedList(){
	function Node(data){
    	this.data=data
      	this.next=null
    }
  //属性
  	this.head=null
  	this.length=0
//添加元素 
  LinkedList.prototype.append=function(data){
  	var newNode=new Node(data)
    //判断链表是否为空
    if(this.length==0){
    	this.head=newNode
    }else{
    	var current=this.head
        while(current.next){
        	current=current.next
        }
      	current.next=newNode
      	this.length+=1
    }
  }
  //toString方法
  LinkedList.prototype.toString=function(){
  	var current=this.head
    var resultStr=""
    while(current){
    	resultStr+=current.data
      	current=current.next
    }
    return resultStr
  }
  //insert插入
  LinkedList.prototype.insert=function(position,data){
    //判断position是否越界
  	if(position>this.length||position<0) return false
    var neoNode=new Node(data)
    //是否插入为第一个
    if(position==0){
      	newNode.next=this.head
    	this.head=newNode
    }else{
      //除了获取当前的，还要获取之前的，插入需要改变两个元素
    	var current=this.head
        var previous=null
        var len=0
        while(len++<position){
          	previous=current
        	current=current.next
        }
      	previous.next=newNode
      	newNode.next=current
    }
    this.length+=1
    return true
  }
  //get方法
  LinkedList.prototype.insert=function(position){
  	if(position<0||position>=this.length) return false
   	var current=this.head
    var index=0
    while(index++<position){
    	current=current.next
    }
    return current.data
  }
  //update方法
  LinkedList.prototype.update=function(position,data){
  	if(position<0||position>=this.length) return false
   	 var current=this.head
     var index=0
     while(index++<position){
     	current=current.next
     }
    current.data=data
    return true
  }
  //indexOf方法
  LinkedList.prototype.indexOf=function(data){
  	var current=this.head
    var index=0
    while(current){
    	if(current.data==data){
        	return index
        }
      	current=current.next
      	index+=1
    }
    return -1
  }
  //removeAt方法
  LinkedList.prototype.removeAt=function(position){
  	if(position<0||position>=this.length) return false
    if(position==0){
    	this.head=this.head.next
    }else{
      	var index=0
   		var current=this.head
    	var previous=null
    	while(index++<position){
    	previous=current
      	current=current.next
    	}
      	previous.next=current.next
    }
    this.length-=1
  }
  //remove方法
  LinkedList.prototype.remove=function(data){
  	var index=this.indexOf(data)
    return this.removeAt(index)
  }
  //isEmepty方法
  LinkedList.prototype.isEmepty=function(){
  	return this.length==0
  }
  //size方法
  LinkedList.prototype.size=function(){
  	return this.length
  }
}

双向链表结构

1. 既可以从头遍历到尾，又可以从尾遍历到头
2. 在删除和插入节点时，需要处理四个引用
3. 相比于单项列表，占用内存空间更大
4. 双向链表封装

function DobulyLinkedList(){
  //定义属性
	this.length=0
  	this.head=null
  	this.tail=null
  	function Node(data){
    	this.data=data
      	this.next=null
      	this.prev=null
    }
  // 定义添加方法
  DobulyLinkedList.prototype.append=function(data){
  	var newNode=new Node(data)
    if(this.length==0){
    	this.head=newNode
      	this.tail=newNode
    }else{
    	this.tail.next=newNode
      	newNode.prev=this.tail
      	this.tail=newNode
    }
    this.length+=1
  }
  // 定义toString方法
  DobulyLinkedList.prototype.toString=function(){
  	return this.backwardString()
  }
  // 定义从后往前toString方法
  DobulyLinkedList.prototype.forwardString=function(){
  	var current=this.tail
    var resultStr=""
    while(current){
    	resultStr+=current.data
      	current=current.prev
    }
    return resultStr
  }
  // 定义从前往后toString方法
  DobulyLinkedList.prototype.backwardString=function(){
  	var current=this.head
    var resultStr=""
    while(current){
    	resultStr+=current.data
      	current=current.next
    }
    return resultStr
  }
  //定义插入方法
  DobulyLinkedList.prototype.insert=function(position,data){
    var newNode=new Node(data)
  	if(position<0||position>this.length) return false
    if(this.length=0){
    	this.head=newNode
      	this.tail=newNode
    }else{
    	if(position==0){
        	this.head.prev=newNode
          	newNode.next=this.head
          	this.head=newNode
        }else if(position==this.length){
        	this.tail.next=newNode
          	newNode.prev=this.tail
          	this.tail=newNode
        }else{
        	var current=this.head
            var index=0
            while(index++<position){
              	current=current.next
            }
          	newNode.prev=current.prev
          	newNode.next=current
          	current.prev.next=newNode
          	current.prev=newNode
        }
    }
     this.length+=1
     return true
  }
  // 定义get方法
  DobulyLinkedList.prototype.get=function(position){
  	if(position<0||position>=this.length) return false
    if(this.length>=position){
    	var index=0
    	var current=this.head
   		 while(index++<position){
    		current=current.next
    	}
      	return current.data
    }else{
    	var index=this.length
        var current=this.tail
        while(index-->position){
        	current=current.prev
        }
      	return current.data
    }
  }
  //定义indexOf方法
  DobulyLinkedList.prototype.indexOf=function(data){
  	var index=0
    var current=this.head
    while(current){
    	if(current.data==data){
        	return index
        }
      	current=current.next
      	index+=1
    }
    return -1
  }
  // 定义update方法
  DobulyLinkedList.prototype.update=function(position,data){
  	if(position<0||position>=this.length) return false
    var index=0
    var current=this.head
    while(index++<position){
    	current=current.next
    }
    current.data=data
    return true
  }
  // 定义removeAt方法
  DobulyLinkedList.prototype.removeAt=function(position){
  	if(position<0||position>=this.length) return false
    if(this.length==1){
    	this.head=null
      	this.tail=null
    }else{
    	if(position==0){
        	this.head.next.prev=null
          	this.head=this.head.next
        }else if(position==this.length-1){
        	this.tail.prev.next=null
          	this.tail=this.tail.prev
        }else{
        	var index=0
            var current=this.head
            while(index++<position){
            	current=current.next
            }
          	current.next.prev=current.prev
          	current.prev.next=current.next
        }
    }
    this.length-=1
    return true
  }
  // 定义remove方法
  DobulyLinkedList.prototype.remove=function(data){
  	return this.removeAt(this.indexOf(data))
  }
  //定义isEmpty方法
  DobulyLinkedList.prototype.isEmpty=function(){
  	return this.length==0
  }
  //定义size方法
  DobulyLinkedList.prototype.size=function(){
  	return this.length
  }
}