Queue data structure in javascript

Learn what is queue data structure and how to implement it in javascript.

A queue is an ordered collection of items that follow FIFO (First In First Out) principle also known as ‘First come first served’.

Unlike Stack Items are added at the tail i.e end of the queue and items are removed from the head i.e start of the queue. An item must wait until it is their term to be removed or all items before they are removed.

The most classical example of the queue is people standing in line in banks or ticket counters.

Queue is used widely in computer science for ordering the processes submitted to an operating system or to maintain the order in which document will be printed by a printer. Also, compilers use the queue to order the response after the execution.

List of operation performed by queue

• enqueue(): Adds an item at the tail of the queue.
• dequeue(): Removes an item from the head of the queue.
• front(): Retruns the first item in the queue.
• rear(): Retruns the last item in the queue.
• size(): Returns the size of the queue.
• isEmpty(): Returns true if queue is empty, false otherwise.

Creating a Queue

We will implement the queue in javascript with different approaches.

A classical approach.

function Queue(){
  let items = [];  //Hold items
  let front = 0;   //track front position
  let rear = -1;   //track rear position
  let count = 0;   //track count

  //other methods goes here
}

Adding an item in the queue

//Add a new element in queue
this.enqueue = (elm) => {
  items[++rear] = elm;
  count++;
}

Remove an item from the queue

//Remove element from the queue
this.dequeue = () => {
  let current = front++;
  let temp = items[current]; 
  items[current] = null;
  count--;
  return temp;
}

Return the first element from the queue

//Return the first element from the queue
this.front = () => {
  return items[front];
}

Return the last element from the queue

//Return the last element from the queue
this.rear = () => {
  return items[rear];
}

Check if queue is empty

//Check if queue is empty
this.isEmpty = () => {
  return count === 0;
}

Return the size of the queue

//Return the size of the queue
this.size = () => {
  return count;
}

Print the queue

//Print the queue
this.print = () => {
 let temp = items.filter((e) => e !== null);
 console.log(temp.toString());
};

Complete implementation of the queue data structure in javascript.

function Queue(){
 let items = [];
 let front = 0;
 let rear = -1;
 let count = 0;
  
 //Add a new element in queue
 this.enqueue = (elm) => {
   items[++rear] = elm;
   count++;
 }
  
 //Remove element from the queue
 this.dequeue = () => {
   let current = front++;
   let temp = items[current]; 
   items[current] = null;
   count--;
   return temp;
 }
  
 //Return the first element from the queue
 this.front = () => {
   return items[front];
 }

 //Return the last element from the queue
 this.rear = () => {
   return items[rear];
 }
  
 //Check if queue is empty
 this.isEmpty = () => {
   return count === 0;
 }
  
 //Return the size of the queue
 this.size = () => {
   return count;
 }
  
 //Print the queue
 this.print = () => {
  let temp = items.filter((e) => e !== null);
  console.log(temp.toString());
 };
  
}

Using the queue

Input:
let queue = new Queue();
console.log(queue.isEmpty());
queue.enqueue('pranav');
queue.enqueue('sachin');
queue.enqueue('yogesh');
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();
queue.enqueue('prashant');
queue.enqueue('yadav');
queue.print();
console.log(queue.size());
console.log(queue.front());
console.log(queue.rear());

Output:
true
"pranav,sachin,yogesh"
"yogesh"
"yogesh,prashant,yadav"
3
"yogesh"
"yadav"

This approach works great but as the array size increases with every input we need to keep track of the null values. We can solve this issue, however with javascript array’s inbuilt methods we can implement queue more efficiently.

Queue with javascript array methods

function Queue(){
  let items = [];  //Hold items

  //other methods goes here
}

Adding an item in the queue

//Add a new element in queue
this.enqueue = (elm) => {
  items.push(elm);
}

Remove an item from the queue

//Remove element from the queue
this.dequeue = () => {
  return items.shift();
}

Return the first element from the queue

//Return the first element from the queue
this.front = () => {
  return items[0];
}

Return the last element from the queue

//Return the last element from the queue
this.rear = () => {
  return items[items.length - 1];
}

Check if queue is empty

//Check if queue is empty
this.isEmpty = () => {
  return items.length == 0;
}

Return the size of the queue

//Return the size of the queue
this.size = () => {
  return items.length;
}

Print the queue

//Print the queue
this.print = () => {
  console.log(items.toString());
};

