# Stacks

> ArrayList from one end, or no allocator at all.

```zig
const std = @import("std");
const expect = std.testing.expect;

test "ArrayList is the stack you want" {
    const gpa = std.testing.allocator;
    var stack: std.ArrayList(u32) = .empty;
    defer stack.deinit(gpa);

    try stack.append(gpa, 1);
    try stack.append(gpa, 2);
    try stack.append(gpa, 3);

    try expect(stack.pop().? == 3);
    try expect(stack.getLast() == 2);
    try expect(stack.items.len == 2);
}

test "pop returns null when empty" {
    const gpa = std.testing.allocator;
    var stack: std.ArrayList(u8) = .empty;
    defer stack.deinit(gpa);

    try expect(stack.pop() == null);
}

test "a bounded stack needs no allocator at all" {
    // For a known maximum, a fixed buffer avoids the heap entirely.
    var buffer: [8]u32 = undefined;
    var len: usize = 0;

    for ([_]u32{ 10, 20, 30 }) |v| {
        buffer[len] = v;
        len += 1;
    }
    len -= 1;
    try expect(buffer[len] == 30);
}

test "balanced bracket check" {
    const gpa = std.testing.allocator;
    var stack: std.ArrayList(u8) = .empty;
    defer stack.deinit(gpa);

    const input = "([]{})";
    var balanced = true;
    for (input) |c| switch (c) {
        '(', '[', '{' => try stack.append(gpa, c),
        ')' => balanced = balanced and stack.pop() == '(',
        ']' => balanced = balanced and stack.pop() == '[',
        '}' => balanced = balanced and stack.pop() == '{',
        else => {},
    };
    try expect(balanced and stack.items.len == 0);
}
```

*Runnable: compiled to WebAssembly and executed by CI against Zig master. (`03-standard-library.stacks`)*

Zig has no dedicated `Stack` type because it does not need one. An `ArrayList`
used from the end is a stack:

| Operation | Call |
| --- | --- |
| push | `append(gpa, x)` |
| pop | `pop()` (returns `?T`) |
| peek | `getLast()` |
| size | `items.len` |

`pop()` returns an optional, so the empty case is handled by the type rather
than by a precondition you might forget.

## When the depth is bounded

If you know the maximum, skip the allocator entirely: a fixed array plus a
length index is a complete stack with no failure mode. This matters for
embedded targets and hot paths, and it is the sort of thing Zig makes
comfortable rather than exotic.

## Why not a linked list

A linked-list stack allocates per element and scatters them across memory.
`ArrayList` amortises to one allocation and keeps everything contiguous, which
is faster for essentially every real workload. Reach for a linked list only
when you need stable addresses or O(1) splicing.