Stacks

Overview

A stack is one of the simplest and most useful data structures in all of computing. It stores items in a strict order and enforces one rule: the last item you add is the first item you remove. That rule is called LIFO — Last In, First Out.

The everyday picture is a stack of plates. You place a new plate on top, and when you need one, you take it from the top. You never pull a plate out of the middle. The plate you set down most recently is the plate you pick up next.

You already have the tools to build one. From Arrays you know how to store many values of the same type in a contiguous block and reach any of them by index. From malloc and the heap you know how to request memory whose size is decided at run time. From free and ownership you know that whoever allocates memory is responsible for releasing it exactly once. A stack ties these three ideas together: it is an array (or a chain of heap nodes) that only lets you touch one end.

In plain language, a stack is a pile you only work with from the top. In terminology, it is an abstract data type (ADT) — a small, fixed set of operations (push, pop, peek, is_empty) whose behaviour is defined regardless of how you store the data underneath. That separation between what a stack does and how it is built is exactly what you will practise in this lesson.

Why it matters

Stacks are everywhere, often invisibly. Every time a C function calls another function, the machine pushes a stack frame (return address, saved registers, local variables) onto the program's call stack, and pops it when the function returns. That is why the structure is literally named after this data type, and why infinite recursion produces a stack overflow.

Beyond the call stack, LIFO order is the natural fit whenever you must remember what to come back to. Undo/redo in an editor, back-button history in a browser, depth-first traversal of a tree or graph, evaluating arithmetic expressions, and matching brackets in a parser all rely on stacks. The two exercises attached to this lesson — checking balanced brackets and measuring nesting depth — are real parsing problems that a stack solves cleanly and that are painful without one.

Learning to build a stack also teaches a habit you will reuse constantly: designing a small, safe interface around raw memory. Get push, pop, and cleanup right once, and you have a reusable, crash-resistant building block.

Core concepts

1. The LIFO rule and the stack ADT

Definition. A stack is a collection that supports adding an item to the top (push), removing the top item (pop), and inspecting the top item without removing it (peek). Removal always returns the most recently pushed item that has not yet been popped.

How it works. Think of the top as a single moving marker. push writes at the marker and moves it up; pop moves it down and reads. Nothing else in the collection is disturbed. Because you only ever touch one end, order is fully determined by when items arrived.

push A, push B, push C          pop  ->  returns C

    top --> [ C ]                    top --> [ B ]
            [ B ]                            [ A ]
            [ A ]  (bottom)                  (bottom)

When to use it. Whenever the next thing you need is the thing you saw most recently: reversing a sequence, backtracking, matching openers to closers. When NOT to use it. When you need first-come-first-served order (that is a queue, the next lesson), or when you need to reach items in the middle or search by value — a stack deliberately hides everything but the top.

Pitfall. Assuming you can peek deeper than the top. The ADT gives you exactly one visible element. If you find yourself wanting item number two, a stack is probably the wrong structure.

Knowledge check. You push 10, 20, 30, then pop once and push 40. What are the two values a caller sees if it now pops twice, in order?

2. Array-backed stack with a top index

Definition. Store elements in a contiguous array and keep an integer len that counts how many are in use. The top element is always at index len - 1; the next free slot is at index len.

How it works internally. push writes to data[len] then does len++. pop does len-- then reads data[len]. is_empty is simply len == 0. When len reaches the allocated cap, you must grow.

cap = 8, len = 3

index:   0    1    2    3    4    5    6    7
data:  [ A ][ B ][ C ][ ?? ][ ?? ][ ?? ][ ?? ][ ?? ]
                     ^
                     len (next free slot; top is len-1 = C)

Growth by doubling. When full, allocate a larger buffer (typically cap * 2) with realloc and copy over. Doubling means the occasional expensive copy is spread thinly across many cheap pushes, so the average cost per push stays constant — this is amortised O(1), the quiz answer. Growing by a fixed amount (say +1 each time) instead makes n pushes cost about n²/2 total copies: O(n²), which is disastrous.