function Queue(){
  let items = [];
  
  //Add a new element in queue
  this.enqueue = (elm) => {
    items.push(elm);
  }
  
  //Remove element from the queue
  this.dequeue = () => {
    return items.shift();
  }
  
  //Return the first element from the queue
  this.front = () => {
    return items[0];
  }
  
  //Return the last element from the queue
  this.rear = () => {
    return items[items.length - 1];
  }
  
  //Check if queue is empty
  this.isEmpty = () => {
    return items.length == 0;
  }
  
  //Return the size of the queue
  this.size = () => {
   return items.length;
  }
  
  //Print the queue
  this.print = () => {
   console.log(items.toString());
  };
  
}

Learn more about the shift() and push() methods.

Here we don’t need to keep track of any ends of the queue also it is quite a memory efficient than the first methods because we are completely removing the items unlike updating them to null.

Making the properties and methods private with closure and IIFE (Immediately Invoked Function Expression).

 let Queue = (function () {
   return function Queue(){
    let items = [];

    //Add a new element in queue
    this.enqueue = (elm) => {
      items.push(elm);
    }

    //Remove element from the queue
    this.dequeue = () => {
      return items.shift();
    }

    //Return the first element from the queue
    this.front = () => {
      return items[0];
    }

    //Return the last element from the queue
    this.rear = () => {
      return items[items.length - 1];
    }

    //Check if queue is empty
    this.isEmpty = () => {
      return items.length == 0;
    }

    //Return the size of the queue
    this.size = () => {
     return items.length;
    }

    //Print the queue
    this.print = () => {
     console.log(items.toString());
    };
  }
})();

Queue data structure using ES6.

 class Queue{
  constructor(){
    this.items = [];
  }
   
  //Add a new element in queue
  enqueue = (elm) => {
    this.items.push(elm);
  }
  
  //Remove element from the queue
  dequeue = () => {
    return this.items.shift();
  }
  
  //Return the first element from the queue
  front = () => {
    return this.items[0];
  }
  
  //Return the last element from the queue
  rear = () => {
    return this.items[this.items.length - 1];
  }
  
  //Check if queue is empty
  isEmpty = () => {
    return this.items.length == 0;
  }
  
  //Return the size of the queue
  size = () => {
   return this.items.length;
  }
  
  //Print the queue
  print = () => {
   console.log(this.items.toString());
  };
  
}

Queue using ES6 and WeakMap.

const items = new WeakMap();
class Queue {
  constructor(){
    items.set(this, []);
  }
   
  //Add a new element in queue
  enqueue = (elm) => {
    let temp = items.get(this);
    temp.push(elm);
  }
  
  //Remove element from the queue
  dequeue = () => {
    let temp = items.get(this);
    return temp.shift();
  }
  
  //Return the first element from the queue
  front = () => {
    let temp = items.get(this);
    return temp[0];
  }
  
  //Return the last element from the queue
  rear = () => {
    let temp = items.get(this);
    return temp[temp.length - 1];
  }
  
  //Check if queue is empty
  isEmpty = () => {
    let temp = items.get(this);
    return temp.length == 0;
  }
  
  //Return the size of the queue
  size = () => {
    let temp = items.get(this);
    return temp.length;
  }
  
  //Print the queue
  print = () => {
   let temp = items.get(this);
   console.log(temp.toString());
  };
  
}

Making properties and methods private using closure and IIFE (Immediately Invoked Function Expression) of Queue using ES6 and WeakMap.

let Queue = (() => {
  const items = new WeakMap();
  return class Queue {
    constructor(){
      items.set(this, []);
    }

    //Add a new element in queue
    enqueue = (elm) => {
      let temp = items.get(this);
      temp.push(elm);
    }

    //Remove element from the queue
    dequeue = () => {
      let temp = items.get(this);
      return temp.shift();
    }

    //Return the first element from the queue
    front = () => {
      let temp = items.get(this);
      return temp[0];
    }

    //Return the last element from the queue
    rear = () => {
      let temp = items.get(this);
      return temp[temp.length - 1];
    }

    //Check if queue is empty
    isEmpty = () => {
      let temp = items.get(this);
      return temp.length == 0;
    }

    //Return the size of the queue
    size = () => {
      let temp = items.get(this);
      return temp.length;
    }

    //Print the queue
    print = () => {
     let temp = items.get(this);
     console.log(temp.toString());
    };

  }  
})();

Time Complexity

Space Complexity