Implement deque data structure in javascript

Posted on | by Prashant Yadav

Posted in ,

We will see what is deque data structure and why is this data structure needed and then implement an object-based deque in javascript.

What is deque data structure?

Deque or Double-ended queue is a generalized version of queue in which data can be added and removed from both the ends. It performs both the combined operations of stack and queue together and can be used as any of them.

Deque Data Structure

Why is deque data structure needed?

It supports clockwise and anti-clockwise rotations in O(1) time which can be very useful in certain applications and also the problem where elements need to be removed and added from both the ends can be solved easily.

Example

List of operations performed on Deque

  • insertFront(): Inserts an element at the front.
  • insertBack(): Inserts an element at the back.
  • removeFront(): Removes an element from the front.
  • removeBack(): Removes an element from the back.
  • getFront(): Returns the element at the front.
  • getBack(): Returns the element at the back.
  • isEmpty(): Checks if the deque is empty or not.
  • size(): Returns the size of the deque.
  • clear(): Clears the deque.
  • toString(): Returns all the elements concatenated as a string from front to back.

A deque can be implemented either using a doubly-linked list or circular array. In both implementation, we can implement all operations in O(1) time.

Check out how to implement Deque data structure with doubly linked list.

Implementing a deque data structure using array in javascript

Javascript arrays are very flexible and they natively support all the operations of the deque.

Still, we will implement a deque with circular array approach.

We will use two different variables count and lowestCount to keep track of the elements on both the end and items to store the data.

function Deque() {
 //To track the elements from back
  let count = 0; 
  
  //To track the elements from the front
  let lowestCount = 0;
  
  //To store the data
  let items = {};

  //Other methods go here
}

Add an item at the front of the deque

We will check if the deque is empty then add the element from the back of the list as it really does not matter, else if there is one item exist then add on the front of it, else shift the existing items and add the current element on the front.

//Add an item on the front
  this.insertFront = (elm) => {
    
    if(this.isEmpty()){
      //If empty then add on the back
      this.insertBack(elm);
   
    }else if(lowestCount > 0){
      //Else if there is item on the back 
      //then add to its front
      items[--lowestCount] = elm;
      
    }else{
      //Else shift the existing items 
      //and add the new to the front
      for(let i = count; i > 0; i--){
        items[i] = items[i - 1];
      }
      
      count++;
      items[0] = elm;
    }
  }

Add an item at the back of the deque

To add item on the back we will push the new item on the back.

//Add an item on the back of the list
  this.insertBack = (elm) => {
    items[count++] = elm;
  }

Remove an item from the front

To remove the item from the front we just get the item by the lowestCount tracker and increase it.

//Remove the item from the front
  this.removeFront = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }
    
    //Get the first item and return it
    const result = items[lowestCount];
    delete items[lowestCount];
    lowestCount++;
    return result;
  }

Remove an item from the back

To remove the item from the front we just get the item by decrementing the count tracker.

//Remove the item from the back
  this.removeBack = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }
    
    //Get the last item and return it
    count--;
    const result = items[count];
    delete items[count];
    return result;
  }

Get the first element from the front

//Peek the first element
  this.getFront = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }
    
    //Return first element
    return items[lowestCount];
  }

Get the first element from the back

//Peek the last element
  this.getBack = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }
    
    //Return first element
    return items[count - 1];
  }

Check if deque is empty

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

Get the size of the deque

//Get the size
  this.size = () => {
    return count - lowestCount;
  }

Clear the deque

//Clear the deque
  this.clear = () => {
    count = 0;
    lowestCount = 0;
    items = {};
  }

Get the deque as a string

//Convert to the string
  //From front to back
  this.toString = () => {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${items[lowestCount]}`;
    for (let i = lowestCount + 1; i < count; i++) {
      objString = `${objString},${items[i]}`;
    }
    return objString;
  }

Complete code of deque data structure

function Deque() {
  //To track the elements from back
  let count = 0; 
  
  //To track the elements from the front
  let lowestCount = 0;
  
  //To store the data
  let items = {};
  
  //Add an item on the front
  this.insertFront = (elm) => {
    
    if(this.isEmpty()){
      //If empty then add on the back
      this.insertBack(elm);
   
    }else if(lowestCount > 0){
      //Else if there is item on the back 
      //then add to its front
      items[--lowestCount] = elm;
      
    }else{
      //Else shift the existing items 
      //and add the new to the front
      for(let i = count; i > 0; i--){
        items[i] = items[i - 1];
      }
      
      count++;
      items[0] = elm;
    }
  }
  
  //Add an item on the back of the list
  this.insertBack = (elm) => {
    items[count++] = elm;
  }
  
  //Remove the item from the front
  this.removeFront = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }
    
    //Get the first item and return it
    const result = items[lowestCount];
    delete items[lowestCount];
    lowestCount++;
    return result;
  }
  
  //Remove the item from the back
  this.removeBack = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }
    
    //Get the last item and return it
    count--;
    const result = items[count];
    delete items[count];
    return result;
  }
  
  //Peek the first element
  this.getFront = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }
    
    //Return first element
    return items[lowestCount];
  }
  
  //Peek the last element
  this.getBack = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }
    
    //Return first element
    return items[count - 1];
  }
  
  //Check if empty
  this.isEmpty = () => {
    return this.size() === 0;
  }
  
  //Get the size
  this.size = () => {
    return count - lowestCount;
  }
  
  //Clear the deque
  this.clear = () => {
    count = 0;
    lowestCount = 0;
    items = {};
  }
  
  //Convert to the string
  //From front to back
  this.toString = () => {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${items[lowestCount]}`;
    for (let i = lowestCount + 1; i < count; i++) {
      objString = `${objString},${items[i]}`;
    }
    return objString;
  }
}