When to use it. Default choice: cache-friendly (elements are contiguous), low overhead, fast. When NOT to. If you cannot tolerate occasional relocation pauses, or elements must never move in memory (other code holds pointers into them).

Pitfall. Off-by-one on the top: reading data[len] (one past the top) instead of data[len - 1], or forgetting to update len.

3. Linked-list stack (push/pop at the head)

Definition. A chain of heap-allocated nodes where each node holds a value and a pointer to the node below it. The stack owns a single top pointer to the head node.

How it works. push allocates a node, points its next at the current top, then makes it the new top. pop reads the top node, moves top to top->next, and frees the old node. Every operation touches only the head, so each is O(1) with no resizing and no relocation.

top --> [ C | *]--> [ B | *]--> [ A | NULL ]
         value next  value next  value  next(bottom)

When to use it. When the stack must never move existing elements, when sizes are wildly unpredictable, or when you want a guaranteed constant per-op cost with no amortisation. When NOT to. When you care about cache performance or memory overhead — each node costs a separate allocation plus a pointer.

Pitfall. Reading node->value after freeing the node (use-after-free), or forgetting to free popped nodes (leak).

Knowledge check (predict the output). With the array stack, cap starts at 0. After eight successive pushes with the doubling rule cap = cap ? cap*2 : 8, how many realloc calls happened, and what is cap?

Knowledge check (find the bug). A pop is written as s->len--; return s->data[s->len]; with no other checks. On an empty stack (len == 0), what does s->len become, and why is the following read undefined behaviour?

Syntax notes

The array-backed stack is just a struct plus a handful of functions. Note size_t for sizes/counts (it is unsigned and matches what malloc/realloc expect), and the pattern of returning a status code so the caller can react to a failed pop or a failed allocation.

typedef struct {
    int   *data;   // heap buffer holding the elements
    size_t len;    // number of elements currently in use
    size_t cap;    // number of slots allocated
} Stack;

int  sk_push(Stack *s, int value);        // 0 on success, -1 on alloc failure
int  sk_pop (Stack *s, int *out);         // 0 on success, -1 if empty
int  sk_peek(const Stack *s, int *out);   // 0 on success, -1 if empty
int  sk_is_empty(const Stack *s);         // 1 if empty, else 0
void sk_free(Stack *s);                    // release the buffer

Key structural points:

• The top is always data[len - 1]; the next free slot is data[len].
• pop and peek write their result through an out pointer and use the return value purely for success/failure — this keeps every int value (including negatives) usable as real data.
• cap == 0 initially, so the first push must allocate; the ternary s->cap ? s->cap * 2 : 8 handles that.

Lesson

What is a stack?

A stack stores items in LIFO order: Last In, First Out. The most recently added item is the first one removed.

Think of a stack of plates. You add a plate to the top, and you take a plate from the top. The last plate you put down is the first one you pick up.

Three core operations

• push — add an item to the top.
• pop — remove and return the item from the top.
• peek — look at the top item without removing it.

Two common implementations

• Array with a top index. Cache-friendly, and can be fixed-size or growable. A single index tracks where the top is.
• Linked list with operations at the head. Every push and pop happens at the head, so each operation is always O(1) (constant time, regardless of how many items the stack holds).

Where stacks are used

Stacks appear throughout software:

• Function call frames (the call stack)
• Depth-first search
• Undo buffers
• Expression evaluation
• JSON and XML parsing

Code examples

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int   *data;
    size_t len;
    size_t cap;
} Stack;

/* Push a value; grows by doubling. Returns 0 on success, -1 on alloc failure. */
int sk_push(Stack *s, int value) {
    if (s->len == s->cap) {
        size_t new_cap = s->cap ? s->cap * 2 : 8;      /* first grow -> 8 */
        int *grown = realloc(s->data, new_cap * sizeof *s->data);
        if (!grown) return -1;                         /* old buffer still valid */
        s->data = grown;
        s->cap  = new_cap;
    }
    s->data[s->len++] = value;                         /* write, then advance top */
    return 0;
}

