# Queues & Deques — Part 1: The Pattern

A **queue** is first-in, first-out: you add at the back and remove from the front. It's the backbone of **BFS** (`graphs/01`), task scheduling, rate limiting by time window, and simulations. A **deque** (double-ended queue) adds O(1) operations at both ends, which enables the **monotonic deque**: the standard O(n) answer to "maximum (or minimum) of every sliding window".

![A monotonic deque for sliding window maximum: the front is always the current max](diagrams/01-monotonic-deque.svg)

## 1. Queues in Each Language

| | Python | TypeScript / JavaScript | C# |
|---|---|---|---|
| FIFO queue | `collections.deque`: `append`, `popleft` | array + **head index** (avoid `shift()`, which is O(n)) | `Queue<T>`: `Enqueue`, `Dequeue`, `Peek` |
| deque | `deque`: `append`, `appendleft`, `pop`, `popleft` | array with head index, or a ring buffer | `LinkedList<T>` (`AddFirst/AddLast/RemoveFirst/RemoveLast`) |
| priority queue | `heapq` (see `trees/04`) | implement a heap | `PriorityQueue<TElement, TPriority>` |

> **Interview trap:** `list.pop(0)` in Python and `array.shift()` in JavaScript are **O(n)**, so a BFS written with them becomes O(n²). Use `deque` or a head pointer.

## 2. Recognition Cues

- "process in arrival order", "level by level", "shortest number of steps" → queue (BFS)
- "requests in the last 3000 ms", "moving average of the last k values" → queue of timestamps/values, evict from the front
- "maximum/minimum of each window of size k" → monotonic deque
- "design a circular buffer", "bounded queue" → fixed array + head/tail indices modulo capacity

## 3. Monotonic Deque Template

```typescript
function windowMax(nums: number[], k: number): number[] {
  const dq: number[] = [];             // use a head pointer instead of shift() for O(1)
  let head = 0;
  const out: number[] = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++;
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}
```

```python
from collections import deque

def window_max(nums, k):
    dq = deque()                       # indices; values decreasing front → back
    out = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:      # front fell out of the window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()                    # smaller values can never be a max again
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])     # front is the window maximum
    return out
```

The deque keeps indices whose values are **decreasing** from front to back. When a new value arrives, every smaller value behind it can never be a window maximum again (the new value is larger and stays in the window longer), so it's popped from the back. The front is evicted when it slides out of the window. Each index enters and leaves once: **O(n)** total, versus O(n·k) for recomputing each window's max.

## 4. Circular Buffers

A fixed-capacity queue stores items in an array with `head` and `size` (or `head` and `tail`); positions wrap with `% capacity`. Enqueue writes at `(head + size) % capacity`; dequeue advances `head`. Everything is O(1) with no allocations, which is why ring buffers are used in network stacks, logging and audio.

## Under the Hood: Why `deque` Is O(1) at Both Ends

CPython's `deque` is a doubly linked list of fixed-size blocks (64 slots each), so appends and pops at either end touch only the end block. Indexing into the middle is O(n). C#'s `Queue<T>` is a circular array that doubles when full (amortized O(1) enqueue). A JavaScript array used with `shift()` must re-index every remaining element, which is why the head-pointer trick matters.

## Common Pitfalls

1. **O(n) dequeues** with `pop(0)` / `shift()`.
2. **Storing values instead of indices** in a monotonic deque: you can't tell when the front leaves the window.
3. **Evicting at the wrong time:** remove the expired front *before* reading the max.
4. **Off-by-one in circular buffers:** distinguish full from empty (keep a `size` counter).
5. **Using a deque when a heap is needed:** a monotonic deque works for sliding windows; arbitrary removals need a heap.

## Quick Reference

```text
Queue: deque.append / popleft · Queue<T>.Enqueue / Dequeue · JS: arr + head index
Window max: pop front if out of window; pop back while ≤ x; push i; answer = a[front]
Circular: tail = (head + size) % cap
All O(1) per operation; sliding window max O(n)
```