Priority Queue in JavaScript

In JavaScript, the priority queue is a data structure that adds a priority dimension to the queue. The queue lists items picked up in the same order that they arrived.

For example, a queue of people waiting for medicine at the medical store behaves like a queue: FIFO (first in, first out). The priority queue adds a priority to the value of each item.

If all elements of a PQ have the same priority, it behaves like a regular queue. Today’s post will teach us how to implement the priority queue in JavaScript.

Priority Queue in JavaScript

Priority Queue is a simple queue with advanced properties as follows.

1. Each item in the priority queue has a priority associated with it.
2. Items are added to the queue based on priority.
3. Items with lower priority are removed first.
4. A priority queue can be designed using two approaches: in the first case, we can add the queue item at the end of the queue and remove items from the queue based on priority. In the second case, we can add items to the queue according to priority and remove them from the queue from the beginning.

Example Code:

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;
  }
}

In the example above, we defined the skeleton of the PriorityQueue class. We used a custom QueueElement class with two Property and Priority elements.

We used an array in the PriorityQueue class to implement the priority queue, and this array is a container of QueueElement. We consider 1 the highest priority item, and you can change this according to your requirements.

1. enqueueFunction(): In this method, we create a queueElement with an element property and priority. We then iterate over the queue to find the correct position of the queueElement based on its priority and add an element to the queue according to its priority.
2. dequeueFunction(): This function removes an element from the front of a queue since the element with the highest priority is stored at the front of the priority queue. We used the modified method of an array to dequeue an element.
3. front(): This function returns the front element of the priority queue. We return element 0 of an array to get the start of a priority queue.
4. rear(): This function returns the last item in the queue or the item with the lowest priority.
5. isPriorityQueueEmpty(): We used the length property of an array to get the length, and if it’s 0, then the priority queue is empty.
6. printPriorityQueue(): In this method, we concatenate the item properties of each item in the priority queue into a string. Prints the item in the queue according to priority, starting from highest to lowest

Now Let’s use the 1st code example of Priority Queue and experiment with its different method described above.

Example Code:

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());

Output:

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

Run Code