迹忆客 专注技术分享

当前位置:主页 > 学无止境 > WEB前端 > JavaScript >

JavaScript 中的优先级队列

作者:迹忆客 最近更新:2024/03/21 浏览次数:

在 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 "

运行代码

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

在 JavaScript 中返回 False

发布时间:2024/03/21 浏览次数:166 分类:JavaScript

本文解释 JavaScript 中的 return false 和 preventDefault 语句;何时何地使用这些语句,它们之间有什么区别。

使用 JavaScript 获取当前 URL

发布时间:2024/03/21 浏览次数:197 分类:JavaScript

在本教程中,我们将讨论如何使用四种不同的方法在 JavaScript 中获取 URL。这些方法将使用 window.location.href、document.location.href、document.URL 和 document.baseURI。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便