Deque Data Structure Explained

What Is a Deque?

A deque, pronounced "deck", is a linear data structure that allows elements to be inserted and removed from both ends of the sequence. The name comes from double-ended queue.

Unlike a standard queue, which normally adds elements at the rear and removes them from the front, a deque supports operations at both the front and the rear. This makes it useful when an application needs more flexibility in how elements enter or leave a data structure.

Front                                  Rear
  ↓                                      ↓
[ 10 ] [ 20 ] [ 30 ] [ 40 ]

Add/remove                          Add/remove
from this end                       from this end
     ↕                                   ↕

A deque can therefore behave like a queue, a stack, or a combination of both, depending on which operations an application performs.

Deque vs Standard Queue

A standard queue follows a more restricted access pattern: elements are inserted at the rear and removed from the front. A deque removes that restriction by allowing operations at both ends.

Core Deque Operations

A deque generally provides four fundamental insertion and deletion operations. Additional operations such as peek, size, and empty checks are commonly added as well.

Adding Elements at the Front

The addFront operation inserts a new element before the current first element. Existing elements maintain their relative order.

Deque:
Front → [20] [30] [40] ← Rear

addFront(10)

Deque:
Front → [10] [20] [30] [40] ← Rear

Adding Elements at the Rear

The addRear operation appends a new element after the current rear element.

Deque:
Front → [10] [20] [30] ← Rear

addRear(40)

Deque:
Front → [10] [20] [30] [40] ← Rear

Removing from the Front

The removeFront operation removes the first element from the deque. This is equivalent to the normal dequeue operation of a standard queue.

Deque:
Front → [10] [20] [30] [40] ← Rear

removeFront()

Removed: 10

Deque:
Front → [20] [30] [40] ← Rear

Removing from the Rear

The removeRear operation removes the last element from the deque. This is the operation that distinguishes a deque from a standard queue.

Deque:
Front → [10] [20] [30] [40] ← Rear

removeRear()

Removed: 40

Deque:
Front → [10] [20] [30] ← Rear

Deque as Both a Queue and a Stack

A deque can model the behavior of a standard queue by adding at the rear and removing from the front. It can also model a stack by adding and removing from the same end.

This flexibility is one of the main reasons deques appear in algorithms and systems that need to change how elements are processed depending on the situation.

Deque Using a JavaScript Array

A JavaScript array provides convenient methods such as push(), pop(), unshift(), and shift(). These methods can demonstrate deque behavior, although operations at the beginning of a JavaScript array may require shifting or reindexing elements.

const deque = [];

deque.push(20);
deque.push(30);

deque.unshift(10);

console.log(deque);
// [10, 20, 30]

deque.push(40);

console.log(deque);
// [10, 20, 30, 40]

The example is easy to understand, but it is not necessarily the most efficient implementation for large workloads because unshift() and shift() can require work proportional to the number of stored elements.

Efficient Deque with a Circular Array

A circular array can provide efficient operations at both ends. The implementation maintains front and rear positions and uses modulo arithmetic to wrap indexes around the underlying array.

Circular storage:

[  ] [  ] [  ] [  ] [  ]

Front and rear can move in either direction:

← Front                       Rear →
   └────── positions wrap ──────┘

This approach is particularly useful for fixed-capacity deques because positions released from one end can be reused when new elements are inserted at either end.

Linked-List Implementation

A doubly linked list is another natural way to implement a deque. Each node maintains references to both its previous and next nodes, allowing elements to be inserted or removed from either end without traversing the entire list.

             previous       next
                ←             →
Front → [10] ⇄ [20] ⇄ [30] ⇄ [40] ← Rear

The front reference points to the first node and the rear reference points to the last node. Because each node knows its neighbors, both ends can be updated directly.

Deque with a Doubly Linked List

The following implementation demonstrates the basic structure of a deque using a doubly linked list.

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class Deque {
  constructor() {
    this.front = null;
    this.rear = null;
    this.count = 0;
  }

  addFront(value) {
    const node = new Node(value);

    if (this.front === null) {
      this.front = node;
      this.rear = node;
    } else {
      node.next = this.front;
      this.front.prev = node;
      this.front = node;
    }

    this.count++;
  }

  addRear(value) {
    const node = new Node(value);

    if (this.rear === null) {
      this.front = node;
      this.rear = node;
    } else {
      node.prev = this.rear;
      this.rear.next = node;
      this.rear = node;
    }

    this.count++;
  }

  removeFront() {
    if (this.front === null) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;

    if (this.front === null) {
      this.rear = null;
    } else {
      this.front.prev = null;
    }

    this.count--;
    return value;
  }

  removeRear() {
    if (this.rear === null) {
      return null;
    }

    const value = this.rear.value;
    this.rear = this.rear.prev;

    if (this.rear === null) {
      this.front = null;
    } else {
      this.rear.next = null;
    }

    this.count--;
    return value;
  }

  isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }
}

