# Deques

Double-ended queues implementing the `Deque<T>` interface. Supports insertion and removal at both front and back: `push`/`pop` (back), `pushFront`/`dequeue` (front), `enqueue` (alias for `push`).

`Deque<T>` extends both `Queue<T>` and `Stack<T>`, so a deque can be used anywhere a queue or stack is expected.

Iteration order is front-to-back.

## Implementations

### ArrayDeque

Array-backed deque. Back operations are O(1); front operations are O(n) due to `Array.unshift()`/`Array.shift()`.

| Operation   | Best | Average        | Worst |
| :---------- | :--- | :------------- | :---- |
| Space       | O(n) | O(n)           | O(n)  |
| `push`      | O(1) | O(1) amortized | O(n)  |
| `pop`       | O(1) | O(1)           | O(1)  |
| `pushFront` | O(n) | O(n)           | O(n)  |
| `dequeue`   | O(n) | O(n)           | O(n)  |
| `peekFirst` | O(1) | O(1)           | O(1)  |
| `peekLast`  | O(1) | O(1)           | O(1)  |
| Iterate     | O(n) | O(n)           | O(n)  |

**Strengths:** Simple, cache-friendly iteration, low memory overhead. Good when back operations dominate.

**Weaknesses:** O(n) front operations — `pushFront` and `dequeue` shift all elements.

### LinkedDeque

Doubly-linked list deque. All four endpoint operations are O(1).

| Operation   | Best | Average | Worst |
| :---------- | :--- | :------ | :---- |
| Space       | O(n) | O(n)    | O(n)  |
| `push`      | O(1) | O(1)    | O(1)  |
| `pop`       | O(1) | O(1)    | O(1)  |
| `pushFront` | O(1) | O(1)    | O(1)  |
| `dequeue`   | O(1) | O(1)    | O(1)  |
| `peekFirst` | O(1) | O(1)    | O(1)  |
| `peekLast`  | O(1) | O(1)    | O(1)  |
| Iterate     | O(n) | O(n)    | O(n)  |

**Strengths:** O(1) on all four endpoint operations. No reallocation overhead.

**Weaknesses:** Higher per-element memory (two pointers per node); not cache-friendly.

## Which to use

| Use case                            | Recommendation                                                        |
| :---------------------------------- | :-------------------------------------------------------------------- |
| Both ends used frequently           | **LinkedDeque** — O(1) everywhere                                     |
| Mostly push/pop with rare front ops | **ArrayDeque** — cache-friendly, front ops infrequent enough to be OK |
| Memory-constrained                  | **ArrayDeque** — no per-element pointer overhead                      |
| Work-stealing / sliding window      | **LinkedDeque** — O(1) steal from front, O(1) push/pop from back      |

**Default choice: LinkedDeque.** The O(n) front operations of `ArrayDeque` are the same trap as `ArrayQueue.dequeue()`. Use `ArrayDeque` only when front operations are rare or the deque stays small.

## Design notes

**Why no ring-buffer deque?** Same rationale as `ArrayQueue` — `ArrayDeque` intentionally uses plain `Array.shift()`/`Array.unshift()` rather than a circular buffer with dynamic resizing. `LinkedDeque` already provides O(1) on all four endpoint operations, making it the correct default. `ArrayDeque` exists for the narrow case where back operations dominate and cache locality matters more than front-operation cost. For fixed-capacity circular buffering, use `ArrayRingBuffer`.

**Why does `Deque` expose both `enqueue` and `push`?** `Deque<T>` extends both `Queue<T>` and `Stack<T>` so that a deque can substitute for either — this is the primary design goal. TypeScript's structural typing means the substitutability would work without nominal inheritance, but extending both interfaces makes the relationship explicit and ensures implementors satisfy both contracts. The trade-off is that `enqueue` (from `Queue`) and `push` (from `Stack`) both add to the back. This is documented in the `Deque` interface JSDoc: prefer `push`/`pushFront` when using a deque directly.