Deque (Double-Ended Queue)

Complexity

Operation	Time
`addFront` / `addBack`	O(1)
`removeFront` / `removeBack`	O(1)
`peekFront` / `peekBack`	O(1)
`isEmpty` / `size`	O(1)
Space	O(n)

A deque (pronounced "deck", short for double-ended queue) is a linear data structure that generalizes both a stack and a queue. Elements can be added or removed from either end — the front (head) or the back (tail) — in O(1) time.

   addFront(3)             addBack(4)
        ↓                       ↓
    ┌───────┬───────┬───────┬───────┐
    │   3   │   1   │   2   │   4   │   ← internal doubly linked list
    └───────┴───────┴───────┴───────┘
        ↑                       ↑
  removeFront()           removeBack()

Operations

Method	Description	Time
`addFront(v)`	Insert element `v` at the front	O(1)
`addBack(v)`	Insert element `v` at the back	O(1)
`removeFront()`	Remove and return the front element	O(1)
`removeBack()`	Remove and return the back element	O(1)
`peekFront()`	Return the front element without removing it	O(1)
`peekBack()`	Return the back element without removing it	O(1)
`isEmpty()`	Return `true` if the deque has no elements	O(1)
`size`	Return the number of elements	O(1)

Note: size is O(1) because the deque keeps a running element count that is updated on every add and remove operation.

Use Cases

A deque is the right tool when you need O(1) access at both ends:

Sliding window maximum/minimum — maintain candidates in a monotonic deque so each element is pushed and popped at most once (overall O(n)).
Browser history — navigate backward (removeFront) and forward (removeBack) through pages.
Undo / redo stacks — push actions to the back, undo from the back, redo from the front.
Palindrome checking — compare characters from both ends simultaneously.
Work-stealing schedulers (e.g. Java's ForkJoinPool) — threads push/pop from their own back, while idle threads steal from another thread's front.

Implementation Note

This implementation is backed by the project's existing DoublyLinkedList. Because every node keeps a reference to both its previous and next neighbours, this gives O(1) prepend (for addFront), O(1) deleteHead (for removeFront) and O(1) append / deleteTail (for addBack / removeBack), with no need to shift array elements. The number of elements is tracked in a counter, so size is O(1) too.

An alternative implementation using a circular buffer (fixed-size array) offers better cache locality but requires resizing logic. The linked-list approach is chosen here to stay consistent with the other data structures in this project.

Code

Deque.js

import DoublyLinkedList from '../doubly-linked-list/DoublyLinkedList';

export default class Deque {
  constructor() {
    // We use a doubly linked list internally so that both front and back
    // operations (add, remove and peek) run in O(1) time.
    this.linkedList = new DoublyLinkedList();

    // Keep a running element count so that `size` stays O(1).
    this.length = 0;
  }

  /**
   * Check if the deque is empty.
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.head;
  }

  /**
   * Read the element at the front of the deque without removing it.
   * @return {*}
   */
  peekFront() {
    if (!this.linkedList.head) {
      return null;
    }
    return this.linkedList.head.value;
  }

  /**
   * Read the element at the back of the deque without removing it.
   * @return {*}
   */
  peekBack() {
    if (!this.linkedList.tail) {
      return null;
    }
    return this.linkedList.tail.value;
  }

  /**
   * Add a new element to the front (head) of the deque.
   * @param {*} value
   */
  addFront(value) {
    this.linkedList.prepend(value);
    this.length += 1;
  }

  /**
   * Add a new element to the back (tail) of the deque.
   * @param {*} value
   */
  addBack(value) {
    this.linkedList.append(value);
    this.length += 1;
  }

  /**
   * Remove the element from the front (head) of the deque.
   * @return {*}
   */
  removeFront() {
    const removedHead = this.linkedList.deleteHead();
    if (!removedHead) {
      return null;
    }
    this.length -= 1;
    return removedHead.value;
  }

  /**
   * Remove the element from the back (tail) of the deque.
   * @return {*}
   */
  removeBack() {
    const removedTail = this.linkedList.deleteTail();
    if (!removedTail) {
      return null;
    }
    this.length -= 1;
    return removedTail.value;
  }

  /**
   * Return the number of elements in the deque.
   * @return {number}
   */
  get size() {
    return this.length;
  }

  /**
   * Convert the deque to an array (front to back).
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map((linkedListNode) => linkedListNode.value);
  }

  /**
   * Return a string representation of the deque.
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Complexity

Operations

Use Cases

Implementation Note

Code

References

Practice

Sliding Window

On this page

Deque (Double-Ended Queue)

ComplexityCopy Anchor Link

OperationsCopy Anchor Link

Use CasesCopy Anchor Link

Implementation NoteCopy Anchor Link

CodeCopy Anchor Link

ReferencesCopy Anchor Link

Practice

Sliding Window

On this page

Complexity

Operations

Use Cases

Implementation Note

Code

References