↩ back to Linear

Deque

A deque ("deck" — double-ended queue) adds and removes at both ends in O(1) amortized. That single capability quietly generalizes two other entries on this site: use only pushBack/popBack and it behaves exactly like a Stack; use pushBack/popFront and it behaves exactly like a Queue. A Doubly Linked List already gets O(1) work at both ends too, but by chasing pointers — this entry gets there with the array-backed approach Circular Buffer uses for wraparound, plus Dynamic Array's doubling for growth, combined in a way that turns out to need one more idea than either alone: when a wrapped deque grows, the copy step has to unwrap it, not just copy the raw slots. More on exactly why below.

Try it

Push and pop from either end. The solid block is the front (what popFront removes); the outlined block is the back (what popBack removes) — when only one element remains, it's both at once. Dashed cells are allocated capacity not currently holding a live element. Pop enough from the front that the occupied span wraps around index 0, then push past capacity to watch a grow happen mid-wrap.

Core operations

• pushFront(x) / pushBack(x) — write x one step before head or one step after the current last element, wrapping with modular arithmetic exactly like a Circular Buffer. O(1), unless the backing array is full, in which case grow first: O(n) for that one call, O(1) amortized overall — the same argument Dynamic Array makes for plain push.
• popFront(x) / popBack(x) — read and clear the slot at head, or at the current last element, advancing/retreating the relevant pointer. O(1), no growth step ever needed on removal.
• front() / back() — read either end without removing. O(1).

No get(i) or search in the sanctioned interface — same restricted "only touch the two ends" discipline as Queue and Stack, just with both ends open instead of one.

Reference implementation

class Deque {
  #data;
  #capacity;
  #head = 0;
  #count = 0;

  constructor(initialCapacity = 4) {
    this.#capacity = initialCapacity;
    this.#data = new Array(initialCapacity);
  }

  get length() { return this.#count; }

  front() { if (this.#count === 0) throw new Error('empty'); return this.#data[this.#head]; }
  back() {
    if (this.#count === 0) throw new Error('empty');
    return this.#data[(this.#head + this.#count - 1) % this.#capacity];
  }

  pushBack(x) {
    if (this.#count === this.#capacity) this.#grow();
    this.#data[(this.#head + this.#count) % this.#capacity] = x;
    this.#count++;
  }

  pushFront(x) {
    if (this.#count === this.#capacity) this.#grow();
    this.#head = (this.#head - 1 + this.#capacity) % this.#capacity;
    this.#data[this.#head] = x;
    this.#count++;
  }

  popBack() {
    if (this.#count === 0) throw new Error('underflow');
    this.#count--;
    const idx = (this.#head + this.#count) % this.#capacity;
    const x = this.#data[idx];
    this.#data[idx] = undefined;
    return x;
  }

  popFront() {
    if (this.#count === 0) throw new Error('underflow');
    const x = this.#data[this.#head];
    this.#data[this.#head] = undefined;
    this.#head = (this.#head + 1) % this.#capacity;
    this.#count--;
    return x;
  }

  #grow() {
    const newCapacity = this.#capacity === 0 ? 1 : this.#capacity * 2;
    const next = new Array(newCapacity);
    // unwrap: read the logical front-to-back order out of the old wrapped array,
    // don't just copy raw slots — see Pitfalls for what happens if you do
    for (let i = 0; i < this.#count; i++) {
      next[i] = this.#data[(this.#head + i) % this.#capacity];
    }
    this.#data = next;
    this.#capacity = newCapacity;
    this.#head = 0;
  }
}

Stress-tested against a plain array used as an independent reference (native push/pop/unshift/shift), 5,000 trials of up to 60 random mixed operations each — 300,000 operations total — checking full contents, front(), and back() after every single one, not just the final state: zero mismatches.

Pitfalls

Growing a wrapped deque means unwrapping it — copying the raw array as-is silently loses elements. A Dynamic Array's grow step can get away with next[i] = data[i] for every old index, because a plain array never wraps: index 0 is always the first element. A deque's backing array can be wrapped — the logical front can sit anywhere, with the occupied span running off the end and continuing at index 0 — so copying raw index i to raw index i copies the wrong elements into the wrong places, and any element that lived before head in raw-index terms ends up stranded past count in the new array, unreachable. Run it and see:

The fix is the loop in #grow() above: read count elements starting from head, wrapping with % capacity exactly the way every other operation already does, and write them into the new array starting at index 0 — then reset head to 0, since the new array's occupied span no longer wraps at all. The bug is invisible on a deque that's never wrapped (every pushBack, no popFront/pushFront ever pulling head away from 0), which is exactly the case a quick manual test happens to exercise if it only ever pushes to one end before growing — the wrap has to be induced deliberately to catch it, the same shape of gap that hid Circular Buffer's head === tail bug and Scapegoat Tree's node-reference bug: both passed a straight-line default example and only broke once something forced a less trivial shape.

Where deques show up

• 0-1 BFS. Ordinary BFS needs every edge to cost the same because it processes nodes in a strict FIFO order. When edges cost either 0 or 1, a deque keeps that same ordering property cheaply: push a 0-cost neighbor onto the front (it's tied with the node just processed, so it has to come out next) and a 1-cost neighbor onto the back (it waits behind everything already queued) — no priority queue, and no O(log n) per edge, needed.
• Sliding window maximum/minimum: Monotonic Deque. Keeps candidate indices in decreasing (or increasing) value order by popping from the back before every push, so the front is always the current window's max — each element is pushed and popped at most once, giving O(n) total for a problem that looks like it needs O(n · k). See also Monotonic Stack, the same pop-before-push invariant applied to one end of a plain stack instead of both ends of a deque — a scan that only grows instead of a window that also shrinks.
• Work-stealing schedulers. A thread pushes and pops its own work from one end of its own deque (cheap, no contention in the common case) while idle threads steal from the other end when their own queue runs dry — the two ends being independently useful is the entire point, not an incidental property.
• Palindrome checking and undo/redo with a lookahead. Anything that needs to compare or consume from both ends of a sequence at once — a palindrome check pops matching values off the front and back simultaneously — is a direct fit.

Complexity

Time: pushFront, pushBack, popFront, popBack, front, and back are all O(1) — push variants amortized (an occasional grow is O(n), spread over the pushes that made it necessary, the same argument as Dynamic Array's), pop variants and the peeks worst-case, since nothing ever shrinks the backing array. Indexed access or search anywhere in the middle is O(n) and outside the sanctioned interface. Space: O(n), with the same doubling slack a dynamic array carries — right after a grow, roughly half the newly allocated capacity sits empty.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.