An Introduction to Queue Data Structure in Javascript

Everything about Queue Data Structure in Javascript

Before Semicolon
Apr 21 · 8 min read

Javascript uses a queue to track the code to execute. Your printer also follows a queue to track which document to print next. Hospitals use a system based on a priority queue to decide which patient to go in first. Point is, Queues are everywhere. From your favorite Coffee shop to computer CPU and your server or network, the queue is an important data structure to learn about.

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.

Watch Videos

What is a Queue?

It is a linear data structure and also an abstract data type. That means that the elements are placed linearly one after another and that it is defined by its behavior rather than being a mathematical model.

The queue is a list and what makes it a queue is how it works and the principle it implements and not how a list is or what it contains.

When to use a Queue?

Processors and languages like Javascript use it for that reason, to keep an order of things to execute. For example, the Javascript event loop keeps an internal callback queue to execute. The system that keeps track of organ donation recipients is likely a priority queue that analysis various details to determine each person's priority in the queue. Another example would a printer.

Pretty much, whenever you have a list of anything that you want to address in a very specific order, either the order or insertion or priority, it calls for a queue data structure.

Queue Implementation with Array

For the below Queue, we are tracking the “head”(item at the front) and the “tail”(item at the end). These 2 trackers are very important and they both start at zero. Another option we have is the ability to specify a “capacity”, a max size the Queue should grow to and it is optional. No capacity means you have a dynamic Queue.

class Queue {
#list = [];
#capacity = null;

#tail = 0;
#head = 0;
constructor(capacity) {
this.#capacity = Math.max(Number(capacity), 0) || null;

if(this.#capacity) {
this.#list = Array.from({length: this.#capacity});
}
}
}

If a “capacity” is specified we first make sure is greater than zero and use it to create a list array of that size. This detail is very important in understanding the nature of the Queue.

To learn more about Array data structure, refer to the Array data structure article.

We can use these properties to define a few getters for the queue. The size is defined by the difference between the tail and the head. You will understand why we define the “enqueue” and “dequeue” methods.

get size() {
return this.#tail - this.#head;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity && this.#tail === this.#capacity;
}

The queue is empty if the size is zero and if the queue is dynamic(has no capacity defined), it is consequently never full. So a queue is considered to be full if there is a defined capacity AND the tail matches the capacity.

The “enqueue” method is very minimal and it must return the size of the list.

enqueue(item) {
if(!this.isFull) {
this.#list[this.#tail] = item;
this.#tail += 1;

}
return this.size;
}

As long as the queue is not full, we will use the “tail” value to insert an item at that index of the array then increment so the next value will be inserted at the next index. Once the tail matches the capacity, the queue is considered to be full and no new item can be inserted.

The “dequeue” method is somehow simple too and it returns the item removed.

dequeue() {
let item = null;
if(!this.isEmpty) {
item = this.#list[this.#head];
delete this.#list[this.#head];
this.#head += 1; if(this.isEmpty) {
this.#head = 0;
this.#tail = 0;

}
}
return item;
}

As long as the queue is not empty we will grab the item at the head to return it then we “delete” the item at the head. Deleting an item at an array index does not change the array size, it simply removes the value at that index. That array index location is considered “empty” and empty is different than “undefined”.

Then, we proceed by incrementing the head so it points to the next item in the array. If the dequeue action causes the queue to become empty — head matches tail — we reset them to their initial value so a new item can be inserted.

Note: Trying to enqueue a new item into a full queue (overflow the queue) will not change anything. A full queue must be cleared before a new item can be inserted. Dequeuing an item leaves empty slots that cannot be filled while the queue is full and because of this the Circular Queue was introduced to improve on this issue.

To peek at the top(front) item we simply return the item at the head index as long as the queue is not empty.

peek() {
if(this.isEmpty) {
return null;
}
return this.#list[this.#head];
}