Using the Linked-List Deque

Once the deque is implemented, elements can be inserted or removed from either end as required.

const deque = new Deque();

deque.addRear(20);
deque.addRear(30);
deque.addFront(10);
deque.addRear(40);

console.log(deque.removeFront()); // 10
console.log(deque.removeRear());  // 40
console.log(deque.removeFront()); // 20
console.log(deque.removeRear());  // 30

Deque Complexity

A properly implemented deque can provide constant-time operations at both ends. A doubly linked list is one common way to achieve this because the front and rear nodes are directly accessible.

Input-Restricted and Output-Restricted Deques

Not every deque implementation needs to expose all four insertion and deletion operations. Two restricted forms are commonly discussed in data structure theory.

Input-Restricted Deque

An input-restricted deque allows insertion at only one end but permits deletion from both ends.

Insertion:
Front ✕
Rear  ✓

Deletion:
Front ✓
Rear  ✓

Output-Restricted Deque

An output-restricted deque allows insertion at both ends but permits deletion from only one end.

Insertion:
Front ✓
Rear  ✓

Deletion:
Front ✓
Rear  ✕

These restricted variants are useful for understanding how different combinations of operations can produce specialized queue behavior.

Applications of Deques

Because a deque supports both ends, it is useful for algorithms and systems where the next element to process may need to be selected from either side.

• Sliding window algorithms: Maintain candidates entering and leaving a moving window.
• Palindrome checking: Compare characters from the front and rear.
• Task scheduling: Add urgent work to one end and normal work to another.
• Browser history or navigation models: Maintain sequences where elements may be managed from either side.
• Graph algorithms: Certain search strategies can benefit from adding and removing nodes at both ends.
• Undo or processing buffers: Allow work to be added or consumed from different ends depending on application rules.

Deque for Palindrome Checking

A deque provides a natural model for checking whether a sequence is a palindrome. The algorithm compares the first and last characters, removes both, and continues until the sequence is exhausted.

Input: "level"

Front → l e v e l ← Rear

Compare:
l == l
e == e

Middle:
v

Result: palindrome

Deque in Sliding Window Problems

Monotonic deques are frequently used in sliding-window problems. They allow an algorithm to remove outdated elements from the front while removing less useful candidates from the rear.

For example, when calculating the maximum value in every window of a fixed size, a deque can maintain candidate values in decreasing order. Elements that fall outside the current window are removed from the front, while smaller candidates can be removed from the rear.

Input:
[1, 3, -1, -3, 5, 3, 6, 7]

Window size = 3

The deque stores useful candidates
rather than every value in the current window.

This technique can reduce the time required for many sliding-window maximum or minimum problems from a straightforward O(n × k) approach to O(n).

Deque vs Queue vs Stack

These three structures are closely related but provide different access rules.

Common Mistakes

• Treating a deque as if elements can be inserted or removed from arbitrary middle positions.
• Using array shift() or unshift() repeatedly without considering their cost.
• Forgetting to update both front and rear references when the deque becomes empty.
• Breaking the previous and next links when implementing a deque with a doubly linked list.
• Confusing a deque with a priority queue. A deque chooses an end; a priority queue chooses according to priority.
• Using a circular implementation without clearly defining how full and empty states are represented.

When Should You Use a Deque?

A deque is a good fit when the algorithm needs efficient access to both ends of a sequence. It is particularly useful when elements can become candidates for removal from either side.

• You need insertion at both ends.
• You need deletion at both ends.
• You are implementing a sliding-window algorithm.
• You need a structure that can behave as either a stack or a queue.
• The application needs flexible end-based scheduling or buffering.

Key Takeaways

• A deque is a double-ended queue that supports operations at both ends.
• Elements can be added and removed from both the front and rear.
• A deque can model both queue and stack behavior.
• Doubly linked lists and circular arrays are common implementation choices.
• A properly implemented deque can perform all four primary end operations in O(1) time.
• Deques are useful in sliding-window algorithms, palindrome checking, scheduling, and buffering.
• Restricted deques limit insertion or deletion to one end.