/* Pop the top into *out. Returns 0 on success, -1 if the stack is empty. */
int sk_pop(Stack *s, int *out) {
    if (s->len == 0) return -1;                        /* guard: never read past bottom */
    *out = s->data[--s->len];                          /* step down, then read */
    return 0;
}

/* Read the top without removing it. Returns 0 on success, -1 if empty. */
int sk_peek(const Stack *s, int *out) {
    if (s->len == 0) return -1;
    *out = s->data[s->len - 1];
    return 0;
}

int sk_is_empty(const Stack *s) {
    return s->len == 0;
}

void sk_free(Stack *s) {
    free(s->data);
    s->data = NULL;                                    /* avoid dangling pointer */
    s->len = s->cap = 0;
}

int main(void) {
    Stack s = {0};   /* data=NULL, len=0, cap=0 -- a valid empty stack */

    for (int i = 1; i <= 5; i++) {
        if (sk_push(&s, i * 10) != 0) {
            fprintf(stderr, "out of memory\n");
            sk_free(&s);
            return 1;
        }
    }

    int top;
    if (sk_peek(&s, &top) == 0)
        printf("peek: %d (len=%zu cap=%zu)\n", top, s.len, s.cap);

    int v;
    printf("popping: ");
    while (sk_pop(&s, &v) == 0)
        printf("%d ", v);
    printf("\n");

    if (sk_pop(&s, &v) != 0)
        printf("pop on empty stack rejected (as expected)\n");

    sk_free(&s);       /* release the heap buffer exactly once */
    return 0;
}

What it does. It creates an empty stack, pushes 10, 20, 30, 40, 50, peeks at the top, then pops everything (which prints in reverse — the LIFO signature), and finally proves that popping an empty stack is rejected instead of crashing.

Expected output:

peek: 50 (len=5 cap=8)
popping: 50 40 30 20 10 
pop on empty stack rejected (as expected)

Edge cases to notice. The first push allocates a buffer of 8, so five pushes never trigger a second grow (cap stays 8). Assigning realloc's result to a new variable (grown) means that if allocation fails, the original buffer is untouched and we can report the error cleanly. sk_free is safe to call even on a never-grown stack because free(NULL) is defined to do nothing.

Line by line

