# Deque (Double-Ended Queue)

> Push and pop from both ends in O(1) — a stack and queue in one structure.

- **Category**: Data Structures
- **Subcategory**: linear
- **Canonical URL**: https://designpattern.fyi/data_structures/deque/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
Sliding window maximum — use a monotonic deque to compute max of every k-element window in O(n) total vs O(n²) naive. Work-stealing thread pool — each thread has a deque, steals from the back of other threads' deques. Palindrome check — push all chars, pop from both ends and compare.



## Implementation Example

```javascript
// ─── Deque backed by doubly linked list ──────────────────────
class DequeNode {
  constructor(value) { this.value = value; this.prev = null; this.next = null; }
}

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

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

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

  popFront() {
    if (!this.#head) return null;
    const val = this.#head.value;
    this.#head = this.#head.next;
    if (this.#head) this.#head.prev = null; else this.#tail = null;
    this.#size--;
    return val;
  }

  popBack() {
    if (!this.#tail) return null;
    const val = this.#tail.value;
    this.#tail = this.#tail.prev;
    if (this.#tail) this.#tail.next = null; else this.#head = null;
    this.#size--;
    return val;
  }

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

// ─── Monotonic Deque: Sliding Window Maximum in O(n) ─────────
// ❌ Naive O(n²): for each window, scan k elements for max
// ✅ Monotonic deque O(n): maintain decreasing deque of indices
function slidingWindowMax(nums, k) {
  const dq = new Deque(); // Stores indices, front = current max index
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // Remove indices outside the current window
    while (!dq.isEmpty() && dq.peekFront() < i - k + 1) dq.popFront();

    // Remove indices whose values are smaller than current (they can never be max)
    while (!dq.isEmpty() && nums[dq.peekBack()] < nums[i]) dq.popBack();

    dq.pushBack(i);

    if (i >= k - 1) result.push(nums[dq.peekFront()]); // Front is always max
  }
  return result;
}

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

```



## Trade-offs


### Advantages

- O(1) operations at both ends — the union of stack and queue capabilities

- Enables the powerful monotonic deque pattern for sliding window problems

- Single structure replaces stack + queue when you need both behaviors

- Flexible — can enforce LIFO or FIFO discipline on the same structure




### Considerations & Drawbacks

- More complex to implement than a plain stack or queue

- Doubly linked list backing has pointer overhead and poor cache locality

- Easy to misuse — if you only need one end, use a stack or queue for clarity

- No random access — middle elements are still O(n) to reach







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)