Double-Ended Queue Visualizer

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:

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

Visual Example

Operation sequence on an empty deque:

  1. addFront(30): [30]
  2. addRear(40): [30, 40]
  3. addFront(20): [20, 30, 40]
  4. addRear(50): [20, 30, 40, 50]
  5. removeFront(): Returns 20 → [30, 40, 50]
  6. removeRear(): Returns 50 → [30, 40]

Implementation Variations

Common implementation approaches:
  1. Doubly Linked List:
    • Natural fit with head and tail pointers
    • All operations are O(1)
    • Extra memory for previous/next pointers
  2. Circular Array:
    • Fixed capacity but efficient
    • Requires careful index management
    • Good for memory-constrained environments
  3. 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:
  1. Undo/Redo operations: Store history at both ends
  2. Palindrome checking: Compare front and rear elements
  3. Steal algorithms: Work stealing in parallel processing
  4. Sliding window problems: Efficient maximum/minimum tracking
  5. 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

Double-Ended Queue (Deque) 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

Features: addFront, addRear, removeFront, removeRear, peekFront, peekRear, isEmpty, isFull, size, and print operations

Note: All implementations use circular array approach for efficient memory usage

Explore Other Types

Single Ended QueueCircular QueueMultiple QueuePriority Queue