Deque (Double-Ended Queue)

Overview

A deque (pronounced "deck", short for double-ended queue) is a data structure that allows insertion and deletion from both ends (front and rear). Unlike a regular queue (FIFO) or stack (LIFO), a deque provides flexibility to add or remove elements from either end, making it versatile for many algorithms.

Deques are essential for problems requiring access to both ends, such as sliding window maximum, palindrome checking, and certain BFS variations. They can be implemented using arrays (with wraparound for circular deque) or doubly linked lists, providing O(1) operations for insertion and deletion at both ends.

Key characteristics:

• Double-ended - Insert/delete from both front and rear
• Flexible - Can act as queue, stack, or both
• O(1) operations - Insert/delete at both ends in constant time
• Versatile - Supports FIFO, LIFO, or mixed operations
• Two pointers - Front and rear pointers for both ends

How Deque Works

Deque maintains elements with access to both ends:

1. Front end - Insert/delete from front (like queue dequeue or stack pop)
2. Rear end - Insert/delete from rear (like queue enqueue or stack push)
3. Four operations - pushFront, popFront, pushRear, popRear
4. Flexible usage - Can use as queue, stack, or both
5. Implementation - Array (circular) or doubly linked list

The double-ended nature allows flexible element management.

Basic Deque Implementation (Doubly Linked List)

Using doubly linked list for O(1) operations:

class DequeNode<T> {
  val: T;
  prev: DequeNode<T> | null = null;
  next: DequeNode<T> | null = null;
  constructor(val: T) {
    this.val = val;
  }
}

class Deque<T> {
  private head: DequeNode<T> | null = null;
  private tail: DequeNode<T> | null = null;
  private size = 0;
  
  pushFront(item: T): void {
    const newNode = new DequeNode(item);
    
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head!.prev = newNode;
      this.head = newNode;
    }
    
    this.size++;
  }
  
  pushRear(item: T): void {
    const newNode = new DequeNode(item);
    
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.tail = newNode;
    }
    
    this.size++;
  }
  
  popFront(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const val = this.head!.val;
    
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = null;
    }
    
    this.size--;
    return val;
  }
  
  popRear(): T | undefined {
    if (this.isEmpty()) return undefined;
    
    const val = this.tail!.val;
    
    if (this.head === this.tail) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail!.prev;
      this.tail!.next = null;
    }
    
    this.size--;
    return val;
  }
  
  peekFront(): T | undefined {
    return this.head?.val;
  }
  
  peekRear(): T | undefined {
    return this.tail?.val;
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  getSize(): number {
    return this.size;
  }
}

Time: O(1) for all operations, Space: O(n)

Circular Deque Implementation (Array-Based)

Using circular array for fixed-size deque:

class CircularDeque<T> {
  private items: (T | null)[];
  private front = 0;
  private rear = 0;
  private size = 0;
  private capacity: number;
  
  constructor(capacity: number) {
    this.capacity = capacity;
    this.items = new Array(capacity).fill(null);
  }
  
  pushFront(item: T): boolean {
    if (this.isFull()) return false;
    
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.items[this.front] = item;
    this.size++;
    return true;
  }
  
  pushRear(item: T): boolean {
    if (this.isFull()) return false;
    
    this.items[this.rear] = item;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
    return true;
  }
  
  popFront(): T | null {
    if (this.isEmpty()) return null;
    
    const item = this.items[this.front];
    this.items[this.front] = null;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return item;
  }
  
  popRear(): T | null {
    if (this.isEmpty()) return null;
    
    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    const item = this.items[this.rear];
    this.items[this.rear] = null;
    this.size--;
    return item;
  }
  
  peekFront(): T | null {
    return this.isEmpty() ? null : this.items[this.front];
  }
  
