JavaScript实现队列、优先队列与循环队列详解

function Queue() {
  var items = [];
  this.enqueue = function (ele) {
    items.push(ele);
  };//入队
  this.dequeue = function () {
    return items.shift();
  };//出队
  this.front = function () {
    return items[0];
  };//查看队头元素
  this.isEmpty = function () {
    return items.length === 0;
  };//判断队列是否为空
  this.size = function () {
    return items.length;
  };//队列大小
  this.clear = function () {
    items = [];
  };//清空队列
  this.print = function () {
    console.log(items.toString());
  };//打印队列
}
var queue = new Queue(); //声明队列的实例

var queue = new Queue();
console.log("队列是否为空： " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("当前队列：");
queue.print();
console.log("出队的人： " + queue.dequeue());
console.log("当前队列：");
queue.print();

function PriorityQueue() {
  var items = [];
  function QueEle(ele, priority){ //封装我们的元素为一个对象
    this.ele = ele; //元素
    this.priority = priority; //优先级
  }
  this.enqueue = function (ele, priority) {
    var queObj = new QueEle(ele, priority); //创建队列元素对象
    if(this.isEmpty()){ //如果队列是空的，直接插入
      this.push(queObj);
    }else{
      var bAdded = false;
      for(var i = 0, len = items.length; i < len; i++){ 
        if(priority < items[i].priority){
          items.splice(i, 0, queObj); // 循环队列，如果优先级小于这个位置元素的优先级，插入
          bAdded = true;
          break;
        }
      }
      if(!bAdded){
        items.push(queObj); // 如果循环一圈都没有找到能插队的位置，直接插入队列尾部
      }
    }
  };
  this.dequeue = function () {
    return items.shift();
  };
  this.front = function () {
    return items[0];
  };
  this.isEmpty = function () {
    return items.length === 0;
  };
  this.size = function () {
    return items.length;
  };
  this.clear = function () {
    items = [];
  };
  this.print = function () {
    //这个地方稍微修改一下下
    var temp = [];
    for(var i = 0, len = items.length; i < len; i++){
      temp.push(items[i].ele);
    }
    console.log(temp.toString());
  };
}

var pQueue = new PriorityQueue();
pQueue.enqueue('Mr.A', 3);
pQueue.enqueue('Mr.B', 3);
pQueue.enqueue('Mr.C', 3);
console.log("原队列:");
pQueue.print();
pQueue.enqueue('VIP', 2);
pQueue.enqueue('SVIP', 1);
console.log("新队列:");
pQueue.print();

function hotPotato(pepoleList, frequency){ //参数：表示人的数组，传花的频率
  var queue = new Queue();
  for(var i = 0, len = pepoleList.length; i < len; i++){
    queue.enqueue(pepoleList[i]); //初始化，进入队列
  }
  var eliminated;//被淘汰的同学
  while(queue.size() > 1){ //只要队列至少还有两个人，就一直循环
    for(var i = 0; i < frequency; i++){//出队入队，模拟循环效果
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();//清算
    console.log(eliminated + '被淘汰');
  }
  return queue.dequeue();//返回队列中的最后一人
}
var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F'];
var gameWinner = hotPotato(pepole, 12);
console.log('全场最佳:' + gameWinner);