Nitin Soni

Posted on May 16

Deque

#webdev #dsa #programming #javascript

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.

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.

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

1. Insert at the Front

This operation adds an element at the front.

Check if the deque is full.

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

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

2. Insert at the Rear

This operation adds an element to the rear.

Check if the deque is full.
If the deque is full, insertion operation cannot be performed (overflow condition).
If the deque is empty, reinitialize rear = 0. And, add the new key into array[rear].
If rear = n - 1, reinitialize real = 0 (first index).
Else, increase rear by 1.

Add the new key 5 into array[rear].

3. Delete from the Front

The operation deletes an element from the front.

Check if the deque is empty.

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

4. Delete from the Rear

This operation deletes an element from the rear.

Check if the deque is empty.

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

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

DEV Community