As you can see, it is a very simple concept to implement and you may be asking why bother with creating a class wrapper if you can just use the array directly as a queue since it has methods like “push” and “unshift”? You may also find this implementation “extra” and it in Javascript, it can be.

class Queue {
#list = [];

enqueue(item) {
return this.#list.push(item)
}

dequeue() {
return this.#list.unshift()
}

peek() {
return this.#list[0]
}
}

The above is also a valid dynamic Queue and maybe all you need. The previous complex implementation can be more efficient since you are not actually changing the array on every “enqueue” and “dequeue” operations, you are changing the values which are quicker. You can check the Linked List article where I dive deeper into this.

For the most part, the simpler implementation is what you need, especially if you don’t care about the slight speed difference and optimizations but it is important to understand this Data Structure as it is and learn the algorithm behind its implementation.

Source Code: Check this full code on Github

Array vs Queue

They both serve a different purpose and just because you can use an array to implement a Queue does not make them closely related. The array grows dynamically and the push and pop methods alone do not know to handle capacity or overflow logic on their own.

It is those restrictions and characteristics in a list that makes a Queue a totally different list and one that solves a very specific problem that the Array does not have the constraints for.

Queue Implementation with Linked List

For the linked list version there is no list. Instead, we have first and last item pointers to track the first and the last items which are the most important items for a Queue. These are commonly referred to as head and tail in some implementations. Another difference is the “size” private property to track the size of the list as we “queue” and “dequeue” items.

class Queue {
#firstItem = null;
#lastItem = null;

#size = 0;
#capacity = null;

constructor(capacity = null) {
this.#capacity = Math.max(Number(capacity), 0) || null;
}
get size() {
return this.#size;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity ? this.size === this.#capacity : false;
}
...

In a linked list, the elements have pointers for previous and next elements but for this, we only need the “next” pointer. It is known as a single-linked list. These pointers are what connect the elements together. To create the element of the list we have the “createItem” method that returns the value and the pointer.

#createItem(value) {
return {
next: null,
value
}
}

For the enqueue method we need to do some changes. We still need to make sure the queue is not full before we add a new item but we need to create the element using the provided item and then perform two checks.

enqueue(item) {
if(!this.isFull) {
const newItem = this.#createItem(item);
if(this.isEmpty) {
this.#firstItem = newItem;
this.#lastItem = newItem;

} else {
this.#lastItem.next = newItem;
this.#lastItem = newItem;

}
this.#size += 1;
}
return this.size;
}

If the queue is empty, the first and last items are the same, the new item. If the list already has items we need to point the current last item to the new item and then set the new item as the last item. After, we increment size and return it at the end.

The dequeue is much simpler. We first need a variable to hold the item we are removing and if the queue is not empty we use the first item value to assign to the removed item variable and make the next item in the list the first item.

dequeue() {
let removedItem = null;
if(!this.isEmpty) {
removedItem = this.#firstItem.value;
this.#firstItem = this.#firstItem.next;
this.#size -= 1;
}
return removedItem;
}

The next item can be null if the queue only has 1 element. Then we decrement the size and return the removed item.

The peek is also simple. All it does is return the first item value.

peek() {
return this.#firstItem.value;
}

A linked list is really powerful because it connects data that can be anywhere in memory with pointer references. It also provides super-fast insertion and removal operations which leave no wasted space in memory. It is my opinion that a Queue is better when implemented with a linked list since it already inherits all the great things about linked lists.

Source Code: Check this full code on Github

Next

Youtube Channel: Before Semicolon
Website: beforesemicolon.com

CodeX

Everything connected with Tech & Code

Before Semicolon

Written by

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.com — youtube.com/c/BeforeSemicolon — Writer: Elson Correia

CodeX

CodeX

Everything connected with Tech & Code

Before Semicolon

Written by

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.com — youtube.com/c/BeforeSemicolon — Writer: Elson Correia

CodeX

CodeX

Everything connected with Tech & Code

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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