Part 2— Queue Data Structure in js

Introduction

A queue is a linear data structure that stores data in FIFO(First In First Out) order i.e. whatever goes in first comes out first. Earlier we have seen stack ds which supports LIFO(Last in first out) order i.e. insertion and deletion will both happen from one end. However, in the case of the queue, the insertion will happen from one end(rear) and removal will happen from another end(front). Queue means exactly the same as it means in the real world.

Operations

There are 2 primary operations in a Stack. Enqueue operation and dequeue operation. Enqueue operation is to add data to the rear end of the queue. Dequeue is to remove data from the front of the queue. Some additional operations are front (or peek) to check the first element of the queue, isEmpty to check whether queue is empty, etc.

Implementation

We can simply create a queue with the Array Data structure. The array support push method by default. In order to support additional methods, we will create a Queue Object with the methods we need. Our queue API will have the following methods:

enqueue
dequeue
front
isEmpty
search

Implementation goes as below:

function Queue(){
   this.items = [];
}
Queue.prototype.enqueue = function(ele){
 this.items.push(ele);
}
Queue.prototype.isEmpty = function(){
 return this.items.length === 0;
}
Queue.prototype.dequeue = function(){
 if(this.isEmpty()){
  return "Empty Queue";
 }
 this.items.splice(0,1);
}
Queue.prototype.front = function(){
   if(this.isEmpty){
      return "Empty Stack";
   }
   return this.items[0];
}
Queue.prototype.search = function(item){
   if(this.isEmpty){
      return "Empty Queue";
   }
   for(let i = 0; i < this.items.length; i++){
      if(this.items[i] === item){
      return `item ${item} found at index ${i}`;
   }
   return "item ${item} not found in the queue"
}

Time Complexity

Access and Search Operation

In order to access an element in the queue, we have to keep shifting elements until we find the one we are looking for. The worst-case is element is present at the rear end of the queue.N movements are required. The best case is element is present at the front of the queue hence 1 movement is required. The average case is n/2 which can be represented asymptotically as O(n);

Insert, delete and front Operation

Insertion can be done only at the rear end hence complexity is O(1),

Similar to insertion, front and deletion are possible from the front of the queue hence time complexity will be O(1).

For accessing an element, we have to keep moving elements until we fin=d the match. The worst-case will be O(n), best case will be O(1). The average case will be O(n/2) which can be asymptotically represented as O(n).

Applications

Queues are commonly used where things don't need to be processed immediately but in First in, First out order. Below is a list of some applications of a queue.

1. CPU resource sharing- When multiple processes are sharing common CPU resources, queue data structures are used to enqueue process until the resource is busy.
2. Asynchronous Data transfer- When data is transferred asynchronously between two processes, generally queues are used to keep a track of the process.

Conclusion

In this section, we learned about the queue as an abstract data type, its implementation, and common applications. As usual, I would recommend you to practice its implementation and related problems to get a good hold of it. In the next section, we will learn about the linked list and its implementation. Stay tuned!