image.png

Queue与Stack类似。唯一不同的是，Queue使用的是FIFO原则（先进先出）。换句话说，当你排队等候公交车时，队列中的第一个总是先上车。

队列具有以下方法：

enqueue：输入队列，在最后添加一个元素
dequeue：离开队列，删除前元素并返回
front：得到第一个元素
isEmpty：确定队列是否为空
size：获取队列中元素的数量

JavaScript中的数组具有Queue的某些属性，因此我们可以使用数组来构造Queue的示例：

function Queue() {
  var collection = [];
  this.print = function () {
    console.log(collection);
  }
  this.enqueue = function (element) {
    collection.push(element);
  }
  this.dequeue = function () {
    return collection.shift();
  }
  this.front = function () {
    return collection[0];
  }

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

优先队列

队列还有另一个高级版本。为每个元素分配优先级，并将根据优先级对它们进行排序：

function PriorityQueue() {

  ...

  this.enqueue = function (element) {
    if (this.isEmpty()) {
      collection.push(element);
    } else {
      var added = false;
      for (var i = 0; i < collection.length; i++) {
        if (element[1] < collection[i][1]) {
          collection.splice(i, 0, element);
          added = true;
          break;
        }
      }
      if (!added) {
        collection.push(element);
      }
    }
  }
}

测试：

var pQ = new PriorityQueue();
pQ.enqueue([ gannicus , 3]);
pQ.enqueue([ spartacus , 1]);
pQ.enqueue([ crixus , 2]);
pQ.enqueue([ oenomaus , 4]);
pQ.print();

返回：

[
  [  spartacus , 1 ],
  [  crixus , 2 ],
  [  gannicus , 3 ],
  [  oenomaus , 4 ]
]