C Stacks

A stack is a linear data structure that stores elements in Last-In, First-Out (LIFO) order: the last item you add is the first one you remove. Think of a stack of plates — you place new plates on top, and you always take the top plate off first. Stacks are one of the most important structures in computer science, powering function call management, expression evaluation, undo systems, backtracking algorithms, and parsers. C has no built-in stack type, so you build one yourself, usually with an array or a linked list — and understanding how to do that teaches you a lot about memory and pointers along the way.

Overview / How a Stack Works

A stack supports two core operations: push (add an element to the top) and pop (remove the element currently on top). A well-designed stack also offers peek (look at the top element without removing it) and isEmpty (check whether the stack has anything in it). Every operation touches only the "top" of the structure, which is what makes stacks fast: push, pop, and peek all run in O(1) constant time, regardless of how many elements the stack holds.

In C, you can implement a stack in two fundamentally different ways:

• Array-based stack — a fixed-size (or manually resized) array plus an integer top index that tracks the current top position. Fast and cache-friendly, but has a maximum capacity unless you write resizing logic.
• Linked-list-based stack — each element is a heap-allocated node with a pointer to the node below it. The stack’s "top" is just a pointer to the head node. This grows and shrinks dynamically, limited only by available memory, but each push/pop involves a malloc/free call and extra pointer overhead.

Internally, in the array version, top is simply an index into the array; pushing increments it and writes a value, popping reads a value and decrements it. Nothing is actually deleted from memory when you pop — the old value is just left behind and considered "out of bounds" because top no longer points to it. In the linked-list version, popping actually calls free() on the node’s memory, which is why forgetting to free is a common source of memory leaks (covered below).

Syntax

There’s no stack keyword in C — you define the structure and functions yourself. The typical shape for an array-based integer stack looks like this:

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s);
int  isEmpty(Stack *s);
int  isFull(Stack *s);
int  push(Stack *s, int value);
int  pop(Stack *s, int *value);
int  peek(Stack *s, int *value);

Part	Meaning
data[MAX_SIZE]	Fixed-size backing array that holds the stack’s elements.
top	Index of the current top element; -1 means the stack is empty.
push(s, value)	Increments top and stores value at data[top].
pop(s, value)	Reads data[top] into *value, then decrements top.
peek(s, value)	Reads data[top] without changing top.

A linked-list stack instead stores a pointer to the top Node, where each Node holds a value and a pointer to the node beneath it — push allocates a new node and makes it the new top; pop reads the top node’s value, relinks top to the next node, and frees the old one.

Examples

Example 1: Array-Based Integer Stack

This example implements a fixed-capacity stack of integers with overflow and underflow protection, then pushes three values and pops them all off.

#include <stdio.h>

#define MAX_SIZE 5

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX_SIZE - 1;
}

int push(Stack *s, int value) {
    if (isFull(s)) {
        printf("Stack overflow: cannot push %d\n", value);
        return 0;
    }
    s->data[++(s->top)] = value;
    return 1;
}

int pop(Stack *s, int *value) {
    if (isEmpty(s)) {
        printf("Stack underflow: cannot pop\n");
        return 0;
    }
    *value = s->data[(s->top)--];
    return 1;
}

int peek(Stack *s, int *value) {
    if (isEmpty(s)) {
        return 0;
    }
    *value = s->data[s->top];
    return 1;
}

int main(void) {
    Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    int top;
    peek(&s, &top);
    printf("Top element: %d\n", top);

    int value;
    while (!isEmpty(&s)) {
        pop(&s, &value);
        printf("Popped: %d\n", value);
    }

    pop(&s, &value);

    return 0;
}

Output:
Top element: 30
Popped: 30
Popped: 20
Popped: 10
Stack underflow: cannot pop

Three values are pushed, so top ends at index 2 holding 30. peek reads that value without removing it. The while loop then pops every element in reverse order of insertion (30, 20, 10) — proof of LIFO behavior. The final call to pop happens on an empty stack, and because isEmpty is checked first, the program safely reports underflow instead of reading garbage memory.

Example 2: Balanced Brackets Checker

Stacks are the natural tool for matching opening and closing symbols. This program uses a character stack to check whether brackets in an expression are properly balanced.

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;
} CharStack;

void initStack(CharStack *s) {
    s->top = -1;
}

int isEmpty(CharStack *s) {
    return s->top == -1;
}

