# Queues

FIFO (first-in, first-out) containers implementing the `Queue<T>` interface: `enqueue`, `dequeue`, `peekFirst`.

## Implementations

### ArrayQueue

Array-backed queue. Simple but `dequeue` is O(n) due to `Array.shift()`.

| Operation   | Best | Average        | Worst |
| :---------- | :--- | :------------- | :---- |
| Space       | O(n) | O(n)           | O(n)  |
| `enqueue`   | O(1) | O(1) amortized | O(n)  |
| `dequeue`   | O(n) | O(n)           | O(n)  |
| `peekFirst` | O(1) | O(1)           | O(1)  |
| Iterate     | O(n) | O(n)           | O(n)  |

**Strengths:** Simplicity; good cache locality for iteration.

**Weaknesses:** O(n) `dequeue` — every removal shifts all remaining elements.

### LinkedQueue

Singly-linked list queue. O(1) for both `enqueue` and `dequeue`.

| Operation   | Best | Average | Worst |
| :---------- | :--- | :------ | :---- |
| Space       | O(n) | O(n)    | O(n)  |
| `enqueue`   | O(1) | O(1)    | O(1)  |
| `dequeue`   | O(1) | O(1)    | O(1)  |
| `peekFirst` | O(1) | O(1)    | O(1)  |
| Iterate     | O(n) | O(n)    | O(n)  |

**Strengths:** O(1) enqueue and dequeue — no shifting, no reallocation.

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

## Which to use

| Use case                          | Recommendation                                                   |
| :-------------------------------- | :--------------------------------------------------------------- |
| Hot path / high throughput        | **LinkedQueue** — O(1) dequeue is critical                       |
| Low-volume / simple usage         | **ArrayQueue** — simpler debugging, good enough for small queues |
| Bounded queue with known max size | **ArrayQueue** — pre-allocated array avoids allocation overhead  |

**Default choice: LinkedQueue.** The O(n) `dequeue` cost of `ArrayQueue` is a performance trap that worsens as the queue grows. Use `ArrayQueue` only when the queue stays small or dequeue is infrequent.

## Design notes

**Why no ring-buffer queue?** `ArrayQueue` intentionally delegates to plain `Array.shift()` rather than implementing a circular buffer with dynamic resizing. A ring-buffer queue would give O(1) amortized dequeue with array cache locality, but it adds implementation complexity (head/tail index management, resize-on-full) that isn't justified when `LinkedQueue` already provides O(1) on both operations. `ArrayQueue` exists as a simpler alternative for low-volume use cases where the O(n) cost is acceptable — not as a general-purpose high-performance queue. If a fixed-capacity ring buffer is needed, use `ArrayRingBuffer` from the `buffer` sub-path.