By Elson Correia
As you may have seen in the previous article, there are some limitations and things that can be improved about Queue. Sometimes you also need different constraints or rules around “enqueuing” and “dequeuing”. For those reasons, the Priority and Circular version of the Queue is available to address very specific situations.
Video Version of This Article
This post is an improved and more detailed article version of the Queue Data Structure Series on Youtube that you can check if you prefer videos.
Priority Queue
A priority queue is simply a queue that cares about the priority level of the items. It is perfect when all you always want to address the most important items first. Whether you are creating a waiting list app for a hospital emergency room or a load balancer on your server or some sort of scheduler, this queue is perfect for you.
Note: Priority queue does not act on the FIFO principle enterily like you learned on the previous article. It acts on priority or level of importance of its items. If all items have the same priority, than it is First In First Out.
Higher priority means an item gets out of the queue first. Among the items of the same priority, the order of insertion decides their order.
image by dailycodebuffer post
We can start by defining our class which will feel very similar to our previous article queue implementation using an array. The difference here is we are not using the “tail” and “head” trackers so we can focus on the prioritization of the queue.
class PriorityQueue {
#list = [];
#capacity;
constructor(capacity) {
this.#capacity = Math.max(Number(capacity), 0) || null;
}
get size() {
return this.#list.length;
}
get isFull() {
return this.#capacity !== null && this.size === this.#capacity;
}
get isEmpty() {
return this.size === 0;
}
}
For the “enqueue” method the first change is that now you can specify the priority of the item which we make sure is a number greater or equal to zero.
enqueue(item, priority = 0) {
priority = Math.max(Number(priority), 0);
const element = { item, priority };
if (
this.isEmpty ||
element.priority <= this.#list[this.size - 1].priority
) {
this.#list.push(element);
} else {
for (let index in this.#list) {
if (element.priority > this.#list[index].priority) {
this.#list.splice(index, 0, element);
break;
}
}
}
return this.size;
}
What we add to the array is an object containing our item and its priority. If the queue is empty or this new item priority is less or equal to the last item priority we just push it to the list, otherwise, we need to iterate the list to find a spot to add it.
The loop will go from the first item to the last comparing priority and as soon as it finds an item with less priority value it'll stop and insert the element and that index then quit the loop. This logic will allow for when the priority is the same, it will continue so it will go to the end of the section with the same priority.
For the dequeue method, we just need to make sure that if the queue is not empty we return the item and not the element containing the priority information. The priority detail is for internal tracking.
dequeue() {
return this.isEmpty ? null : this.#list.shift().item;
}
Source Code: Check this full code on Github
If you use a linked list to implement the Priority Queue, almost the same changes need to be addressed. Compared to the above array version, the difference here is that there is no “list” array and we have trackers for the first and last item and for size as well.
class PriorityQueue {
#firstItem = null;
#lastItem = null;
#size = 0;
#capacity = null;
constructor(capacity = null) {
this.#capacity = capacity;
}
get size() {
return this.#size;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity ? this.size === this.#capacity : false;
}
}
Before we implement the “enqueue” method, we need a method that will create our list item. It contains the “value”(the item you inserted), the next pointer, and the priority information.
#createItem(value, priority) {
return {
next: null,
value,
priority
}
}
The queue version for this is quite extensive so let's break it down. It takes your item and priority which defaults to zero. Then it makes sure the priority is never less than zero and we only enqueue if the list is not full.
enqueue(item, priority = 0) {
priority = Math.max(Number(priority), 0);
if(!this.isFull) {
const newItem = this.#createItem(item, priority);
(1) if(this.isEmpty) {
this.#firstItem = newItem;
this.#lastItem = newItem;
(2) } else if(newItem.priority <= this.#lastItem.priority) {
this.#lastItem.next = newItem;
this.#lastItem = newItem;
(3) } else if(newItem.priority > this.#firstItem.priority) {
newItem.next = this.#firstItem;
this.#firstItem = newItem;
(4) } else {
let current = this.#firstItem;
while(current) {
if(newItem.priority > current.next.priority) {
newItem.next = current.next;
current.next = newItem;
break;
}
current = current.next;
}
}
this.#size += 1;
}
return this.size;
}
- (1) — if the queue is empty the new item is both, the first and the last item.
- (2) — We take a shortcut to check if the item has the least priority — less than the last item priority — we simply add it to the end by making the current last item point to it and make it the last item.
- (3) — Similarly, another shortcut for if the new item has the highest priority — greater than the first item in the list — we add it to the front but making it point to the current first item and make it the first item.
- (4) — If it does not go at the end or at the front it must go in the middle and we need to find out where. We start from the first item as current and as long as there is a current we try to find the first item from which this new item has higher priority. When we find it, we insert it right after the current item we are iterating by making the current item point to the new item and the new item point to the item the current item was pointing to.
Note: this logic skips the first and the last item by comparing new item to the item after the current item. We don’t have to worry if the “next” will be null because at this point we know the new item does not go till the end.
For the “dequeue” method we will be removing the item at the front so all we do is grab the first item and make the item that comes next to the first item, decrement the size and return the removed item.
dequeue() {
let removedItem = null;
if(!this.isEmpty) {
removedItem = this.#firstItem.value;
this.#firstItem = this.#firstItem.next;
this.#size -= 1;
}
return removedItem;
}
Source Code: Check this full code on Github
It is also common to find priority queues implemented using a tree data structure which is a non-linear data structure and can be very efficient. Check the page for the article on the tree data structure.
Circular Queue
A circular queue, also known as the ring buffer, is an improvement over the linear queue in the way that in a linear queue if the queue is full but there is space in front you cannot enqueue new items, you must empty the queue first. This is further explained in the first article.
This queue is not only an improvement over the normal queue but it has some great real-world applications as well. The traffic light uses it to show the repeated lights. Your clock, a calendar, schedulers and memory management systems, etc. Whenever you have a fixed size of things you need to manage over and over this queue is for it.
Ring Buffer — A 24-byte keyboard circular buffer. When the write pointer is about to reach the read pointer — because the microprocessor is not responding — the buffer stops recording keystrokes. On some computers, a beep would be played
A circular queue keeps track of the front and rear pointers which are connected and if you remove items in front and “enqueue” new items, the queue goes around and adds new items to the newly empty space.
image by geeksforgeeks
Notice that for this queue even though we are using an array, we still tracking the size and have additional 2 pointers to track the head and the tail of the queue. No other queue screams “implement me with linked list” more than this but ill show you that version next.
class CircularQueue {
#list = [];
#capacity;
#tail = -1;
#head = -1;
#size = 0;
constructor(capacity = 10) {
this.#capacity = Math.max(Number(capacity), 0) || 10;
}
get size() {
return this.#size;
}
get isFull() {
return this.#size === this.#capacity;
}
get isEmpty() {
return this.size === 0;
}
}
For the enqueue method there are a few interesting things happening. The obvious thing is that we use the tail as the index to insert the new item and increment the size.
enqueue(item) {
if (!this.isFull) {
this.#tail = (this.#tail + 1) % this.#capacity;
this.#list[this.#tail] = item;
this.#size += 1;
// queue was empty before this insertion
if (this.#head === -1) {
this.#head = this.#tail;
}
}
return this.size;
}
We also only “enqueue” new items if the queue is not full. We also check if the head is -1 (this happens when the queue is empty which you will understand when it happens later in the dequeue method) and set it to the tail which will be 0 after the first insertion.
Every time we try to “enqueue” we increment the tail and mod it by the capacity to find the next index to insert a new item. What this does is make the index reset to 0 when it reaches the last index.
// tails starts at -1
// than after the first increment
// becomes 0 so if capacity is 3
0 % 3 // 0
1 % 3 // 1
2 % 3 // 2
3 % 3 // 0
For the dequeue method, we set the local variable to contain the item to be removed and if the queue is not empty we use the head to grab the item at the front and then delete the item at that index.
dequeue() {
let item = null;
if (!this.isEmpty) {
item = this.#list[this.#head];
delete this.#list[this.#head];
this.#head = (this.#head + 1) % this.#capacity;
this.#size -= 1;
// reset tail and head if empty
if (!this.size) {
this.#head = -1;
this.#tail = -1;
}
}
return item;
}
After, we need to increment the head to make it point to the next item and decrement size. In case the queue becomes empty, we reset “head” and “tail” back to -1 so on the next insertion the incrementation puts them at 0 indexes which will happen with the first item insertion. This is why we check if the head is -1 inside the “enqueue” method.
Source Code: Check this full code on Github
Conclusion
As you could see Priority and Circular queues are simply awesome to learn about. Sometimes, complex things we find out there are based on simple data structures like these and as developers, recognizing patterns helps us avoid reinventing the wheel and base on proven and tested ideas to accomplish what we need.
This article is part of a Data Structure series so check the page for more Data Structure posts and follow for any future ones. Thank you.
YouTube Channel: Before Semicolon Website: beforesemicolon.com