void push(CharStack *s, char c) {
    s->data[++(s->top)] = c;
}

char pop(CharStack *s) {
    return s->data[(s->top)--];
}

int isMatchingPair(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '[' && close == ']') ||
           (open == '{' && close == '}');
}

int isBalanced(const char *expr) {
    CharStack s;
    initStack(&s);

    for (int i = 0; expr[i] != '\0'; i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&s) || !isMatchingPair(pop(&s), c)) {
                return 0;
            }
        }
    }
    return isEmpty(&s);
}

int main(void) {
    const char *expressions[] = {
        "(a + b) * ",
        "{[a + (b * c)] - d}",
        "(a + b] * ,
               isBalanced(expressions[i]) ? "Balanced" : "Not balanced");
    }

    return 0;
}

Output:
(a + b) *  -> Balanced
{[a + (b * c)] - d} -> Balanced
(a + b] * .
Pop: check isEmpty; if not empty, read data[top], then decrement top. The old value physically remains in the array but is now considered inaccessible.
Peek: read data[top] without touching top at all.

For the linked-list version, each push/pop involves pointer rewiring rather than index arithmetic: pushing links a new node in front of the current top; popping unlinks the current top and returns memory to the heap. This is why a linked-list stack never "fills up" the way an array-based one does — it only fails when the operating system can no longer satisfy a malloc request.
Common Mistakes
Mistake 1: Skipping Overflow/Underflow Checks
A push or pop without bounds checking silently corrupts memory or reads garbage:
int data[5];
int top = -1;

void push(int value) {
    data[++top] = value; /* no check against array size */
}

Calling push a sixth time writes past the end of data, which is undefined behavior — it may silently corrupt an unrelated variable or crash the program much later, far from the actual bug. Always guard both operations:
void push(int value) {
    if (top == 4) {
        printf("Stack overflow\n");
        return;
    }
    data[++top] = value;
}

Mistake 2: Leaking Memory in a Linked-List Stack
It’s easy to remove a node from the chain without freeing it:
int pop(LinkedStack *s, int *value) {
    Node *temp = s->top;
    *value = temp->data;
    s->top = temp->next;
    return 1; /* temp is never freed — memory leak */
}

Every popped node here becomes unreachable but still occupies heap memory, since nothing points to it anymore and it was never released. Over a long-running program this steadily exhausts available memory. The fix is to call free(temp) once its data has been copied out, and to fully drain (and free) the stack before the program exits, as shown in freeStack in Example 3.
Best Practices

Always check isEmpty before popping and isFull before pushing (array-based) to prevent undefined behavior.
Choose the array-based stack when you know a safe upper bound on size and want maximum speed and cache locality; choose the linked-list stack when the size is unpredictable or potentially very large.
Wrap stack operations in functions (as shown) rather than manipulating top directly wherever you use the stack — it keeps the invariants (bounds, indexing) in one place.
For a linked-list stack, always free() every node you pop, and drain the whole stack before your program ends to avoid leaks.
Use a stack (instead of recursion) to convert deep recursive algorithms into iterative ones when you need to avoid stack-overflow from the call stack itself.
Make the element type generic with void * or a typedef if you need a stack of more than one data type across your program.

Practice Exercises

Exercise 1: Extend the array-based Stack from Example 1 with a function int stackSum(Stack *s) that returns the sum of all elements currently on the stack without permanently removing them (hint: pop everything into a temporary array, sum it, then push the values back in the original order).
Exercise 2: Write a program that uses a character stack to reverse a string in place, pushing every character then popping them back into a new buffer. For input "Stacks", the expected output is "skcatS".
Exercise 3: Using the LinkedStack from Example 3, write a function int stackContains(LinkedStack *s, int target) that returns 1 if target is anywhere in the stack and 0 otherwise, without permanently modifying the stack’s contents.

Summary

A stack follows LIFO order: the most recently pushed element is the first one popped.
C has no built-in stack — you implement one with a fixed-size array plus a top index, or with a linked list of heap-allocated nodes.
Push, pop, and peek all run in O(1) time because they only ever touch the top of the structure.
Array-based stacks are fast but bounded in size; linked-list stacks grow dynamically but require careful memory management.
Always guard against overflow (array-based) and underflow (both types) before performing an operation.
Stacks are the natural tool for matching/nesting problems (brackets, undo systems) and for converting recursive algorithms into iterative ones.