  peekRear(): T | null {
    if (this.isEmpty()) return null;
    const rearIndex = (this.rear - 1 + this.capacity) % this.capacity;
    return this.items[rearIndex];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Time: O(1) for all operations, Space: O(capacity)

Key points:

• Use modulo arithmetic for wraparound
• (index - 1 + capacity) % capacity for moving backward
• Track size to distinguish empty from full

Pattern 1: Sliding Window Maximum

Use deque to find maximum in sliding window:

function maxSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = []; // Store indices
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with smaller values (they won't be max)
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add max to result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Key insight: Maintain deque with indices in decreasing order of values.

Pattern 2: Sliding Window Minimum

Find minimum in sliding window:

function minSlidingWindow(nums: number[], k: number): number[] {
  const deque: number[] = []; // Store indices
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with larger values (they won't be min)
    while (deque.length > 0 && nums[deque[deque.length - 1]] >= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add min to result when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time: O(n), Space: O(k)

Key insight: Maintain deque with indices in increasing order of values.

Pattern 3: Palindrome Checker

Use deque to check if string is palindrome:

function isPalindrome(s: string): boolean {
  const deque = new Deque<string>();
  
  // Add all characters to deque
  for (const char of s.toLowerCase().replace(/[^a-z0-9]/g, '')) {
    deque.pushRear(char);
  }
  
  // Compare from both ends
  while (deque.getSize() > 1) {
    if (deque.popFront() !== deque.popRear()) {
      return false;
    }
  }
  
  return true;
}

Time: O(n), Space: O(n)

Pattern 4: Design Circular Deque (LeetCode)

LeetCode-style circular deque:

class MyCircularDeque {
  private items: number[];
  private front = 0;
  private rear = 0;
  private size = 0;
  private capacity: number;
  
  constructor(k: number) {
    this.capacity = k;
    this.items = new Array(k);
  }
  
  insertFront(value: number): boolean {
    if (this.isFull()) return false;
    
    this.front = (this.front - 1 + this.capacity) % this.capacity;
    this.items[this.front] = value;
    this.size++;
    return true;
  }
  
  insertLast(value: number): boolean {
    if (this.isFull()) return false;
    
    this.items[this.rear] = value;
    this.rear = (this.rear + 1) % this.capacity;
    this.size++;
    return true;
  }
  
  deleteFront(): boolean {
    if (this.isEmpty()) return false;
    
    this.items[this.front] = undefined;
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return true;
  }
  
  deleteLast(): boolean {
    if (this.isEmpty()) return false;
    
    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    this.items[this.rear] = undefined;
    this.size--;
    return true;
  }
  
  getFront(): number {
    return this.isEmpty() ? -1 : this.items[this.front];
  }
  
  getRear(): number {
    if (this.isEmpty()) return -1;
    const rearIndex = (this.rear - 1 + this.capacity) % this.capacity;
    return this.items[rearIndex];
  }
  
  isEmpty(): boolean {
    return this.size === 0;
  }
  
  isFull(): boolean {
    return this.size === this.capacity;
  }
}

Time: O(1) for all operations

Pattern 5: Monotonic Deque (Next Greater Element)

Use deque to find next greater element:

function nextGreaterElements(nums: number[]): number[] {
  const deque: number[] = []; // Store indices
  const result = new Array(nums.length).fill(-1);
  
  for (let i = 0; i < nums.length; i++) {
    // Process elements smaller than current
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      const index = deque.pop()!;
      result[index] = nums[i];
    }
    
    deque.push(i);
  }
  
  return result;
}

Time: O(n), Space: O(n)

Key insight: Maintain decreasing order in deque.

Pattern 6: BFS with Deque (0-1 BFS)

Use deque for 0-1 BFS (edges have weight 0 or 1):

function bfs01(graph: number[][][], start: number): number[] {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;
  
  const deque: number[] = [start];
  
  while (deque.length > 0) {
    const node = deque.shift()!;
    
    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist[node] + weight;
      
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        
        // Add to front if weight is 0, rear if weight is 1
        if (weight === 0) {
          deque.unshift(neighbor);
        } else {
          deque.push(neighbor);
        }
      }
    }
  }
  
  return dist;
}

Time: O(V + E), Space: O(V)

Key insight: Process 0-weight edges first (add to front).

Pattern 7: Deque as Both Queue and Stack

Use deque to implement both queue and stack operations:

class QueueStack<T> {
  private deque = new Deque<T>();
  
  // Queue operations (FIFO)
  enqueue(item: T): void {
    this.deque.pushRear(item);
  }
  
  dequeue(): T | undefined {
    return this.deque.popFront();
  }
  
  // Stack operations (LIFO)
  push(item: T): void {
    this.deque.pushRear(item);
  }
  
  pop(): T | undefined {
    return this.deque.popRear();
  }
  
  peek(): T | undefined {
    return this.deque.peekRear();
  }
  
  isEmpty(): boolean {
    return this.deque.isEmpty();
  }
}

Use case: When you need both queue and stack functionality

When to Use Deque

Use deque when you see these signals:

• "Sliding window maximum/minimum" - Need to track extremum in window
• "Both ends" - Need to add/remove from both ends
• "Palindrome" - Check palindrome by comparing ends
• "0-1 BFS" - BFS with edge weights 0 or 1
• "Monotonic" - Need to maintain monotonic order
• "Next greater/smaller" - Find next extremum element
• "Flexible operations" - Need both queue and stack operations

Key distinction:

• Deque - Insert/delete from both ends, O(1) operations
• Queue - Insert rear, delete front only
• Stack - Insert/delete from one end only

Deque vs Queue vs Stack

| Aspect | Deque | Queue | Stack |

|--------|-------|-------|-------|

| Insert front | Yes (O(1)) | No | No |

| Insert rear | Yes (O(1)) | Yes (O(1)) | Yes (O(1)) |

| Delete front | Yes (O(1)) | Yes (O(1)) | No |

| Delete rear | Yes (O(1)) | No | Yes (O(1)) |

| Use case | Sliding window, both ends | BFS, FIFO | DFS, LIFO |

Remember:

• Deque for operations on both ends, sliding window problems
• Queue for FIFO processing, BFS
• Stack for LIFO processing, DFS

Template (Basic Deque)

class DequeTemplate<T> {
  private head: DequeNode<T> | null = null;
  private tail: DequeNode<T> | null = null;
  private size = 0;
  
  pushFront(item: T): void {
    // Add to front
  }
  
  pushRear(item: T): void {
    // Add to rear
  }
  
  popFront(): T | undefined {
    // Remove from front
  }
  
  popRear(): T | undefined {
    // Remove from rear
  }
  
  peekFront(): T | undefined {
    return this.head?.val;
  }
  
  peekRear(): T | undefined {
    return this.tail?.val;
  }
}

Template (Sliding Window Maximum)

function slidingWindowMaxTemplate(nums: number[], k: number): number[] {
  const deque: number[] = []; // Store indices
  const result: number[] = [];
  
  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside window
    while (deque.length > 0 && deque[0] <= i - k) {
      deque.shift();
    }
    
    // Remove indices with smaller values
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    // Add max when window is complete
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

Time and Space Complexity

Doubly Linked List Deque

• pushFront: O(1)
• pushRear: O(1)
• popFront: O(1)
• popRear: O(1)
• peekFront: O(1)
• peekRear: O(1)
• Space: O(n)

Circular Array Deque

• All operations: O(1)
• Space: O(capacity)

Sliding Window Maximum

• Time: O(n) - Each element added/removed at most once
• Space: O(k) - Deque size at most k

Note: All deque operations are O(1) with proper implementation.

Practice Tips

1. Choose implementation - Doubly linked list for dynamic, array for fixed size
2. Maintain order - Keep deque in decreasing order for max, increasing for min
3. Remove old indices - Remove indices outside window in sliding window problems
4. Monotonic deque - Maintain monotonic order for next greater/smaller problems
5. 0-1 BFS - Add 0-weight edges to front, 1-weight to rear
6. Both ends - Use deque when you need operations on both ends
7. Index tracking - Store indices in deque for sliding window problems

Common Mistakes

1. Wrong order - Not maintaining correct monotonic order
2. Not removing old indices - Forgetting to remove indices outside window
3. Index vs value - Confusing storing indices vs values
4. Modulo errors - Wrong modulo calculation in circular deque
5. Empty check - Not checking isEmpty before pop operations
6. Front/rear confusion - Mixing up front and rear operations
7. Memory leaks - Not clearing references in linked list implementation

Real-World Applications

Deques are used extensively in:

• Sliding Window Algorithms - Maximum/minimum in window
• Graph Algorithms - 0-1 BFS, certain shortest path problems
• String Processing - Palindrome checking, string manipulation
• Task Scheduling - Priority-based task management
• Browser History - Back/forward navigation
• Undo/Redo - Text editor operations
• Cache Implementation - LRU cache with deque
• Monotonic Problems - Next greater/smaller element

Related Concepts

• Queue - Single-ended queue (FIFO)
• Stack - Single-ended stack (LIFO)
• Sliding Window - Common deque application
• Monotonic Stack - Similar concept for single-ended operations
• Circular Queue - Fixed-size queue with wraparound
• Doubly Linked List - Implementation structure for deque

Summary

Deque is a versatile double-ended data structure:

• Double-ended - Insert/delete from both front and rear
• O(1) operations - All operations in constant time
• Flexible - Can act as queue, stack, or both
• Essential - For sliding window, 0-1 BFS, palindrome problems
• Versatile - Supports many different operation patterns

Key takeaways:

• Use deque for operations on both ends
• Maintain monotonic order for sliding window problems
• Store indices (not values) for sliding window maximum/minimum
• Essential for 0-1 BFS and sliding window algorithms
• More flexible than queue or stack alone

Mastering deque will help you solve sliding window, 0-1 BFS, and palindrome problems efficiently in coding interviews.