Queue in Javascript: How to create Priority, and Circular Queue

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.

image by dailycodebuffer post
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;
}
}
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;
}
dequeue() {
return this.isEmpty ? null : this.#list.shift().item;
}
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;
}
}
#createItem(value, priority) {
return {
next: null,
value,
priority
}
}
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;
}
  • (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.
dequeue() {
let removedItem = null;
if(!this.isEmpty) {
removedItem = this.#firstItem.value;
this.#firstItem = this.#firstItem.next;
this.#size -= 1;
}
return removedItem;
}

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.

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
image by geeksforgeeks
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;
}
}
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;
}
// 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
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;
}

Conclusion

As you could see Priority and Circular queue 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 proved and tested ideas to accomplish what we need.

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.comyoutube.com/c/BeforeSemicolon

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store