Implementing priority queue in JavaScript

In this blog, you’re going learn how to implement a Priority Queue in JavaScript. But what makes this tutorial even more interesting is that we’ll explore two different approaches using both an array and a linked list. We will be using object oriented programming approach using class and methods. So, keep reading to learn.

A priority queue is a data structure where each element is associated with a priority, and elements are served based on their priority. Think of it like a queue where elements with higher priority get served before those with lower priority. This is a powerful concept used in various real-world applications such as task scheduling and job processing. In cases where two elements share the same priority, the priority queue behaves like a regular queue, adhering to the FIFO principle.

Now, let’s jump into the first implementation using an array. We’ll store elements along with their priorities in the array and sort it based on priority. Let’s walk through the code.

class PriorityQueue {
  constructor() {
    this.elements = [];
  }

  enqueue(element, priority) {
    const queueElement = { element, priority };

    if (this.isEmpty()) {
      this.elements.push(queueElement);
    } else {
      let added = false;

      for (let i = 0; i < this.elements.length; i++) {
        if (priority < this.elements[i].priority) {
          this.elements.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }

      if (!added) {
        this.elements.push(queueElement);
      }
    }
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.elements.shift().element;
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.elements[0].element;
  }

  isEmpty() {
    return this.elements.length === 0;
  }

  size() {
    return this.elements.length;
  }
}

// Example usage:
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue("Task 1", 2);
priorityQueue.enqueue("Task 2", 1);
priorityQueue.enqueue("Task 3", 3);
priorityQueue.enqueue("Task 4", 2);

console.log(priorityQueue.dequeue()); // Output: Task 2
console.log(priorityQueue.dequeue()); // Output: Task 1
console.log(priorityQueue.dequeue()); // Output: Task 4
console.log(priorityQueue.dequeue()); // Output: Task 3

In this example, each element in the priority queue is an object with an element and a priority. The enqueue method adds elements to the queue based on their priority, and the dequeue method removes and returns the element with the highest priority. A priority value of 1 has higher precedence than a priority value of 2. Lower values indicate higher priority.

Another simpler approach can be we use the push method to add elements to the array and then sort the array based on priority.

//rest of the code
 enqueue(element, priority) {
    const queueElement = { element, priority };
    this.elements.push(queueElement);
    this.elements.sort((a, b) => a.priority - b.priority);
  }
//rest of the code

Implementing priority queue using linked list