Input:
let deque = new Deque2();
deque.insertBack(5);
deque.insertBack(10);
console.log(deque.getBack());
deque.removeBack();
console.log(deque.getBack());
deque.insertFront(15);
console.log(deque.getFront());
deque.removeFront(); 
console.log(deque.getFront());

Output:
10
5
15
5

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

let Deque = (function(){
 return function Deque2() {
    //To track the elements from back
    let count = 0; 

    //To track the elements from the front
    let lowestCount = 0;

    //To store the data
    let items = {};

    //Add an item on the front
    this.insertFront = (elm) => {

      if(this.isEmpty()){
        //If empty then add on the back
        this.insertBack(elm);

      }else if(lowestCount > 0){
        //Else if there is item on the back 
        //then add to its front
        items[--lowestCount] = elm;

      }else{
        //Else shift the existing items 
        //and add the new to the front
        for(let i = count; i > 0; i--){
          items[i] = items[i - 1];
        }

        count++;
        items[0] = elm;
      }
    }

    //Add an item on the back of the list
    this.insertBack = (elm) => {
      items[count++] = elm;
    }

    //Remove the item from the front
    this.removeFront = () => {
      //if empty return null
      if(this.isEmpty()){
        return null;
      }

      //Get the first item and return it
      const result = items[lowestCount];
      delete items[lowestCount];
      lowestCount++;
      return result;
    }

    //Remove the item from the back
    this.removeBack = () => {
      //if empty return null
      if(this.isEmpty()){
        return null;
      }

      //Get the last item and return it
      count--;
      const result = items[count];
      delete items[count];
      return result;
    }

    //Peek the first element
    this.getFront = () => {
      //If empty then return null
      if(this.isEmpty()){
        return null;
      }

      //Return first element
      return items[lowestCount];
    }

    //Peek the last element
    this.getBack = () => {
      //If empty then return null
      if(this.isEmpty()){
        return null;
      }

      //Return first element
      return items[count - 1];
    }

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

    //Get the size
    this.size = () => {
      return count - lowestCount;
    }

    //Clear the deque
    this.clear = () => {
      count = 0;
      lowestCount = 0;
      items = {};
    }

    //Convert to the string
    //From front to back
    this.toString = () => {
      if (this.isEmpty()) {
        return '';
      }
      let objString = `${items[lowestCount]}`;
      for (let i = lowestCount + 1; i < count; i++) {
        objString = `${objString},${items[i]}`;
      }
      return objString;
    }
  } 
}());

Input:
let deque = new Deque2();
deque.insertBack(5);
deque.insertBack(10);
console.log(deque.getBack());
deque.removeBack();
console.log(deque.getBack());
deque.insertFront(15);
console.log(deque.getFront());
deque.removeFront(); 
console.log(deque.getFront());

Output:
10
5
15
5

Class based implementation of deque data structure in javascript

class Deque{
  constructor(){
    //To track the elements from back
    this.count = 0;
    
    //To track the elements from front
    this.lowestCount = 0;
    
    //To store the elements
    this.items = {};
  }
  
  //Add an item on the front
  insertFront = (elm) => {
    if(this.isEmpty()){
      //If empty then add on the back
      this.insertBack(elm);
   
    }else if(this.lowestCount > 0){
      //Else if there is item on the back 
      //then add to its front
      this.items[--this.lowestCount] = elm;
      
    }else{
      //Else shift the existing items 
      //and add the new to the front
      for(let i = this.count; i > 0; i--){
        this.items[i] = this.items[i - 1];
      }
      
      this.count++;
      this.items[0] = elm;
    }
  }
  
  //Add an item on the back of the list
  insertBack = (elm) => {
    this.items[this.count++] = elm;
  }

  //Remove the item from the front
  removeFront = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }

    //Get the first item and return it
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  //Remove the item from the back
  removeBack = () => {
    //if empty return null
    if(this.isEmpty()){
      return null;
    }

    //Get the last item and return it
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  //Peek the first element
  getFront = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }

    //Return first element
    return this.items[this.lowestCount];
  }

  //Peek the last element
  getBack = () => {
    //If empty then return null
    if(this.isEmpty()){
      return null;
    }

    //Return first element
    return this.items[this.count - 1];
  }

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

  //Get the size
  size = () => {
    return this.count - this.lowestCount;
  }

  //Clear the deque
  clear = () => {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  //Convert to the string
  //From front to back
  toString = () => {
    if (this.isEmpty()) {
      return '';
    }
    
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
  
}

Input:
let deque = new Deque2();
deque.insertBack(5);
deque.insertBack(10);
console.log(deque.getBack());
deque.removeBack();
console.log(deque.getBack());
deque.insertFront(15);
console.log(deque.getFront());
deque.removeFront(); 
console.log(deque.getFront());

Output:
10
5
15
5

Time Complexity

# Access Search Insert Delete
Average Θ(1) Θ(N) Θ(1) Θ(1)
Worst O(1) O(N) O(1) O(1)

Space Complexity

# space
Worst O(N)

Introducing frontend system design course 🔥 where you will learn to design frontend of 30+ applications.