Dequeue (Double-Ended Queue) Implementation Cheatsheet

Basic Implementation

class Deque {
    constructor() {
        this.items = {};
        this.frontIndex = 0;
        this.backIndex = 0;
    }

    addFront(item) {
        this.frontIndex--;
        this.items[this.frontIndex] = item;
    }

    addBack(item) {
        this.items[this.backIndex] = item;
        this.backIndex++;
    }

    removeFront() {
        if (this.isEmpty()) return undefined;
        const item = this.items[this.frontIndex];
        delete this.items[this.frontIndex];
        this.frontIndex++;
        return item;
    }

    removeBack() {
        if (this.isEmpty()) return undefined;
        this.backIndex--;
        const item = this.items[this.backIndex];
        delete this.items[this.backIndex];
        return item;
    }

    peekFront() {
        if (this.isEmpty()) return undefined;
        return this.items[this.frontIndex];
    }

    peekBack() {
        if (this.isEmpty()) return undefined;
        return this.items[this.backIndex - 1];
    }

    isEmpty() {
        return this.backIndex - this.frontIndex === 0;
    }

    size() {
        return this.backIndex - this.frontIndex;
    }

    clear() {
        this.items = {};
        this.frontIndex = 0;
        this.backIndex = 0;
    }
}

Time Complexities

Operation	Time Complexity	Description
addFront	O(1)	Add item to front
addBack	O(1)	Add item to back
removeFront	O(1)	Remove and return front item
removeBack	O(1)	Remove and return back item
peekFront	O(1)	Return front item without removing
peekBack	O(1)	Return back item without removing
isEmpty	O(1)	Check if deque is empty
size	O(1)	Get number of items
clear	O(1)	Remove all items

Usage Examples

Basic Operations

const deque = new Deque();

// Adding elements
deque.addFront(1);    // [1]
deque.addBack(2);     // [1, 2]
deque.addFront(0);    // [0, 1, 2]

// Removing elements
deque.removeFront();  // returns 0, deque is [1, 2]
deque.removeBack();   // returns 2, deque is [1]

// Peeking elements
deque.peekFront();    // returns 1
deque.peekBack();     // returns 1

Dequeue using DoublyLinkedList

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null; // Pointer to the previous node
    this.next = null; // Pointer to the next node
  }
}

class Deque {
  constructor() {
    this.front = null; // Pointer to the front node
    this.rear = null;  // Pointer to the rear node
    this.size = 0;     // Size of the deque
  }

  // Add an item at the front
  addFront(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = this.rear = newNode;
    } else {
      newNode.next = this.front;
      this.front.prev = newNode;
      this.front = newNode;
    }
    this.size++;
  }

  // Add an item at the rear
  addRear(value) {
    const newNode = new Node(value);
    if (this.isEmpty()) {
      this.front = this.rear = newNode;
    } else {
      newNode.prev = this.rear;
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  // Remove an item from the front
  removeFront() {
    if (this.isEmpty()) return null;  
    const removedValue = this.front.value;
    this.front = this.front.next;
    if (this.front) {
      this.front.prev = null;
    } else {
      this.rear = null; // Deque is now empty
    }
    this.size--;
    return removedValue;
  }

  // Remove an item from the rear
  removeRear() {
    if (this.size === 0) {
      return null; // Deque is empty
    }
    const removedValue = this.rear.value;
    this.rear = this.rear.prev;
    if (this.rear) {
      this.rear.next = null;
    } else {
      this.front = null; // Deque is now empty
    }
    this.size--;
    return removedValue;
  }

  // Get the size of the deque
  getSize = () => this.size;

  // Check if the deque is empty
  isEmpty = () => this.size === 0;

  // Peek at the front item
  peekFront = () => this.front ? this.front.value : null;

  // Peek at the rear item
  peekRear = () => this.rear ? this.rear.value : null;
}

// Example usage
const deque = new Deque();
deque.addFront(10);
deque.addRear(20);
console.log(deque.peekFront()); // 10
console.log(deque.peekRear());  // 20
console.log(deque.removeFront()); // 10
console.log(deque.removeRear());  // 20
console.log(deque.isEmpty()); // true

Common Applications

Sliding Window Maximum

function maxSlidingWindow(nums, k) {
    const deque = new Deque();
    const result = [];
    
    for (let i = 0; i < nums.length; i++) {
        // Remove elements outside window
        while (!deque.isEmpty() && deque.peekFront() < i - k + 1) {
            deque.removeFront();
        }
        
        // Remove smaller elements
        while (!deque.isEmpty() && nums[deque.peekBack()] < nums[i]) {
            deque.removeBack();
        }
        
        deque.addBack(i);
        
        // Add to result if window has reached size k
        if (i >= k - 1) {
            result.push(nums[deque.peekFront()]);
        }
    }
    
    return result;
}

Palindrome Check

function isPalindrome(str) {
    const deque = new Deque();
    
    // Add all characters to deque
    for (let char of str) {
        deque.addBack(char);
    }
    
    // Compare characters from both ends
    while (deque.size() > 1) {
        if (deque.removeFront() !== deque.removeBack()) {
            return false;
        }
    }
    
    return true;
}

Best Practices

1. Use object-based implementation for O(1) operations
2. Maintain front and back indices for efficient operations
3. Handle edge cases (empty deque, single element)
4. Implement size tracking for quick length checks
5. Clear references to prevent memory leaks
6. Use type checking for robust implementation

Memory-Efficient Version

class CompactDeque {
    constructor() {
        this.items = new Array(16);  // Initial capacity
        this.front = 8;              // Start in middle
        this.back = 8;
        this.capacity = 16;
    }

    resize(newCapacity) {
        const newItems = new Array(newCapacity);
        const size = this.size();
        const newFront = Math.floor((newCapacity - size) / 2);
        
        for (let i = 0; i < size; i++) {
            newItems[newFront + i] = this.items[(this.front + i) % this.capacity];
        }
        
        this.items = newItems;
        this.capacity = newCapacity;
        this.front = newFront;
        this.back = newFront + size;
    }

    addFront(item) {
        if (this.front === 0) {
            this.resize(this.capacity * 2);
        }
        this.front--;
        this.items[this.front] = item;
    }

    addBack(item) {
        if (this.back === this.capacity) {
            this.resize(this.capacity * 2);
        }
        this.items[this.back] = item;
        this.back++;
    }

    size() {
        return this.back - this.front;
    }
}

Common Pitfalls

1. ❌ Using array shift/unshift operations (O(n) complexity)
2. ❌ Not handling empty deque cases
3. ❌ Forgetting to update indices after operations
4. ❌ Not cleaning up removed elements
5. ❌ Inefficient resizing strategies

Performance Tips

1. ✅ Use object/array implementation instead of linked list
2. ✅ Implement lazy cleanup for removed elements
3. ✅ Use power-of-two capacity for efficient resizing
4. ✅ Maintain indices instead of restructuring data
5. ✅ Batch operations when possible