# Stacks

LIFO (last-in, first-out) containers implementing the `Stack<T>` interface: `push`, `pop`, `peekLast`.

## Implementations

### ArrayStack

Array-backed stack. Both `push` and `pop` operate at the end of the array.

| 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)  |
| `peekLast` | O(1) | O(1)           | O(1)  |
| Iterate    | O(n) | O(n)           | O(n)  |

**Strengths:** Cache-friendly, low memory overhead, simple. Iteration yields top-to-bottom.

**Weaknesses:** Rare O(n) `push` when the engine reallocates the backing array.

### LinkedStack

Singly-linked list stack. Uses head insertion/removal for O(1) push and pop with no reallocation.

| 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)  |
| `peekLast` | O(1) | O(1)    | O(1)  |
| Iterate    | O(n) | O(n)    | O(n)  |

**Strengths:** Guaranteed O(1) push/pop — no reallocation spikes.

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

## Which to use

| Use case                                   | Recommendation                                                   |
| :----------------------------------------- | :--------------------------------------------------------------- |
| General-purpose                            | **ArrayStack** — simpler, cache-friendly, amortized O(1) is fine |
| Latency-sensitive (no reallocation spikes) | **LinkedStack** — guaranteed O(1) worst case                     |
| Memory-constrained                         | **ArrayStack** — no per-element pointer overhead                 |

**Default choice: ArrayStack.** The amortized O(1) `push` is fast enough for nearly all use cases, and the cache-friendly array layout gives better real-world performance. Choose `LinkedStack` only when worst-case O(1) guarantees matter (e.g., real-time systems).