Queue is one of the most common data structures. It is a FIFO or First In First Out data structure. In this post, we will look at Queue implementation in Javascript.
Just like Stack, Queue also has several practical uses in real-life as well as computer science. In real-life, you will find queues everywhere. In shopping malls you have queues at the payment counter. Also, in hospitals, you have queues. While trying to catch a bus or an airplane, you have to usually walk in a queue.
Even in computer science, you have a Queue. For examples, processes in an operating system rely on some sort of Queue implementation. Also, things such as a printer executing print job internally uses a Queue.
1 – Important Queue Methods
Typically, a Queue data structure should have the below two methods:
- Enqueue – This method inserts an item to a queue. If a queue is empty, this item will be the first item in the queue and also the first that should be removed.
- Dequeue – As the name suggests, this method removes an item from the queue. Being a FIFO data structure, this method should always remove the first item that was inserted in the queue.
Many programming languages (such as Java or C#) provide native implementations of a Queue data structure. However, in Javascript there is no such separate implementation.
Basically, in Javascript, we can replicate the Queue data-structure using Arrays.
2 – Queue using Array in Javascript
A simple way to replicate a Queue in Javascript is by using an Array. We can simply define a new Queue as below.
let Queue = []
Once we declare an array, we have two approaches to use the same as Queue.
2.1 – Using Unshift and Pop
Javascript arrays have in-build methods such as Unshift and Pop that can allow us to simulate the behavior of the Queue.
For example, we can use unshift() function to push elements into the array.
Queue.unshift(3) Queue.unshift(4) Queue.unshift(5)
After the above three statement, below is the how the array appears
[5, 4, 3]Basically, unshift() function inserts into the beginning of the array.
Now, we can use the pop() function to remove the element from the end of the array.
Queue.pop()
In the above example array, the order of elements popping would be 5, 4 & 3. Basically, this replicates the behavior of a Queue data structure.
2.2 – Using Push and Shift
The second approach to replicate Queue data structure using Arrays is to use the in-built functions Push and Shift.
For example, we can use push() function to push elements into the array.
Queue.push(3) Queue.push(4) Queue.push(5)
The above statements will push elements 3, 4 & 5 into the array. Basically, the array will look like below:
[3, 4, 5]Now, we can use the shift() function to remove the elements from the array. For example, the first execution of the below statement will remove the element 3 from the array.
Queue.shift()
In other words, the first element that was inserted.
2.3 – Comparing Unshift/Pop with Push/Shift
While perfectly workable, both the approaches have one similar problem.
In the unshift/pop approach, the pop() function has time complexity of O(1) since we always pop from the end. However, unshift() inserts a new element in the beginning of the array. This leads to re-indexing of every element in the array. This leads to an overall time complexity of O(n).
Similarly, in the push/shift approach, the push() function has time complexity of O(1) since we always push to the end of the array. However, shift() removes the element from the beginning of the array. This leads to re-indexing of every element in the array. This leads to an overall time complexity of O(n).
Therefore, if you want to use one of the above approaches, it is beneficial to look at the primary requirement.
If the main requirement is to push elements to the queue, the push/shift approach is better. However, if removing elements from the queue is more important, then the unshift/pop approach is better.
3 – Queue Implementation from scratch in Javascript
In case you need a solution that works better for adding as well as removing elements from the Queue, we can have our Queue Implementation in Javascript.
We use Linked List for such an implementation. You can read more about Linked List in Javascript in case you want more details about what a Linked List is.
We will use a Singly-Linked List for our implementation. Below are the details:
3.1 – The Node class
The Node class basically defines a single element in the Queue.
class Node { constructor(val){ this.val = val; this.next = null; } }
Basically, we need only two attributes. The val attribute stores the value of the element. The next attribute points to the next element in the Queue or Linked List.
3.2 – The Queue class
The queue class is the main class for our implementation.
class Queue { constructor(){ this.first = null; this.last = null; this.length = 0; } }
Basically, here we have properties such as first, last and the length. When the Queue is initialized, we set the first and the last nodes to null and the length to 0. In other words, it is an empty queue.
3.3 – Enqueue Function
As seen earlier, the enqueue function adds an element to the queue.
Below is how we implement the same:
enqueue(val){
let newNode = new Node(val);
if (this.size === 0){
this.first = newNode;
this.last = newNode;
}else{
this.last.next = newNode;
this.last = newNode;
}
this.size++;
}
As can be seen in the above snippet, we always insert a new element at the end of the list. In case it is the first element, we set both the first and the last element to the first element.
By following this approach, the first element to come into our list will always be found at the beginning.
3.4 – Dequeue Function
The Dequeue function removes the first element from the list.
Below is the implementation:
dequeue(){
if (this.size === 0) return null;
let node = this.first;
if (this.size === 1){
this.first = null;
this.last = null
}else{
this.first = this.first.next;
}
this.size--
return node;
}
Basically, we just return the first element from the list and set the first element’s next element as the new first element.
Due to this approach, both the enqueue() and dequeue() functions have a time complexity of O(1).
Conclusion
With this, we have finished our Queue Implementation in Javascript. We also looked at how you can use Javascript arrays to work as Queues. However, our own implementation has a better time complexity.
The code for the same is available on this Gist.
0 Comments