So, now we know what is a basic queue, but what about the priority queue? In the priority queue, each element that enters the queue has two values, a priority value and the data. The elements which have the same priority value will be executed based on FIFO (first in and first out) but elements with higher priority than others will be executed first no matter when they were added into the queue.
This is an advanced data structure topic, so we are assuming that you are familiar with how javascript works and the basic functionalities of javascript. To implement a priority queue in JavaScript we must first know how to implement a simple queue in javascript.
Implementing a queue in JavaScript
The data structure concepts like queues, stacks, heaps, or priority queues are implemented using arrays in javascript.
Let’s define a function that will define our structure:
// Later code will be placed inside here
}
We know that queues are implemented with arrays, so we are going to create an array named collections
Inside the function:
Now, to implement the queues data structure we need to implement the following functionalities:
- Enqueue: To add a new element at the end of the list
- Dequeue: To remove the first element from the list
- isEmpty: To check whether the queue is empty or not
- Size: To return the length of the queue
- Front: To return the value of the first element in the list
- Print: To print the queue
These functionalities are all easily added by using the following lines of code:
array= [];
this.print = function() {
console.log(array);
};
this.enqueue = function(newMem) {
array.push(newMem);
};
this.dequeue = function() {
returnarray.shift();
};
this.front = function() {
return array[0];
};
this.size = function() {
returnarray.length;
};
this.isEmpty = function() {
return (array.length === 0);
};
}
Now, that we have our data structure ready, we need to create an object mapped to this structure, we do that by using the line:
Now, we need some elements to be placed in the queue, we do that by using the following lines:
newQueue.enqueue('b');
newQueue.enqueue('c');
To look at how our queue looks right now we can call the print function like so:
We get the following output on our console:
To test, if the First-in and First-out implementation is working correctly, we are going to dequeue an element from the list, and print the foremost value and then print the whole remaining queue with the following lines:
console.log(newQueue.front());
newQueue.print();
The complete code snippet of the Queue structure is:
array= [];
this.print = function () {
console.log(array);
};
this.enqueue = function (newMem) {
array.push(newMem);
};
this.dequeue = function () {
returnarray.shift();
};
this.front = function () {
return array[0];
};
this.size = function () {
returnarray.length;
};
this.isEmpty = function () {
returnarray.length === 0;
};
}
varnewQueue = new Queue();
newQueue.enqueue("a");
newQueue.enqueue("b");
newQueue.enqueue("c");
newQueue.print();
newQueue.dequeue();
console.log(newQueue.front());
newQueue.print();
On executing this code, we can observe the following result on the console:
So, when we called the dequeue function it removed the first element from the list. After that, we checked for the foremost element in the queue which was “b”. Then we printed the queue again and it gave us the remaining queue in the correct order. This means that our queue implementation is working perfectly:
Implementing a priority queue in JavaScript
We know the difference between a normal queue and a priority queue is that the elements inside the priority queue contain a priority value along with their data. This means that all the functionality of the priority queue is the same as a normal queue except for the Enqueue function.
In priority queues, the enqueue function, places the higher priority element before the lower priority element. And if two or more elements have the same priority then newly added elements are placed at the later end of the queue to maintain a first-in and first-out valuation method.
So, keeping that in mind we can write the new Enqueue function for the priority queue with the following lines of code:
var array = [];
// Later code will be placed inside here
};
The first thing we do in the enqueue function is that if the collection is empty, then we just push the element onto the queue:
array.push(newMem);
}
If the queue is not empty:
- then we are going to check the priority of the new element with the priority of every element in the queue
- If the priority of the new element is lower than the collection’s element.The we are going to add the new element at before that collection’s element
- This is because 1 means first priority whereas 2 means second priority
- If the priority of the new element greater in value (lower in actual priority), then we are going to move to the end of the queue and add the element there
var added = false;
for (vari = 0; i<array.length; i++) {
if (newMem[1] < array[i][1]) {
array.splice(i, 0, newMem);
added = true;
break;
}
}
if (!added) {
array.push(newMem);
}
}
The whole enqueue function will look like this:
if (this.isEmpty()) {
array.push(newMem);
} else {
var added = false;
for (vari = 0; i<array.length; i++) {
if (newMem[1] < array[i][1]) {
array.splice(i, 0, newMem);
added = true;
break;
}
}
if (!added) {
array.push(newMem);
}
}
};
The rest of the priority queue functions are pretty much the same as the normal queue, with a slight change in dequeue function to display only the name and not the value of the element. The whole priority queue code snippet is as:
vararray = [];
this.printCollection = function () {
console.log(array);
};
this.enqueue = function (newMem) {
if (this.isEmpty()) {
array.push(newMem);
} else {
var added = false;
for (vari = 0; i<array.length; i++) {
if (newMem[1] <array[i][1]) {
array.splice(i, 0, newMem);
added = true;
break;
}
}
if (!added) {
array.push(newMem);
}
}
};
this.dequeue = function () {
var value = array.shift();
return value[0];
};
this.front = function () {
returnarray[0];
};
this.size = function () {
returnarray.length;
};
this.isEmpty = function () {
returnarray.length === 0;
};
}
Time to put elements in the queue using the following lines of code:
pq.enqueue(["Google", 2]);
pq.enqueue(["Bing", 3]);
pq.enqueue(["Microsoft", 1]);
pq.enqueue(["Apple", 2]);
pq.printCollection();
As you can see, the first priority is the “Microsoft” element with value 1. It must be at the start of the queue even if it was added at 3rd place.
Now, if we call dequeue function and then the print function again the first element should be removed from the list:
pq.printCollection();
There you go, our priority queue is working perfectly.
Conclusion
Queues are data structure concepts that work on the valuation method of first-in and first-out. Similarly, priority queues work on the valuation of first-in and first-out but with an extra value of “priority”, the element with the highest priority will be executed first no matter when they were added to the queue. In this post, we learned how to implement a simple queue in javascript and how to use that data structure to implement the working of a priority queue.
