Double Ended Queue

What is a Double-Ended Queue (Deque)?

A Double-Ended Queue (Deque) is a versatile data structure that allows insertion and deletion of elements from both ends (front and rear). Unlike a single-ended queue, it provides more flexibility while maintaining efficient O(1) operations.

Key Characteristics

Deques have these fundamental properties:

Two open ends:
- Supports operations at both front and rear
Four core operations:
- addFront() - Insert at front
- addRear() - Insert at rear
- removeFront() - Delete from front
- removeRear() - Delete from rear
Hybrid nature:
- Combines features of both stacks and queues

Visual Example

Operation sequence on an empty deque:

addFront(30): [30]
addRear(40): [30, 40]
addFront(20): [20, 30, 40]
addRear(50): [20, 30, 40, 50]
removeFront(): Returns 20 → [30, 40, 50]
removeRear(): Returns 50 → [30, 40]

Implementation Variations

Common implementation approaches:

Doubly Linked List:
- Natural fit with head and tail pointers
- All operations are O(1)
- Extra memory for previous/next pointers
Circular Array:
- Fixed capacity but efficient
- Requires careful index management
- Good for memory-constrained environments
Dynamic Array:
- Amortized O(1) operations
- May need occasional resizing

Time Complexity

addFront(): O(1)
addRear(): O(1)
removeFront(): O(1)
removeRear(): O(1)
peekFront(): O(1)
peekRear(): O(1)

Applications

Deques are used in:

Undo/Redo operations: Store history at both ends
Palindrome checking: Compare front and rear elements
Steal algorithms: Work stealing in parallel processing
Sliding window problems: Efficient maximum/minimum tracking
Browser history: Navigation in both directions

Special Cases

Interesting deque variations:

Input-Restricted Deque: Insertion only at one end
Output-Restricted Deque: Deletion only at one end
Palindrome Checker: Using deque properties
Priority Deque: Combines deque and priority queue features

The double-ended queue is a powerful hybrid data structure that combines the best features of stacks and queues. Its flexibility makes it invaluable for algorithms requiring access to both ends of a dataset, while maintaining efficient constant-time operations for all key functions.

Visualize Double Ended Queue (Deque) Operations

Deque is empty

FrontRear

Deque is empty

Test Your Knowledge before moving forward!

Queue Quiz Challenge

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Double Ended Queue Implementation

// Double-Ended Queue Implementation (JavaScript)
class Deque {
  constructor(size = 10) {
    this.items = new Array(size);
    this.front = -1;
    this.rear = 0;
    this.size = 0;
    this.capacity = size;
  }

  // Add to front
  addFront(item) {
    if (this.isFull()) {
      console.log("Deque Overflow");
      return;
    }
    if (this.front === -1) {
      this.front = 0;
      this.rear = 0;
    } else if (this.front === 0) {
      this.front = this.capacity - 1;
    } else {
      this.front--;
    }
    this.items[this.front] = item;
    this.size++;
  }

  // Add to rear
  addRear(item) {
    if (this.isFull()) {
      console.log("Deque Overflow");
      return;
    }
    if (this.front === -1) {
      this.front = 0;
      this.rear = 0;
    } else if (this.rear === this.capacity - 1) {
      this.rear = 0;
    } else {
      this.rear++;
    }
    this.items[this.rear] = item;
    this.size++;
  }

  // Remove from front
  removeFront() {
    if (this.isEmpty()) {
      console.log("Deque Underflow");
      return undefined;
    }
    const item = this.items[this.front];
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.front === this.capacity - 1) {
      this.front = 0;
    } else {
      this.front++;
    }
    this.size--;
    return item;
  }

  // Remove from rear
  removeRear() {
    if (this.isEmpty()) {
      console.log("Deque Underflow");
      return undefined;
    }
    const item = this.items[this.rear];
    if (this.front === this.rear) {
      this.front = -1;
      this.rear = -1;
    } else if (this.rear === 0) {
      this.rear = this.capacity - 1;
    } else {
      this.rear--;
    }
    this.size--;
    return item;
  }

  // Peek front
  peekFront() {
    if (this.isEmpty()) {
      console.log("Deque is empty");
      return undefined;
    }
    return this.items[this.front];
  }

  // Peek rear
  peekRear() {
    if (this.isEmpty()) {
      console.log("Deque is empty");
      return undefined;
    }
    return this.items[this.rear];
  }

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

  // Check if full
  isFull() {
    return this.size === this.capacity;
  }

  // Get current size
  getSize() {
    return this.size;
  }

  // Print deque contents
  print() {
    if (this.isEmpty()) {
      console.log("Deque is empty");
      return;
    }
    console.log("Deque contents (front to rear):");
    let i = this.front;
    let count = 0;
    while (count < this.size) {
      console.log(this.items[i]);
      i = (i + 1) % this.capacity;
      count++;
    }
  }
}

// Usage
const deque = new Deque(5);
deque.addRear(10);
deque.addFront(20);
deque.addRear(30);
console.log("Front element:", deque.peekFront()); // 20
console.log("Rear element:", deque.peekRear());   // 30
console.log("Deque size:", deque.getSize());      // 3
deque.print();
deque.removeFront();
console.log("After removeFront, front element:", deque.peekFront()); // 10

Explore Other Types

Single Ended Queue

Circular Queue

Multiple Queue

Priority Queue