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

To implement a priority queue using a linked list in JavaScript, you can define a class for both the priority queue and the linked list node. Each node in the linked list contains an element and its associated priority. The priority queue operations, such as enqueue and dequeue, are then implemented based on the linked list.

Here’s an example implementation:

class Node {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
    this.next = null;
  }
}

class PriorityQueue {
  constructor() {
    this.front = null;
  }

  enqueue(element, priority) {
    const newNode = new Node(element, priority);

    if (!this.front || priority < this.front.priority) {
      newNode.next = this.front;
      this.front = newNode;
    } else {
      let current = this.front;

      while (current.next && !(priority < current.next.priority)) {
        current = current.next;
      }

      newNode.next = current.next;
      current.next = newNode;
    }
  }

  dequeue() {
    if (!this.front) {
      return null;
    }

    const removedNode = this.front;
    this.front = this.front.next;
    return removedNode.element;
  }

  peek() {
    return this.front ? this.front.element : null;
  }

  isEmpty() {
    return !this.front;
  }

  size() {
    let count = 0;
    let current = this.front;

    while (current) {
      count++;
      current = current.next;
    }

    return count;
  }
}

// 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, the Node class represents a node in the linked list, and the PriorityQueue class uses this linked list to implement the priority queue operations. The enqueue method inserts elements based on their priority, and the dequeue method removes and returns the element with the highest priority.

If the priority of the new node is less than the priority of the current front element or if the linked list is empty, the new node is inserted at the beginning. Otherwise, it needs to be inserted in the middle or at the end of the linked list.

This loop iterates through the linked list until it finds the correct position for the new node based on its priority. The condition !(priority < current.next.priority) ensures it exits the loop when condition priority < current.next.priority or when current.next node is null

  • newNode.next = current.next;: The newNode.next is set to point to the node that has lower or equal priority.
  • current.next = newNode;: The current.next is updated to point to the newNode, effectively inserting it into the linked list.

If you found this blog helpful, don't forget to share it on social media.

Don't Miss Out! Subscribe to Read Our Latest Blogs.

If you found this blog helpful, share it on social media.

Subscription form (#5)

Leave a Comment

Your email address will not be published. Required fields are marked *

Pin It on Pinterest

Scroll to Top