JavaScript Program to Implement a Priority Queue

Introduction

A Priority Queue is a special type of queue where each element is associated with a priority, and elements are dequeued based on their priority, rather than just the order they were enqueued. A higher-priority element is dequeued before a lower-priority element. If two elements have the same priority, they are dequeued in the order they were enqueued (FIFO behavior for same-priority elements).

This guide will walk you through writing a JavaScript program to implement a priority queue using an array.

Problem Statement

Create a JavaScript program that:

• Implements a Priority Queue.
• Allows operations such as:
  • Enqueue: Adds an element with a priority to the queue.
  • Dequeue: Removes the element with the highest priority.
  • Display: Displays the current state of the priority queue.

Example:

• Input: Enqueue elements with priority {"task": "Clean", "priority": 2}, {"task": "Pay bills", "priority": 1}, {"task": "Cook", "priority": 3}
• Output:
  • Dequeued element: Pay bills
  • Queue after dequeue: [Cook, Clean]

Solution Steps

1. Define the Element Class: Create a class that stores the task and its priority.
2. Define the Priority Queue Class: Implement methods for:
   • Enqueue: Add an element to the queue based on its priority.
   • Dequeue: Remove the element with the highest priority.
   • Display: Show the elements in the queue.
3. Display the Queue: Output the state of the queue after each operation.

JavaScript Program

Step 1: Define the Element Class

// JavaScript Program to Implement a Priority Queue
// Author: https://www.rameshfadatare.com/

class Element {
    constructor(task, priority) {
        this.task = task;
        this.priority = priority;
    }
}

Step 2: Define the Priority Queue Class

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

    // Enqueue: Adds an element in the queue based on its priority
    enqueue(task, priority) {
        const newElement = new Element(task, priority);

        if (this.isEmpty()) {
            // If the queue is empty, add the element
            this.queue.push(newElement);
        } else {
            // Insert the element based on priority
            let added = false;
            for (let i = 0; i < this.queue.length; i++) {
                if (newElement.priority < this.queue[i].priority) {
                    this.queue.splice(i, 0, newElement); // Insert at the right position
                    added = true;
                    break;
                }
            }
            if (!added) {
                this.queue.push(newElement); // Add to the end if it has the lowest priority
            }
        }
        console.log(`Task '${task}' added to the queue with priority ${priority}`);
    }

    // Dequeue: Removes and returns the element with the highest priority
    dequeue() {
        if (this.isEmpty()) {
            console.log("Queue is empty");
            return null;
        }
        const removedElement = this.queue.shift(); // Remove the first element (highest priority)
        console.log(`Task '${removedElement.task}' with priority ${removedElement.priority} dequeued`);
        return removedElement;
    }

    // Check if the queue is empty
    isEmpty() {
        return this.queue.length === 0;
    }

    // Display the current state of the queue
    displayQueue() {
        if (this.isEmpty()) {
            console.log("The queue is empty");
        } else {
            console.log("Current queue:");
            for (let element of this.queue) {
                console.log(`Task: ${element.task}, Priority: ${element.priority}`);
            }
        }
    }
}

Step 3: Example Usage

// Example usage of the Priority Queue
const pq = new PriorityQueue();
pq.enqueue("Clean", 2);
pq.enqueue("Pay bills", 1);
pq.enqueue("Cook", 3);

pq.displayQueue(); // Display queue after adding elements

pq.dequeue(); // Dequeue the highest priority element
pq.displayQueue(); // Display queue after dequeue

Output Example

Task 'Clean' added to the queue with priority 2
Task 'Pay bills' added to the queue with priority 1
Task 'Cook' added to the queue with priority 3
Current queue:
Task: Pay bills, Priority: 1
Task: Clean, Priority: 2
Task: Cook, Priority: 3
Task 'Pay bills' with priority 1 dequeued
Current queue:
Task: Clean, Priority: 2
Task: Cook, Priority: 3

Explanation

Step 1: Define the Element Class

• The Element class represents each element (task) in the priority queue. Each element has:
  • task: The task description.
  • priority: The priority of the task (lower numbers indicate higher priority).

Step 2: Define the Priority Queue Class

• Enqueue: The enqueue() method adds a new element to the queue based on its priority. It inserts the new element at the correct position to maintain the priority order. The queue is sorted in ascending order of priority.
• Dequeue: The dequeue() method removes and returns the element with the highest priority (the first element in the queue).
• isEmpty: This method checks whether the queue is empty by returning true if the queue length is 0.
• Display Queue: The displayQueue() method prints all the elements currently in the queue.

Step 3: Example Usage

• The priority queue is created, and three tasks are enqueued with different priorities. The queue is then displayed, and the highest priority task is dequeued.

Time Complexity

• Enqueue: O(n), where n is the number of elements in the queue (since we may need to insert an element at the correct position).
• Dequeue: O(1), since removing the first element from the queue is constant time.
• Display Queue: O(n), where n is the number of elements in the queue.

Conclusion

This JavaScript program implements a priority queue using arrays. The queue maintains the order of elements based on their priority, and the program supports enqueueing, dequeueing, and displaying the current state of the queue. This is a basic implementation and can be optimized using other data structures like heaps if better performance is required for larger data sets.