1. Stack s = {0}; zero-initialises every field: data = NULL, len = 0, cap = 0. This is a fully valid empty stack — no allocation has happened yet.
2. First loop iteration, sk_push(&s, 10): len (0) == cap (0) is true, so we grow. new_cap = 8 (the ternary's else branch). realloc(NULL, 8 * sizeof(int)) behaves like malloc and returns a fresh buffer. data now points to it, cap = 8. Then s->data[0] = 10; len = 1.
3. Pushes for 20, 30, 40, 50: each time len < cap (1,2,3,4 all < 8), so no growth. Values land at indices 1–4; len ends at 5.
4. sk_peek(&s, &top): len != 0, so it reads data[len - 1] = data[4] = 50 into top. Prints peek: 50 (len=5 cap=8).
5. The pop loop calls sk_pop repeatedly. First call: len != 0, --len makes it 4, reads data[4] = 50. Next reads data[3]=40, then 30, 20, 10. After the fifth pop, len == 0.
6. The sixth sk_pop sees len == 0, returns -1 immediately without touching memory — that is the empty-stack guard doing its job.
7. sk_free(&s) releases the buffer once and nulls the pointer.

A trace of the top index through the run:

action        len (before -> after)   data touched     value seen
push 10        0 -> 1                 data[0]=10        -
push 20        1 -> 2                 data[1]=20        -
push 30        2 -> 3                 data[2]=30        -
push 40        3 -> 4                 data[3]=40        -
push 50        4 -> 5                 data[4]=50        -
peek           5 -> 5                 read data[4]      50
pop            5 -> 4                 read data[4]      50
pop            4 -> 3                 read data[3]      40
pop            3 -> 2                 read data[2]      30
pop            2 -> 1                 read data[1]      20
pop            1 -> 0                 read data[0]      10
pop (empty)    0 -> 0 (rejected)      none              -

Common mistakes

Mistake 1 — Popping (or peeking) an empty stack.

/* WRONG: no empty check */
int sk_pop(Stack *s, int *out) {
    *out = s->data[--s->len];   /* if len==0, --len underflows to SIZE_MAX! */
    return 0;
}

len is an unsigned size_t. Decrementing 0 wraps to a gigantic value, and data[SIZE_MAX] is far out of bounds — undefined behaviour, usually a crash. Fix: guard first, as in the lesson code: if (s->len == 0) return -1;. Recognise it: random crashes or garbage values right after the stack "should" be empty.

Mistake 2 — Assigning realloc back onto the same pointer.

/* WRONG: leaks the old buffer if realloc fails */
s->data = realloc(s->data, new_cap * sizeof *s->data);
if (!s->data) return -1;   /* original block is now lost forever */

When realloc fails it returns NULL but leaves the old block allocated. Overwriting s->data with NULL leaks it. Fix: assign into a temporary (grown) and only commit on success.

Mistake 3 — Growing by one slot per push.

/* WRONG: O(n^2) total work */
int *grown = realloc(s->data, (s->cap + 1) * sizeof *s->data);

This reallocates and potentially copies the whole array on every push. For 1,000,000 pushes that is ~500 billion element copies. Fix: double (cap * 2). Recognise it: filling a large stack is mysteriously slow and gets worse as it grows.

Mistake 4 — Forgetting cleanup. Building the stack and never calling sk_free leaks the whole buffer. In a long-running program this grows without bound. Fix: pair every successful build with exactly one sk_free, including on early-error return paths.

Debugging tips

Compiler errors.

• implicit declaration of function 'realloc' / 'malloc' — you forgot #include <stdlib.h>.
• dereferencing pointer to incomplete type — you used Stack before the full struct { ... } definition, or misspelled the typedef.
• Warning comparison of integers of different signedness when you compare len (unsigned) to a signed int loop counter — cast or use size_t consistently.

Runtime errors.

• Segfault right after emptying the stack usually means a missing empty-check in pop/peek (the size_t underflow bug).
• Run under sanitizers: compile with -fsanitize=address,undefined -g. AddressSanitizer pinpoints out-of-bounds reads (bad top index) and use-after-free; UBSan catches the unsigned underflow. valgrind ./a.out reports leaks ("definitely lost" bytes = a missing free).

Logic errors.

• Values come out in the wrong order? Confirm you read data[len - 1], not data[len], and that push does data[len++] (post-increment) while pop does data[--len] (pre-decrement).
• cap never grows past the initial 8 but you pushed thousands? Your grow branch condition is wrong — it should trigger on len == cap.

Questions to ask when it misbehaves. Is len ever allowed to exceed cap? After a pop, is the old top logically gone (does len decrease)? On every error path, did I free what I allocated? Is the top index len - 1 in every place I touch the top?

Memory safety

This topic is a concentrated dose of C memory discipline. Watch these specifically:

• Bounds. The only valid indices are 0 .. len-1. data[len] is the next free slot, legal to write during push (because len < cap) but never legal to read as data. Reading it in peek is a classic off-by-one out-of-bounds access.
• Unsigned underflow. len is size_t. --len when len == 0 wraps to SIZE_MAX, and any array access with that index is undefined behaviour. Always guard pop/peek with an emptiness check before decrementing.
• Initialisation. A stack must start in a known state ({0} gives data=NULL, len=0, cap=0). Using an uninitialised Stack means push may realloc a garbage pointer — undefined behaviour. Because realloc(NULL, n) acts like malloc, starting from NULL is deliberately safe.
• realloc ownership. On failure realloc returns NULL and keeps the old block alive. Never overwrite your only pointer to it before checking the result, or you leak. On success the old pointer may be freed by realloc — do not keep using stale copies of s->data (e.g. an interior pointer taken before a push).
• Lifetime after free. After sk_free, set data = NULL (the code does) so a later stray access faults loudly instead of corrupting freed memory. Do not pop or peek a freed stack.
• Overflow of the size math. new_cap * sizeof *s->data can overflow on absurdly large capacities; production code checks for that before allocating. For beginner-scale stacks it will not occur, but be aware it is the reason serious libraries validate the multiplication.

Getting these right turns a stack from a crash magnet into a dependable, reusable component.

Real-world uses

Concrete uses.

• The call stack. Every function call pushes a frame; returning pops it. Debuggers print this as the backtrace, and runaway recursion overflows it (a real stack overflow).
• Compilers and parsers. Matching (, [, { — exactly the Balanced brackets exercise — and evaluating expressions (converting infix to postfix, then evaluating) are textbook stack applications.
• Undo/redo in editors, back/forward in browsers, and depth-first search in graph/maze solvers all remember "where to return to" with a stack.
• Virtual machines like the JVM and CPython are stack machines: bytecode operands are pushed and popped from an operand stack.

Best-practice habits.

• Beginner: give operations clear names (sk_push, sk_pop); always check emptiness before popping; free exactly once; initialise with {0}; return status codes rather than crashing.
• Advanced: make the stack generic (store void* or bytes with an element-size parameter), validate the capacity multiplication for overflow, expose an is_empty/size accessor instead of poking at fields, keep the public interface small so the storage strategy (array vs list) can change without breaking callers, and document ownership (does pop transfer responsibility for freeing elements to the caller?).

Practice tasks

Beginner 1 — Complete the ADT. Starting from the lesson code, add int sk_size(const Stack *s) returning the element count and reuse sk_is_empty. In main, push 1..5, print the size, pop two items, and print the size again. Expected: size 5, then size 3. Concepts: top index, len. Hint: sk_size is a one-liner that returns len (cast to int if you print with %d).

Beginner 2 — Reverse a string with a stack. Read a line of text, push each character, then pop them all to print the string reversed. Input: stack → Output: kcats. Concepts: LIFO, push/pop. Hint: a stack of char works the same way as a stack of int; the reversal is the LIFO order doing the work for you.

Intermediate 1 — Balanced brackets. Implement int paren_balanced(const char *s) (the attached exercise): return 1 if every (, [, { is closed by the matching bracket in the correct nested order, else 0. Examples: "([]{})" → 1, "([)]" → 0, "(" → 0. Concepts: push openers, on a closer pop and compare, reject if the stack is empty or mismatched; at the end the stack must be empty. Hint: a mismatch and an empty-stack-on-closer are both failures.

Intermediate 2 — Two stacks, one array. Store two independent stacks in a single fixed-size array: one grows from the left (index 0 up), the other from the right (last index down). Support push/pop on each and detect "full" when the two tops would collide. Concepts: two top indices, bounds checking. Hint: the array is full when left_len + right_len == cap.

Challenge — Min-stack in O(1). Build a stack of ints that also answers sk_min (the smallest value currently stored) in O(1) time, alongside O(1) push and pop. Constraint: no scanning the whole stack per query. Concepts: auxiliary stack. Hint: keep a second stack whose top always holds the minimum so far; on push(v) push min(v, current_min) onto it, and pop both stacks together. Do not attempt to recompute the minimum by looping.

Summary

A stack is a LIFO collection: the last item pushed is the first popped. Its whole interface is tiny — push (add on top), pop (remove the top), peek (look at the top), and is_empty.

Most important syntax/mechanics. With an array + len index, the top is data[len - 1] and the next free slot is data[len]. push does data[len++] = v (after growing if len == cap); pop does v = data[--len] after checking len != 0. Grow by doubling capacity via realloc so push is amortised O(1) — growing one slot at a time is O(n²). A linked-list stack instead does everything at the head for a guaranteed O(1) with no resizing, at the cost of per-node memory and cache locality.

Common mistakes to remember. Never pop/peek without an empty check (unsigned len underflows to a huge index and crashes). Assign realloc into a temporary so a failure does not leak the old buffer. Grow geometrically, not by one. Free the buffer exactly once and null the pointer.

What to remember: a stack is a pile you only touch from the top; keep the interface small and safe, guard the empty case, double to grow, and always clean up.

Practice with these exercises

• Balanced brackets
• Maximum nesting depth