Implementing Deques

1. Creating Deque Class

A deque (double-ended queue) is a data structure that allows insertion and deletion at both ends. Below is the implementation of a basic deque class in JavaScript.

Example: Basic Deque Implementation

class Deque {
  constructor() {
    this.items = [];
  }

  // Add an element to the front
  pushFront(element) {
    this.items.unshift(element);
  }

  // Add an element to the back
  pushBack(element) {
    this.items.push(element);
  }

  // Remove an element from the front
  popFront() {
    return this.items.shift();
  }

  // Remove an element from the back
  popBack() {
    return this.items.pop();
  }

  // Peek at the front element
  peekFront() {
    return this.items[0];
  }

  // Peek at the back element
  peekBack() {
    return this.items[this.items.length - 1];
  }

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

  // Get the size of the deque
  size() {
    return this.items.length;
  }
}

// Example usage:
const deque = new Deque();
deque.pushBack(1);
deque.pushBack(2);
deque.pushFront(0);
console.log(deque.peekFront()); // 0
console.log(deque.peekBack());  // 2

Method	Description	Time Complexity	Space Complexity
pushFront(element)	Adds an element to the front of the deque	O(n)	O(1)
pushBack(element)	Adds an element to the back of the deque	O(1)	O(1)
popFront()	Removes and returns the front element	O(n)	O(1)
popBack()	Removes and returns the back element	O(1)	O(1)
peekFront()	Returns the front element without removing it	O(1)	O(1)
peekBack()	Returns the back element without removing it	O(1)	O(1)
isEmpty()	Checks if the deque is empty	O(1)	O(1)
size()	Returns the number of elements in the deque	O(1)	O(1)

2. Creating Deque

A deque (double-ended queue) is a data structure that allows insertion and deletion at both ends. Below are the key properties and methods for creating and managing a deque.

Property/Method	Description	Example
pushFront(item)	Adds an item to the front of the deque	`deque.pushFront(10);`
pushBack(item)	Adds an item to the back of the deque	`deque.pushBack(20);`
popFront()	Removes and returns the item from the front	`let item = deque.popFront();`
popBack()	Removes and returns the item from the back	`let item = deque.popBack();`
front()	Returns the item at the front without removing it	`let item = deque.front();`
back()	Returns the item at the back without removing it	`let item = deque.back();`
size()	Returns the number of items in the deque	`let size = deque.size();`
isEmpty()	Checks if the deque is empty	`let empty = deque.isEmpty();`

Example: Creating and Using a Deque

class Deque {
  constructor() {
    this.items = [];
  }

  pushFront(item) {
    this.items.unshift(item);
  }

  pushBack(item) {
    this.items.push(item);
  }

  popFront() {
    return this.items.shift();
  }

  popBack() {
    return this.items.pop();
  }

  front() {
    return this.items[0];
  }

  back() {
    return this.items[this.items.length - 1];
  }

  size() {
    return this.items.length;
  }

  isEmpty() {
    return this.items.length === 0;
  }
}

// Example usage
let deque = new Deque();
deque.pushFront(10);
deque.pushBack(20);
console.log(deque.front()); // 10
console.log(deque.back());  // 20
deque.popFront();
console.log(deque.front()); // 20

3. Inserting at Front

Method	Description	Time Complexity	Space Complexity
insertFront(element)	Inserts an element at the front of the deque	O(1)	O(1)

Example: Inserting at Front

const deque = [10, 20, 30];
deque.unshift(5);
console.log(deque); // [5, 10, 20, 30]

4. Inserting at Rear

Inserting an element at the rear of a deque involves adding the element to the end of the underlying data structure. The operation's efficiency depends on the deque's implementation.

Operation	Time Complexity	Space Complexity	Description
insertAtRear(element)	`O(1)`	`O(1)`	Inserts an element at the rear of the deque

Example: Inserting at Rear in a Doubly Linked List Implementation

class DequeNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

class Deque {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  insertAtRear(data) {
    const newNode = new DequeNode(data);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      newNode.prev = this.rear;
      this.rear = newNode;
    }
  }
}

const deque = new Deque();
deque.insertAtRear(10);
deque.insertAtRear(20);
// Deque now contains: 10 <-> 20

5. Removing from Front

Method	Description	Time Complexity	Space Complexity
removeFront()	Removes and returns the element at the front of the deque	O(1)	O(1)

Example: Removing from Front

const deque = [1, 2, 3, 4, 5];
deque.shift(); // Removes and returns 1
console.log(deque); // [2, 3, 4, 5]

6. Removing from Rear

Method	Description	Time Complexity	Space Complexity
removeFromBack()	Removes and returns the element at the rear of the deque	O(1)	O(1)
pop()	Alias for removeFromBack() in some implementations	O(1)	O(1)

Example: Removing from Rear

const deque = [1, 2, 3, 4, 5];

// Remove from rear
const removed = deque.pop(); // returns 5
console.log(deque); // [1, 2, 3, 4]
console.log(removed); // 5

Note: In JavaScript arrays, pop() removes and returns the last element. For a true deque implementation, use a library like double-ended-queue.

7. Peeking Front Element

Method	Description	Time Complexity	Space Complexity
peekFront()	Returns the element at the front of the deque without removing it	O(1)	O(1)

Example: Peeking Front Element

const deque = [10, 20, 30, 40];

const frontElement = deque[0]; // 10

console.log(frontElement); // Output: 10

8. Peeking Rear Element

Method	Description	Time Complexity	Space Complexity
peekRear()	Returns the element at the rear of the deque without removing it	O(1)	O(1)

Example: Peeking Rear Element

const deque = [1, 2, 3, 4, 5];
const rearElement = deque[deque.length - 1];
console.log(rearElement); // Output: 5

9. Checking if Empty

Method	Description	Time Complexity	Space Complexity
isEmpty()	Returns `true` if the deque is empty, otherwise `false`.	`O(1)`	`O(1)`

Example: Checking if Deque is Empty

const deque = new Deque();
console.log(deque.isEmpty()); // true

deque.pushBack(10);
console.log(deque.isEmpty()); // false