JS数据结构与算法-队列

1. 定义

队列是遵循FIFO（First In First Out，先进先出）原则的一组有序的项。

在现实中，最常见的队列的例子就是排队：

来自《javascript数据结构与算法》

2. 创建队列

• 声明类并声明一个数组用于存储队列中元素的数据结构。

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

• 实现enqueue()方法，向队列尾部添加数个新的项。

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

• 实现dequeue()方法，移除队的第一项（队首），并返回被移除的元素。

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

• front()方法，返回队列中的第一个元素，不改变队列。

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

• isEmpty()方法，如果队列中不包含任何元素，返回true，否则返回false。

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

• clear()方法，清空队列元素

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

• size()方法，返回队列包含的元素个数。

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"

3. 优先队列
   现实生活中也有优先队列，如头等舱>商务舱>经济舱，接下来我们用代码实现下优先队列。

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"

4. 循环队列
   循环队列的一个例子就是击鼓传花游戏（HotPotato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

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);

参考学习 ：

《javascript数据结构与算法学习》
《数据结构与算法javascript描述》