Deque (Double Ended Queue) in JavaScript

1 What is a Deque?

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.

Operations on Deque:

Mainly the following basic operations are performed on queue:

insertFront(): Adds an item at the front of Deque.
insertLast(): Adds an item at the rear of Deque.
deleteFront(): Deletes an item from the front of Deque.
deleteLast(): Deletes an item from the rear of Deque.

In addition to the above operations, the following operations are also supported:

getFront(): Gets the front item from the queue.
getRear(): Gets the last item from queue.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Applications of Deque:

Since Deque supports both stack and queue operations, it can be used as both. The Deque data structure supports clockwise and anticlockwise rotations in O(1) time which can be useful in certain applications. Also, the problems where elements need to be removed and or added to both ends can be efficiently solved using Deque.

Some Practical Applications of Deque:

Applied as both stack and queue, as it supports both operations.
Storing a web browser's history.
Storing a software application's list of undo operations.
Job scheduling algorithm.

2 Circular Implementation of Deque

A Deque can be implemented either using a doubly-linked list or a circular array. In both implementations, we can implement all operations in O(1) time. We couldn't implement Deque using a singly linked list because the delete rear operation can't be implemented in O(1) time.

Circular array Implementation of Deque:

For implementing the deque, we need to keep track of two indices, front and rear. We enqueue an item at the rear or the front and dequeue an item from both ends.

Insert Elements at the Rear end of Deque:

1. Check if deque is full
2. IF full, print "Overflow"
3. IF rear == capacity - 1
      rear = 0
4. ELSE
      rear = rear + 1

Insert Elements at the Front end of Deque:

1. Check if deque is full
2. IF full, print "Overflow"
3. IF front == 0
      front = capacity - 1
4. ELSE
      front = front - 1

Delete Element From Rear end of Deque:

1. Check if deque is empty
2. IF empty, print "Underflow"
3. IF front == rear (only 1 element)
      front = -1, rear = -1
4. ELSE IF rear == 0
      rear = capacity - 1
5. ELSE
      rear = rear - 1

Delete Element From the Front end of Deque:

1. Check if deque is empty
2. IF empty, print "Underflow"
3. IF front == rear (only 1 element)
      front = -1, rear = -1
4. ELSE IF front == capacity - 1
      front = 0
5. ELSE
      front = front + 1

3 Advanced Interview Problems using Deque

Problem 1: Design a Data Structure with Min and Max operations

Problem: Design a Data Structure SpecialQueue which supports following operations enqueue(), dequeue(), getMin() or getMax() where getMin() operation takes O(1) time.

Approach: The idea is to use a Doubly Ended Queue to store in increasing order if the structure is to return the minimum element, and store in decreasing order if the structure is to return the maximum element.

Enqueue:
- Insert the element into the queue structure.
- If the size of the Deque structure is empty (size is 0), then insert the element from the back.
- Otherwise, if there are some elements in the Deque structure then pop the elements out from the Deque until the back of the Deque is greater than the current element and then finally insert the element from back.
Dequeue:
- If the first element of the Deque is equal to the front element of the queue then pop the elements out from the Queue and the Deque at the same time.
- Otherwise, pop the element from the front of the queue to maintain the order of the elements.
Get Minimum:
- Return the front element of the Deque to get the minimum element of the current element of the queue.

class MinMaxQueue {
  constructor() {
    this.Q = []; // Main queue
    this.D = []; // Deque for minimums
  }
  
  enqueue_element(element) {
    if (this.Q.length === 0) {
      this.Q.push(element);
      this.D.push(element);
    } else {
      this.Q.push(element);
      while (this.D.length > 0 && this.D[this.D.length - 1] > element) {
        this.D.pop();
      }
      this.D.push(element);
    }
  }
  
  dequeue_element() {
    if (this.Q.length > 0) {
      let val = this.Q.shift();
      if (val === this.D[0]) {
        this.D.shift();
      }
    }
  }
  
  getMin() {
    return this.D[0];
  }
}

Time Complexity: O(N) (Amortized O(1) per operation)
Auxiliary Space: O(N)

Problem 2: Maximum of all subarrays of size k

Problem: Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Approach: Use a doubly ended queue (Deque). The Deque will store indices of useful elements in the current window of size k. An element is useful if it is in the current window and is greater than all other elements on its right side in the current window.

function printMax(arr, n, k) {
  let Qi = []; // Create a Double Ended Queue
  
  // Process first k (or first window) elements of array
  let i;
  for (i = 0; i < k; ++i) {
    // For every element, the previous smaller elements are useless so remove them from Qi
    while (Qi.length > 0 && arr[i] >= arr[Qi[Qi.length - 1]]) {
      Qi.pop(); 
    }
    // Add new element at rear of queue
    Qi.push(i);
  }
  
  let result = [];
  // Process rest of the elements, i.e., from arr[k] to arr[n-1]
  for (; i < n; ++i) {
    // The element at the front of the queue is the largest element of previous window
    result.push(arr[Qi[0]]);
    
    // Remove the elements which are out of this window
    while (Qi.length > 0 && Qi[0] <= i - k) {
      Qi.shift();
    }
    
    // Remove all elements smaller than the currently being added element
    while (Qi.length > 0 && arr[i] >= arr[Qi[Qi.length - 1]]) {
      Qi.pop();
    }
    
    // Add current element at the rear of Qi
    Qi.push(i);
  }
  
  // Print the maximum element of last window
  result.push(arr[Qi[0]]);
  console.log(result.join(" "));
}

Time Complexity: O(N). Every element of array is added and removed at most once. So there are total 2N operations.
Auxiliary Space: O(k) for elements stored in Qi.

Problem 3: First Circular Tour

Problem: Given information about N petrol pumps (amount of petrol and distance to next petrol pump). The truck has infinite capacity and consumes 1 unit of petrol to travel 1 unit distance. Find the index of the first starting point such that the truck can visit all the petrol pumps and come back to that starting point.

First Circular Tour Using Queue: Instead of checking the whole array for each starting point, we can store the current tour inside a queue. At the moment, the current amount of petrol becomes inefficient (i.e., negative) to reach the next petrol pump, remove the current starting point from the queue and consider the next point as the new starting point.

Instead of building a separate queue, we can use the array itself as a queue with the help of start and end pointers.

class petrolPump {
  constructor(petrol, distance) {
    this.petrol = petrol;
    this.distance = distance;
  }
}
 
function printTour(arr, n) {
  let start = 0;
  let end = 1;
  let curr_petrol = arr[start].petrol - arr[start].distance;
  
  // Run a loop while all petrol pumps are not visited
  // And we have reached first petrol pump again with 0 or more petrol
  while (end !== start || curr_petrol < 0) {
    // If current amount of petrol in truck becomes less than 0, then remove the starting petrol pump from tour
    while (curr_petrol < 0 && start !== end) {
      curr_petrol -= arr[start].petrol - arr[start].distance;
      start = (start + 1) % n;
      
      // If 0 is being considered as start again, then there is no possible solution
      if (start === 0) return -1;
    }
    // Add a petrol pump to current tour
    curr_petrol += arr[end].petrol - arr[end].distance;
    end = (end + 1) % n;
  }
  
  // Return starting point
  return start;
}

Time Complexity: O(N)
Auxiliary Space: O(1)

Queue Tree