JavaScript实现优先级队列

实现一个优先级队列（Priority Queue）是JavaScript开发中一个常见的问题，本文将介绍如何用JavaScript实现优先级队列。

什么是优先级队列？

优先级队列是一种特殊的队列，每个元素都有一个优先级。出队列时，队列将会按照元素的优先级从高到低出队列。

实现步骤

步骤一、创建优先级队列类

我们可以使用ES6中的class来创建一个优先级队列，代码如下：

class PriorityQueue {
  constructor() {
    this.items = []; // 用数组来保存队列元素
  }

  // 添加新元素到队列
  enqueue(element, priority) {
    // 创建一个包含元素和优先级的对象
    let queueElement = {
      element: element,
      priority: priority
    };

    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority > this.items[i].priority) {
        this.items.splice(i, 0, queueElement); // 使用splice方法将元素插入到指定位置
        added = true;
        break;
      }
    }

    // 如果队列中无元素或者新元素的优先级最小，则将其插入到队尾
    if (!added) {
      this.items.push(queueElement);
    }
  }

  // 从队列中删除元素
  dequeue() {
    return this.items.shift();
  }

  // 查看队列头元素
  front() {
    return this.items[0];
  }

  // 检查队列是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 返回队列长度
  size() {
    return this.items.length;
  }

  // 清空队列
  clear() {
    this.items = [];
  }
}

上述代码中，优先级队列类包含enqueue方法（添加元素）、dequeue方法（删除元素）、front方法（查看队列头元素）、isEmpty方法（检查队列是否为空）、size方法（返回队列长度）等常用的方法。

在enqueue方法中，我们遍历队列元素，如果新元素的优先级大于队列中的某个元素，就将新元素插入到该元素之前。如果新元素优先级最小，则将其插入到队尾。

步骤二、创建优先级队列实例

创建优先级队列实例的过程如下所示：

let pq = new PriorityQueue(); // 创建一个优先级队列实例
pq.enqueue("A", 2); // 添加元素 A，优先级为 2
pq.enqueue("B", 3); // 添加元素 B，优先级为 3
pq.enqueue("C", 1); // 添加元素 C，优先级为 1
console.log(pq.size()); // 输出 3
console.log(pq.front()); // 输出 {element: "B", priority: 3}
console.log(pq.dequeue()); // 输出 {element: "B", priority: 3}，元素 B，优先级为 3 出列
console.log(pq.front()); // 输出 {element: "A", priority: 2}
console.log(pq.size()); // 输出 2

在这个示例中，创建了一个优先级队列pq，并添加了三个元素，元素A的优先级最小，元素B的优先级最大。用console.log输出了队列长度、队列头元素、出队列的元素以及修改后的队列长度。

步骤三、创建一个优先级队列类的继承类

我们还可以创建一个继承自优先级队列类的继承类，这个子类可以实现自己的方法。下面的示例展示了如何创建一个继承类ExtendedPriorityQueue：

class ExtendedPriorityQueue extends PriorityQueue {
  constructor() {
    super(); // 调用父类的构造函数
    this.map = new Map(); // 为子类添加一个新属性
  }

  // 重写enqueue方法，同时在map中保存元素
  enqueue(element, priority) {
    super.enqueue(element, priority);
    this.map.set(element, priority);
  }

  // 重写dequeue方法，同时在map中删除元素
  dequeue() {
    let dequeued = super.dequeue();
    this.map.delete(dequeued.element);
    return dequeued;
  }

  // 新增方法，获取某个元素的优先级
  getPriority(element) {
    return this.map.get(element);
  }
}

let epq = new ExtendedPriorityQueue(); // 创建一个子类的实例
epq.enqueue("A", 2); // 添加元素 A，优先级为 2
epq.enqueue("B", 3); // 添加元素 B，优先级为 3
epq.enqueue("C", 1); // 添加元素 C，优先级为 1
console.log(epq.size()); // 输出 3
console.log(epq.front()); // 输出 {element: "B", priority: 3}
console.log(epq.getPriority("A")); // 输出 2
console.log(epq.getPriority("B")); // 输出 3

在这个示例中，我们创建了一个ExtendedPriorityQueue类，继承自PriorityQueue类，并重写了enqueue、dequeue方法。同时，子类新增一个方法getPriority，用来获取某个元素的优先级。

总结

本文介绍了如何使用JavaScript实现优先级队列。步骤包括创建优先级队列类、创建优先级队列实例、创建优先级队列类的继承类等。如果您想在JavaScript开发中使用优先级队列，可以按照本文的步骤实现。