JavaScript 中的優先順序佇列

Shraddha Paghdar 2022年5月10日
JavaScript 中的優先順序佇列

在 JavaScript 中,優先順序佇列是一種向佇列新增優先順序維度的資料結構。佇列按照到達的順序列出取走的物品。

例如,在藥店排隊等候藥品的人的行為類似於佇列:FIFO(先進先出)。優先順序佇列為每個專案的值新增一個優先順序。

如果 PQ 的所有元素具有相同的優先順序,則它的行為類似於常規佇列。今天的文章將教我們如何在 JavaScript 中實現優先順序佇列。

JavaScript 中的優先順序佇列

Priority Queue 是一個簡單的佇列,具有如下高階屬性。

  1. 優先順序佇列中的每個專案都有一個與之關聯的優先順序。
  2. 根據優先順序將專案新增到佇列中。
  3. 優先順序較低的專案首先被刪除。
  4. 優先順序佇列可以使用兩種方法設計:第一種情況,我們可以在佇列末尾新增佇列項,並根據優先順序從佇列中刪除項。在第二種情況下,我們可以根據優先順序將專案新增到佇列中,並從頭開始將它們從佇列中移除。

示例程式碼:

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 "

執行程式碼

Shraddha Paghdar avatar Shraddha Paghdar avatar

Shraddha is a JavaScript nerd that utilises it for everything from experimenting to assisting individuals and businesses with day-to-day operations and business growth. She is a writer, chef, and computer programmer. As a senior MEAN/MERN stack developer and project manager with more than 4 years of experience in this sector, she now handles multiple projects. She has been producing technical writing for at least a year and a half. She enjoys coming up with fresh, innovative ideas.

LinkedIn