JS数据结构与算法-队列

function Queue() {
  var items = [];
  //这里是属性和方法
}

this.enqueue = function(element) {
  //用push方法，将元素添加到数组末尾
  items.push(element);
};

this.dequeue = function() {
  //shift方法，移除数组中的第一项（索引为0）的元素
  return items.shift();
};

this.front = function() {
  return items.shift();
};

this.isEmpty = function() {
  return items.length == 0;
};

this.clear = function() {
  items = [];
};

this.size = function(){
  return items.lenght;
};

function Queue() {
  var items = [];

  this.enqueue = function(element) {
    items.push(element);
  };

  this.dequeue = function() {
    return items.shift();
  };

  this.front = function() {
    return items[0];
  };

  this.isEmpty = function() {
    return items.length == 0;
  };

  this.clear = function() {
    items = [];
  };

  this.size = function() {
    return items.length;
  };

  this.print = function() {
    console.log(items.toString());
  }
}

var queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);

queue.print(); // "1,2"

function PriorityQueue() {
  //声明一个items用于保存元素
  var items = [];

  //创建一个QueueElement类，用于保存元素和其在队列中的优先级(priority越小，优先级越高)
  function QueueElement(element,priority) {
    this.element = element;
    this.priority = priority;
  }

  this.enqueue = function(element,priority) {
    var queueElement = new QueueElement(element,priority);
    //如果队列为空，可以将元素入列
    if(this.isEmpty()) {
      items.push(queueElement);
    }else {
      var added = false;
      //反之就循环队列里面的每一个元素，比较优先级，如果priority小(优先级越高)的话，就用splice()方法放在该元素的前面
      for(var i=0; i<items.length; i++) {
        if(queueElement.priority < items[i].priority) {
          items.splice(i,0,queueElement);
          added = true;
          break;
        }
      }
      //如果添加的元素的priority比队列中的每一个元素都要大的话，就把它添加到队列的最后面
      if(!added) {
        items.push(queueElement);
      }
    }
  };

  this.isEmpty = function() {
    return items.length === 0;
  };

  this.print = function() {
    console.log(items);
  };
}

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("one",1);
priorityQueue.enqueue("two",2);
priorityQueue.enqueue("zero",0);
priorityQueue.enqueue("four",4);

priorityQueue.print(); // "0,1,2,4"

function hotPotato(nameList,num) {
  var queue = new Queue();

  //将传入的nameList遍历，将每一项添加到队列中
  for(var i=0; i<nameList; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = '';
  //如果队列里的size大于1，就一直循环下去
  while(queue.size() > 1) {
    //将第一项放到最后一项，循环给定的num
    for(var i=0; i<num; i++) {
      queue.enqueue(queue.dequeue);
    }
    //传递次数达到了给定的数值，（移除第一项）
    eliminated = queue.dequeue();
    console.log(eliminated + '淘汰')；
  }
  //返回队列中仅有的最后一项
  return queue.dequeue();
}

var names = ['a','b','c','d','e'];
var winner = hotPotato(names,7);
console.log('胜利者' + winner);