DEV Community

Cover image for Deque
Nitin Soni
Nitin Soni

Posted on

2

Deque

A Deque (Double-Ended Queue) is a type of linear data structure that allows insertion and deletion of elements from both the front and the rear ends. Unlike a standard queue, it does not strictly follow the FIFO (First In, First Out) principle.

deque visual

Types of Deque

  • Input Restricted Deque
    In this deque, input is restricted at a single end but allows deletion at both the ends.

  • Output Restricted Deque
    In this deque, output is restricted at a single end but allows insertion at both the ends.

Operations on a Deque

Below is the circular array implementation of deque. In a circular array, if the array is full, we start from the beginning.

But in a linear array implementation, if the array is full, no more elements can be inserted. In each of the operations below, if the array is full, "overflow message" is thrown.

Before performing the following operations, these steps are followed.

  1. Take an array (deque) of size n. Set two pointers front = -1 and rear = 0.

deque visual

1. Insert at the Front

This operation adds an element at the front.

  1. Check if the deque is full.

deque visual

  1. If the deque is full (i.e. (front == 0 && rear == n - 1) || (front == rear + 1)), insertion operation cannot be performed (overflow condition).
  2. If the deque is empty, reinitialize front = 0. And, add the new key into array[front].
  3. If front = 0, reinitialize front = n-1 (last index).

deque visual

  1. Else, decrease front by 1.
  2. Add the new key 5 into array[front].

deque visual

2. Insert at the Rear

This operation adds an element to the rear.

  1. Check if the deque is full.
    deque visual

  2. If the deque is full, insertion operation cannot be performed (overflow condition).

  3. If the deque is empty, reinitialize rear = 0. And, add the new key into array[rear].

  4. If rear = n - 1, reinitialize real = 0 (first index).

  5. Else, increase rear by 1.

deque visual

  1. Add the new key 5 into array[rear].

deque visual

3. Delete from the Front

The operation deletes an element from the front.

  1. Check if the deque is empty.

deque visual

  1. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
  2. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1.
  3. Else if front is at the last index (i.e. front = n - 1), set front = 0.
  4. Else, front = front + 1.

deque visual

4. Delete from the Rear

This operation deletes an element from the rear.

  1. Check if the deque is empty.

deque visual

  1. If the deque is empty (i.e. front = -1), deletion cannot be performed (underflow condition).
  2. If the deque has only one element (i.e. front = rear), set front = -1 and rear = -1, else follow the steps below.
  3. If rear is at the first index (i.e. rear = 0), reinitialize rear = n - 1.
  4. Else, rear = rear - 1

deque visual

5. Check Empty

This operation checks if the deque is empty. If front = -1, the deque is empty.

6. Check Full

This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front = rear + 1, the deque is full.

Deque Code:

class Deque {
  constructor(size) {
    this.size = size;
    this.arr = new Array(size);
    this.front = -1;
    this.rear = 0;
  }

  isFull() {
    return (
      (this.front === 0 && this.rear === this.size - 1) ||
      this.front === this.rear + 1
    );
  }

  isEmpty() {
    return this.front === -1;
  }

  insertFront(key) {
    if (this.isFull()) {
      console.log('Overflow! Cannot insert at front');
      return;
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else if (this.front === 0) {
      this.front = this.size - 1;
    } else {
      this.front--;
    }

    this.arr[this.front] = key;
    console.log(`Inserted ${key} at front`);
  }

  insertRear(key) {
    if (this.isFull()) {
      console.log('Overflow! Cannot insert at rear');
      return;
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else if (this.rear === this.size - 1) {
      this.rear = 0;
    } else {
      this.rear++;
    }

    this.arr[this.rear] = key;
    console.log(`Inserted ${key} at rear`);
  }

  deleteFront() {
    if (this.isEmpty()) {
      console.log('Underflow! Cannot delete from front');
      return;
    }

    console.log('Deleting from front...', this.front);

    const removed = this.arr[this.front];
    this.arr[this.front] = null;  // <-- clear the slot
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.front === this.size - 1) {
      this.front = 0;
    } else {
      this.front++;
    }

    console.log(`Deleted ${removed} from front`, this.arr);
  }

  deleteRear() {
    if (this.isEmpty()) {
      console.log('Underflow! Cannot delete from rear');
      return;
    }

    const removed = this.arr[this.rear];
    this.arr[this.rear] = null; // <-- clear the slot
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.rear === 0) {
      this.rear = this.size - 1;
    } else {
      this.rear--;
    }

    console.log(`Deleted ${removed} from rear`);
  }

  getFront() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return null;
    }
    return this.arr[this.front];
  }

  getRear() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return null;
    }
    return this.arr[this.rear];
  }

  printDeque() {
    if (this.isEmpty()) {
      console.log('Deque is empty');
      return;
    }

    let i = this.front;
    let result = [];
    while (true) {
      result.push(this.arr[i]);
      if (i === this.rear) break;
      i = (i + 1) % this.size;
    }
    console.log('Deque contents:', result.join(' -> '));
  }
}

// Example usage:
const dq = new Deque(4);
dq.insertFront(5);
dq.insertRear(6);
dq.insertRear(7);
dq.insertFront(8);
dq.printDeque();  // Expected: 2 -> 5 -> 10 -> 20
dq.deleteRear();  // Expected: Deleted 20
dq.deleteFront(); // Expected: Deleted 2
dq.printDeque(); // Expected: 5 -> 10

Enter fullscreen mode Exit fullscreen mode

Time Complexity

The time complexity of all the above operations is constant i.e. O(1).

Applications of Deque Data Structure

  1. In undo operations on software.
  2. To store history in browsers.
  3. For implementing both stacks and queues.

Scale globally with MongoDB Atlas. Try free.

Scale globally with MongoDB Atlas. Try free.

MongoDB Atlas is the global, multi-cloud database for modern apps trusted by developers and enterprises to build, scale, and run cutting-edge applications, with automated scaling, built-in security, and 125+ cloud regions.

Learn More

Top comments (0)

Embedded BI Dashboards are 💩 Building them yourself is 💩

Embedded BI Dashboards are 💩 Building them yourself is 💩

Use our developer toolkit to build fast-loading, native-feeling dashboards for your customers (without the sh*t).

Get early access

👋 Kindness is contagious

Explore this practical breakdown on DEV’s open platform, where developers from every background come together to push boundaries. No matter your experience, your viewpoint enriches the conversation.

Dropping a simple “thank you” or question in the comments goes a long way in supporting authors—your feedback helps ideas evolve.

At DEV, shared discovery drives progress and builds lasting bonds. If this post resonated, a quick nod of appreciation can make all the difference.

Okay