Queue

Double Ended

What is a Double-Ended Queue (Deque)?

A deque drops the "only one end" restriction of a normal queue: you can insert or remove elements at both the front and the rear, and both directions stay O(1).

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

How Does It Work?

Both ends are live. Where a normal queue only lets the rear grow and the front shrink, a deque lets either pointer move in either direction. Follow this sequence on an initially empty deque:

addRear(10): [10]
addRear(20): [10, 20] — rear grows to the right
addFront(5): [5, 10, 20] — front grows to the left instead
removeRear(): Returns 20 → [5, 10]
removeFront(): Returns 5 → [10]

Just insertedJust removedSitting in the deque

Steps 2 and 3 are the whole idea: the same deque accepted a new element at the rear and then at the front, and the boxes already in it never moved. Use only addRear and removeFront and you have an ordinary FIFO queue; use only addRear and removeRear and you have a stack. That is why a deque is described as a hybrid of the two.

Time Complexity

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

Every operation touches only a pointer at one end, never the elements in between, so all six stay flat as the deque grows:

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

Because it can act like a stack from one end and a queue from the other, a deque is genuinely a hybrid of the two. That flexibility is exactly why it turns up in algorithms that need fast access to both ends of a dataset at once.

Daily DSA Challenge by Scale Engineer

Double-Ended Queue Visualiser

Deque is empty

Test Your Knowledge before moving forward!

Deque Quiz

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

Done With the Learning

Mark Double Ended Queue as done and view it on your dashboard

Explore Other Types

Single Ended Queue

Circular Queue

Multiple Queue

Priority Queue