迹忆客 专注技术分享

在 JavaScript 中，优先级队列是一种向队列添加优先级维度的数据结构。队列按照到达的顺序列出取走的物品。

例如，在药店排队等候药品的人的行为类似于队列：FIFO（先进先出）。优先级队列为每个项目的值添加一个优先级。

如果 PQ 的所有元素具有相同的优先级，则它的行为类似于常规队列。今天的文章将教我们如何在 JavaScript 中实现优先级队列。

JavaScript 中的优先级队列

Priority Queue 是一个简单的队列，具有如下高级属性。

示例代码：

class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}
class PriorityQueue {
  constructor() {
    this.queueItems = [];
  }
  enqueueFunction(element, priority) {
    let queueElement = new QueueElement(element, priority);
    let contain = false;

    for (let i = 0; i < this.queueItems.length; i++) {
      if (this.queueItems[i].priority > queueElement.priority) {
        this.queueItems.splice(i, 0, queueElement);
        contain = true;
        break;
      }
    }
    /* if the input element has the highest priority push it to end of the queue
     */
    if (!contain) {
      this.queueItems.push(queueElement);
    }
  }
  dequeueFunction() {
    /* returns the removed element from priority queue. */
    if (this.isPriorityQueueEmpty()) {
      return 'No elements present in Queue';
    }
    return this.queueItems.shift();
  }
  front() {
    /* returns the highest priority queue element without removing it. */
    if (this.isPriorityQueueEmpty()) {
      return 'No elements present in Queue';
    }
    return this.queueItems[0];
  }
  rear() {
    /* returns the lowest priority queue element without removing it. */
    if (this.isPriorityQueueEmpty()) {
      return 'No elements present in Queue';
    }
    return this.queueItems[this.queueItems.length - 1];
  }
  isPriorityQueueEmpty() {
    /* Checks the length of an queue */
    return this.queueItems.length === 0;
  }
  /* prints all the elements of the priority queue */
  printPriorityQueue() {
    let queueString = '';
    for (let i = 0; i < this.queueItems.length; i++)
      queueString += this.queueItems[i].element + ' ';
    return queueString;
  }
}

在上面的示例中，我们定义了 PriorityQueue 类的框架。我们使用了一个自定义的 QueueElement 类，其中包含两个 Property 和 Priority 元素。

我们在 PriorityQueue 类中使用了一个数组来实现优先队列，这个数组是 QueueElement 的容器。我们将 1 视为最高优先级项目，你可以根据自己的要求进行更改。

1. enqueueFunction()：在这个方法中，我们创建一个带有元素属性和优先级的 queueElement。然后我们遍历队列以根据其优先级找到 queueElement 的正确位置，并根据其优先级将元素添加到队列中。
2. dequeueFunction()：该函数从队列的前面移除一个元素，因为具有最高优先级的元素存储在优先级队列的前面。我们使用修改后的数组方法将元素出列。
3. front()：该函数返回优先队列的最前面的元素。我们返回数组的元素 0 以获取优先级队列的开始。
4. rear()：此函数返回队列中的最后一项或具有最低优先级的项。
5. isPriorityQueueEmpty()：我们使用数组的 length 属性来获取长度，如果为 0，则优先队列为空。
6. printPriorityQueue()：在此方法中，我们将优先级队列中每个项目的项目属性连接成一个字符串。根据优先级打印队列中的项目，从最高到最低

现在让我们使用优先队列的第一个代码示例并尝试上面描述的不同方法。

示例代码：

let priorityQueue = new PriorityQueue();
console.log(priorityQueue.isPriorityQueueEmpty());

console.log(priorityQueue.front());

priorityQueue.enqueueFunction('Sonya', 2);
priorityQueue.enqueueFunction('John', 1);
priorityQueue.enqueueFunction('Alma', 1);
priorityQueue.enqueueFunction('Alexander', 2);
priorityQueue.enqueueFunction('Arthur', 3);

console.log(priorityQueue.printPriorityQueue());
console.log(priorityQueue.front().element);
console.log(priorityQueue.rear().element);
console.log(priorityQueue.dequeueFunction().element);

priorityQueue.enqueueFunction('Harold', 2);
console.log(priorityQueue.printPriorityQueue());

输出：

true
"No elements present in Queue"
"John Alma Sonya Alexander Arthur "
"John"
"Arthur"
"John"
"Alma Sonya Alexander Harold Arthur "

运行代码