JavaScript: Implement a Priority Queue

1. Introduction

A Priority Queue is a special type of queue where each element has a priority associated with it. Elements are dequeued based on their priorities, with higher-priority elements being dequeued before lower-priority elements.

2. Program Overview

In this program, we will implement a basic priority queue using an array. Each item in the priority queue will be an object containing the data and its priority.

3. Code Program

// Define the structure for the queue item
function QueueItem(data, priority) {
    this.data = data;
    this.priority = priority;
}

// Define the Priority Queue class
function PriorityQueue() {
    this.items = [];
}

// Add a method to enqueue an item
PriorityQueue.prototype.enqueue = function(data, priority) {
    var queueItem = new QueueItem(data, priority);
    var added = false;

    // Find the right spot based on the priority and insert the item
    for (var i = 0; i < this.items.length; i++) {
        if (this.items[i].priority > queueItem.priority) {
            this.items.splice(i, 0, queueItem);
            added = true;
            break;
        }
    }

    if (!added) {
        this.items.push(queueItem);
    }
};

// Add a method to dequeue an item
PriorityQueue.prototype.dequeue = function() {
    if (this.items.length == 0) {
        return "Underflow";
    }
    return this.items.shift().data;
};

// Create a new priority queue and perform some operations
var pq = new PriorityQueue();
pq.enqueue("Task 1", 2);
pq.enqueue("Task 2", 1);
pq.enqueue("Task 3", 3);

console.log(pq.dequeue());  // Task 2 (because it has the highest priority)
console.log(pq.dequeue());  // Task 1

Output:

Task 2
Task 1

4. Step By Step Explanation

1. QueueItem is a simple structure to hold the data and its associated priority.

2. The PriorityQueue class has an array items that will store the queue elements.

3. The enqueue method accepts data and its priority, creates a new QueueItem, and inserts it into the right spot in the queue based on the priority.

4. The dequeue method simply removes and returns the first item from the array (highest priority).

5. In our test case, we enqueue three tasks with varying priorities. When dequeuing, "Task 2" comes out first because it has the highest priority, followed by "Task 1" with the next highest priority.