Stacks

Lesson

A stack stores items so the last in is the first out. Two implementations: an array with a top index (cache-friendly, fixed or growable) and a linked list with operations at the head (always O(1)).

Stacks appear everywhere: function call frames, depth-first search, undo buffers, expression evaluation, JSON/XML parsing.

Code examples

typedef struct { int *data; size_t cap, len; } stack_t;
int sk_push(stack_t *s, int v) {
    if (s->len == s->cap) {
        size_t nc = s->cap ? s->cap * 2 : 8;
        int *nd = realloc(s->data, nc * sizeof(int));
        if (!nd) return -1;
        s->data = nd; s->cap = nc;
    }
    s->data[s->len++] = v;
    return 0;
}

Common mistakes

• Not handling pop on an empty stack (return error, don't crash).
• Growing by 1 every push — that's O(n²) total. Always grow by doubling.