场景

生存中相似优先队列的场景：

  • 优先排队的人，优先解决。 (买票、结账、WC)。
  • 排队中，有紧急情况（非凡状况）的人可优先解决。

优先队列

优先级队列次要思考的问题：

  • 每个元素不再只是一个数据，还蕴含优先级。
  • 在增加元素过程中，依据优先级放入到正确地位。

优先队列的实现

代码实现

class QueueElement { constructor(element, priority) {  this.element = element  this.priority = priority }}// 优先队列类export class PriorityQueue extends Queue { constructor() {  super(); }  // enqueue(element, priority) 入队，将元素按优先级退出到队列中 enqueue(element, priority) {  // 依据传入的元素，创立 QueueElement 对象  const queueElement = new QueueElement(element, priority);  // 判断队列是否为空  if (this.isEmpty()) {   // 如果为空，不必判断优先级，间接增加   this.items.push(queueElement);  } else {   // 定义一个变量记录是否胜利增加了新元素   let added = false;   for (let i = 0; i < this.items.length; i++) {    // 让新插入的元素进行优先级比拟，priority 值越小，优先级越大    if (queueElement.priority < this.items[i].priority) {     // 在指定的地位插入元素     this.items.splice(i, 0, queueElement);     added = true     break;    }   }   // 如果遍历完所有元素，优先级都大于新插入的元素，就将新插入的元素插入到最初   if (!added) {    this.items.push(queueElement);   }  } } // dequeue() 出队 dequeue() {  return super.dequeue() } front() {  return super.front() } isEmpty() {  return super.isEmpty() } size() {  return super.size() } toString() {  let result = ''  for (let item of this.items) {    result += item.element + '-' + item.priority + ' '  }  return result }}