「数据结构与算法Javascript描述」队列

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，「先进先出」，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。

队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

1. 对队列的操作

队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。下图 演示了这两个操作。

队列的另外一项重要操作是读取队头的元素。这个操作叫做 peek()。该操作返回队头元 素，但不把它从队列中删除。除了读取队头元素，我们还想知道队列中存储了多少元素，可以使用 length 属性满足该需求；要想清空队列中的所有元素，可以使用 clear() 方法来实现。

2. 队列的实现

使用数组来实现队列看起来顺理成章。JavaScript 中的数组具有其他编程语言中没有的优点，数组的 push() 方法可以在数组末尾加入元素，shift() 方法则可删除数组的第一个元素。

push() 方法将它的参数插入数组中第一个开放的位置，该位置总在数组的末尾，即使是个空数组也是如此。

接下来准备开始实现 Queue 类，先从构造函数开始：

function Queue() {
  this.data = [];
}

enqueue() 方法向队尾添加一个元素：

Queue.prototype.enqueue = function(element) {
  this.data.push(element);
}

dequeue() 方法删除队首的元素：

Queue.prototype.dequeue = function() {
  return this.data.shift();
}

可以使用如下方法读取队首和队尾的元素：

Queue.prototype.front = function() {
  return this.data[0];
}
Queue.prototype.back = function() {
  return this.data[this.data.length - 1];
}

还需要 toString() 方法显示队列内的所有元素：

Queue.prototype.toString = function() {
  let retStr = '';
  for(const element of this.data) {
    retStr += element + '\n';
  }
  return retStr;
}

最后，需要一个方法判断队列是否为空：

Queue.prototype.empty = function() {
  return this.data.length === 0;
}

下面我们来测试一下 Queue 类：

const q = new Queue();
q.enqueue("夏安1");
q.enqueue("夏安2");
q.enqueue("夏安3");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue: " + q.front());
console.log("Back of queue: " + q.back());

输出为：

夏安1
夏安2
夏安3
夏安2
夏安3
Front of queue: 夏安2
Back of queue: 夏安3

3. 优先队列

在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的数据结构来进行模拟。

从优先队列中删除元素时，需要考虑优先权的限制。比如医院急诊科（Emergency Department）的候诊室，就是一个采取优先队列的例子。当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。