Deques

A deque adds front insertion and removal to a queue; backed by a doubly-linked list it keeps all four operations at O(1) and powers the sliding-window max.

5 min read Level 3/5 #dsa#deque#double-ended-queue

What you'll learn

Describe the deque API and when it is preferable to a stack or queue
Implement a doubly-linked-list deque with O(1) push/pop at both ends
Use a monotonic deque to solve sliding-window maximum in O(n)

A deque (double-ended queue, pronounced “deck”) generalises both the stack and the queue: you can push and pop from either end. That extra flexibility unlocks a family of sliding-window algorithms that would be O(n²) with a plain queue.

API

Method	Description	Time
pushFront(v)	Add to the front	O(1)
pushBack(v)	Add to the back	O(1)
popFront()	Remove from front	O(1)
popBack()	Remove from back	O(1)
peekFront()	Read front without removing	O(1)
peekBack()	Read back without removing	O(1)

Doubly-Linked-List Implementation

A doubly-linked list gives true O(1) at both ends without any amortization:

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

class Deque {
  #head = null;
  #tail = null;
  #size = 0;

  pushBack(value) {
    const node = new DNode(value);
    if (this.#tail) { this.#tail.next = node; node.prev = this.#tail; }
    this.#tail = node;
    if (!this.#head) this.#head = node;
    this.#size++;
  }

  pushFront(value) {
    const node = new DNode(value);
    if (this.#head) { this.#head.prev = node; node.next = this.#head; }
    this.#head = node;
    if (!this.#tail) this.#tail = node;
    this.#size++;
  }

  popFront() {
    if (!this.#head) throw new Error("Deque is empty");
    const value = this.#head.value;
    this.#head = this.#head.next;
    if (this.#head) this.#head.prev = null;
    else this.#tail = null;
    this.#size--;
    return value;
  }

  popBack() {
    if (!this.#tail) throw new Error("Deque is empty");
    const value = this.#tail.value;
    this.#tail = this.#tail.prev;
    if (this.#tail) this.#tail.next = null;
    else this.#head = null;
    this.#size--;
    return value;
  }

  peekFront() { return this.#head?.value; }
  peekBack()  { return this.#tail?.value; }
  get size()  { return this.#size; }
  isEmpty()   { return this.#size === 0; }
}

Sliding-Window Maximum

Given an array and a window size k, find the maximum in each window as it slides from left to right. Brute force is O(nk). A monotonic deque brings it to O(n).

The deque stores indices in decreasing order of value. When the window slides:

Remove the front if it has fallen outside the window.
Remove from the back while the back value is smaller than the incoming value (it can never be a future maximum while the new element is in the window).
The front is always the current window’s maximum.

function maxSlidingWindow(nums, k) {
  const deque = []; // stores indices; front = largest value's index
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // drop out-of-window indices from the front
    if (deque.length && deque[0] <= i - k) deque.shift();

    // maintain decreasing order — drop smaller values from the back
    while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();

    deque.push(i);

    // start recording results once the first full window is complete
    if (i >= k - 1) result.push(nums[deque[0]]);
  }

  return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

Note: the implementation above uses a plain array as the backing store for the deque. For production code with very large windows, replace the array with the Deque class above to avoid the O(k) worst-case shift.

Up Next

A circular buffer trades dynamic sizing for a fixed-capacity ring that never allocates, making it ideal for streaming and audio scenarios.

Circular Buffer →