jsschools

Deque (Double-Ended Queue)

A double-ended queue that supports O(1) insertion and removal from both the front and the back.

Spec ↗

Syntax

class Deque {
  #data = new DoublyLinkedList();
  pushFront(val) { ... }
  pushBack(val)  { ... }
  popFront()     { ... }
  popBack()      { ... }
}

Returns

Deque — A new Deque instance backed by a doubly linked list.

Examples

// Sliding window maximum using a deque (monotonic decreasing)
function maxSlidingWindow(nums, k) {
  const dq = []; // stores indices
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    while (dq.length && dq[0] < i - k + 1) dq.shift(); // remove out-of-window
    while (dq.length && nums[dq.at(-1)] <= nums[i]) dq.pop(); // maintain monotonicity
    dq.push(i);
    if (i >= k - 1) result.push(nums[dq[0]]);
  }
  return result;
}
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
Output 
[ 3, 3, 5, 5, 6, 7 ]

// JavaScript arrays can serve as a basic deque
const dq = [];
dq.push(1);       // pushBack  O(1) amortized
dq.unshift(0);    // pushFront O(n) — use a DLL for O(1)
console.log(dq.shift(), dq.pop()); // popFront, popBack
Output 
0 1

Notes

| Operation | Best | Avg | Worst | Space | |-----------|------|------|-------|-------| | pushFront | O(1) | O(1) | O(1) | O(1) | | pushBack | O(1) | O(1) | O(1) | O(1) | | popFront | O(1) | O(1) | O(1) | O(1) | | popBack | O(1) | O(1) | O(1) | O(1) | All four operations are O(1) only when backed by a doubly linked list. A fixed-size circular array can also achieve O(1) with no allocation overhead — see ring-buffer. A deque generalises both the stack and the queue.

See also