js实现栈

栈是一种先进后出的数据结构，可以想象为一个箱子，只有一面是开口，先放入的东西会被放在最底部，最后放入的在最上面。所以往出取的时候就只能先取出最上面的，然后一层一层才能取出最底部的。

封装栈类
function Stack(){
  //栈中属性
  this.items = [];
//1.压栈
Stack.prototype.push = function(element){
  this.items .push(element);
}
//2.出栈
Stack.prototype.pop= function(element){
  this.items .pop(element);
}
//3.查看栈顶
Stack.prototype.peek= function(){
  return this.items[this.items.length - 1];
}
//4.栈是否为空
Stack.prototype.isEmpty= function(){
  return this.items.length === 0;
}
//5.获取栈元素个数
Stack.prototype.size= function(){
  return this.items.length;
}
//6.toString方法
Stack.prototype.toString= function(){
  return this.items.join(' ');
}
}

var stack = new Stack();

js实现队列

队列是一种先进先出的数据结构，可以想象成吃饭排队，排在队头的人先取到饭，按顺序取饭，最后一个排队的人只能等前面的人都取完了轮到自己才能取到。

封队列类
function Queue(){
  //栈中属性
  this.items = [];
//1.进入队列
Queue.prototype.queueIn= function(element){
  this.items .push(element);
}
//2.出队列
Queue.prototype.queueOut= function(element){
  this.items .shift(element);
}
//3.队列是否为空
Queue.prototype.isEmpty= function(){
  return this.items.length === 0;
}
//4.获取队列元素个数
Queue.prototype.size= function(){
  return this.items.length;
}
//6.toString方法
Queue.prototype.toString= function(){
  return this.items.join(' ');
}
//7.获取当前列表数据
Queue.prototype.getList= function(){
  return this.items;
}
}

击鼓传花游戏算法

小时候我们玩过一种游戏叫击鼓传花，几个人围坐在一堆，击鼓一段时间，将一个花球在人圈中依次传递，在鼓声停止之时，将此刻手中拿着花球的人淘汰，剩下的人继续游戏，最后剩下一人为胜利者。

//用队列的思想解决这个算法
function makeGame(peopleList,num){
  var que = new Queue();
  peopleList.map(function(item){
    que.queueIn(item);
  })
  
while(que.size > 1){
  for(var i= 0;i<num-1;i++){
      que.queueIn(que.queueOut())
    }
    que.queueOut() 
  }
}

que.getList()[0] //为最后获胜者

链表

数组：内存空间是连续的，当内存空间不足时，元素需要扩容然后把之前的数据复制过来。增加与删除操作其他元素需要位移。
链表：元素在内存中不必是连续的空间，链表的每个元素是由一个存储元素本身的节点和一个指向下一个元素的引用(指针或连接)组成。
链表的优点：1.内存空间不鄙是连续的，可充分利用计算机内存，实现灵活的动态内存管理。
2.链表不必在创建时就确定大小，并且大小可以无限延伸下去。
3.链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多。

//封装链表  单向链表
function Linked(){
    //内部类 节点
  function Node(data){
    this.data = data;
    this.next = null;
  }
  this.head = null;
  this.length = 0;

//追加方法
Linked.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;
    }
    //最后next指向新节点
      current.next = new Node(data);
  }
    this.length +=1;
}
}