← Index

Linear Structures

Deque

Push and pop from both ends — a stack and a queue in one.

What it is

A double-ended queue lets you add or remove from either the front or the back in O(1). It subsumes both stack and queue behavior, and is the go-to structure whenever an algorithm needs to look at a 'window' of data and drop items from either side as that window moves.

Real-world examples

• A deck of cards where you can draw from the top or the bottom.
• A line at a theme park with a fast-pass entrance at the front and the regular line joining at the back — both ends are active.

Where you've probably used this already

• Sliding window maximum/minimum problems — keep a deque of candidate indexes, drop from whichever end no longer qualifies.
• Browser history that supports both 'back' and being able to trim the oldest entries once it gets too long.
• JS's own Array is flexible enough to act as a deque via push/pop/shift/unshift, though shift/unshift are O(n) unlike a true deque.

Complexity

Code

// Deque (Double-Ended Queue) — push/pop from BOTH ends in O(1).
// It's a stack and a queue at the same time, from either side.

class Deque {
  constructor() {
    this.items = {};
    this.front = 0;
    this.back = 0;
  }

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

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

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

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

  isEmpty() {
    return this.front === this.back;
  }
}

// --- Example: sliding window maximum, the classic reason deques show up ---
// Keeps indexes in the deque in decreasing order of their value, so the
// front is always the max of the current window.
function slidingWindowMax(nums, k) {
  const dq = new Deque();
  // use plain arrays as a simpler deque for this specific algorithm
  const window = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    while (window.length && nums[window[window.length - 1]] <= nums[i]) {
      window.pop(); // drop smaller values, they can never be the max now
    }
    window.push(i);

    if (window[0] <= i - k) window.shift(); // drop indexes outside the window

    if (i >= k - 1) result.push(nums[window[0]]);
  }
  return result;
}

// --- Example Usage ---
const dq = new Deque();
dq.addBack(2);
dq.addBack(3);
dq.addFront(1);
console.log("removeFront:", dq.removeFront()); // 1
console.log("removeBack:", dq.removeBack());   // 3

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