Stack in C (Array and Linked List)

Some problems need you to undo things in reverse order: the last change is the first one you take back. A stack in C is the data structure built for exactly that. In this lesson, you'll learn the four stack operations, implement a stack with an array (including overflow and underflow checks), build a version on a linked list, and use a stack to check whether brackets in code are balanced.

What is a stack?

A stack is a collection where items are added and removed at only one end, called the top. This rule is called LIFO: Last In, First Out. The item you added most recently is always the next one to come out.

A stack has four basic operations:

All four take the same tiny amount of time no matter how many items the stack holds, because they only touch the top.

How push and pop work

Stack implementation using an array

The simplest stack is an array plus an integer top that holds the index of the top item. An empty stack has top = -1. We group them in a struct and pass a pointer to it, so the functions can change it. The functions return bool from <stdbool.h> to report success or failure.

Two error conditions need checks:

• Stack overflow: pushing onto a full stack. Without a check, you'd write past the end of the array.
• Stack underflow: popping from an empty stack. There's nothing to return.

#include <stdio.h>
#include <stdbool.h>

#define CAPACITY 5

struct Stack {
    int items[CAPACITY];
    int top;   /* index of the top item, -1 when empty */
};

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

bool is_empty(const struct Stack *s) {
    return s->top == -1;
}

bool is_full(const struct Stack *s) {
    return s->top == CAPACITY - 1;
}

bool push(struct Stack *s, int value) {
    if (is_full(s)) {
        printf("Stack overflow: cannot push %d\n", value);
        return false;
    }
    s->top++;
    s->items[s->top] = value;
    return true;
}

bool pop(struct Stack *s, int *out) {
    if (is_empty(s)) {
        printf("Stack underflow: nothing to pop\n");
        return false;
    }
    *out = s->items[s->top];
    s->top--;
    return true;
}

bool peek(const struct Stack *s, int *out) {
    if (is_empty(s)) {
        return false;
    }
    *out = s->items[s->top];
    return true;
}

int main(void) {
    struct Stack plates;
    init_stack(&plates);

    for (int i = 1; i <= 6; i++) {
        push(&plates, i * 10);   /* the 6th push overflows */
    }

    int value = 0;
    if (peek(&plates, &value)) {
        printf("Top plate: %d\n", value);
    }

    while (!is_empty(&plates)) {
        pop(&plates, &value);
        printf("Popped %d\n", value);
    }

    pop(&plates, &value);   /* one pop too many */
    return 0;
}

Stack overflow: cannot push 60
Top plate: 50
Popped 50
Popped 40
Popped 30
Popped 20
Popped 10
Stack underflow: nothing to pop

The items come out in the reverse order they went in: 10 was pushed first, so it's popped last. Because pop() and peek() must return two things (success and the value), they write the value through the out pointer, a technique from pass by reference.

Stack implementation using a linked list

An array stack has a fixed capacity. If you don't know how many items you'll need, build the stack on a linked list. The head of the list is the top: push inserts a new node at the head, and pop removes the head node and frees it.

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

struct Node {
    int data;
    struct Node *next;
};

bool push(struct Node **top, int value) {
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;          /* out of memory */
    }
    node->data = value;
    node->next = *top;
    *top = node;
    return true;
}

bool pop(struct Node **top, int *out) {
    if (*top == NULL) {
        return false;          /* underflow */
    }
    struct Node *old_top = *top;
    *out = old_top->data;
    *top = old_top->next;
    free(old_top);
    return true;
}

int main(void) {
    struct Node *top = NULL;

    push(&top, 1);
    push(&top, 2);
    push(&top, 3);

    int value = 0;
    while (pop(&top, &value)) {
        printf("Popped %d\n", value);
    }
    return 0;
}

Popped 3
Popped 2
Popped 1

The loop pops until the stack is empty, and each pop frees its node, so no memory is left behind. This stack never overflows unless the computer runs out of memory.

Array stack vs linked list stack

Real use case: checking balanced brackets

Compilers and code editors use a stack to check that every (, [ and { has a matching closing bracket in the right order. The idea:

1. When you see an opening bracket, push it.
2. When you see a closing bracket, pop the top. If the stack is empty or the popped bracket doesn't match, the text is unbalanced.
3. At the end, the stack must be empty; otherwise something was never closed.

#include <stdio.h>
#include <stdbool.h>

#define MAX_DEPTH 100

bool is_balanced(const char *text) {
    char stack[MAX_DEPTH];
    int top = -1;

    for (int i = 0; text[i] != '\0'; i++) {
        char c = text[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == MAX_DEPTH - 1) {
                return false;              /* too deep for our stack */
            }
            top++;
            stack[top] = c;                /* push */
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) {
                return false;              /* nothing to close */
            }
            char open = stack[top];        /* pop */
            top--;
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) {
                return false;              /* wrong kind of bracket */
            }
        }
    }
    return top == -1;                      /* everything opened was closed */
}

int main(void) {
    const char *tests[] = {
        "{ x = (a[0] + b) * 2; }",
        "(1 + 2]",
        "((total)",
        "if (a[i] > 0) { count++; }",
    };

    for (int i = 0; i < 4; i++) {
        printf("\"%s\" is %s\n", tests[i], is_balanced(tests[i]) ? "balanced" : "NOT balanced");
    }
    return 0;
}

"{ x = (a[0] + b) * 2; }" is balanced
"(1 + 2]" is NOT balanced
"((total)" is NOT balanced
"if (a[i] > 0) { count++; }" is balanced

In (1 + 2], the ] pops a (, which is the wrong kind. In ((total), one ( is still on the stack at the end.

Common mistakes with stacks

1. Skipping the overflow check

Pushing onto a full array stack without checking writes past the end of the array. That's undefined behavior: it can silently overwrite other variables or crash the program.

2. Popping an empty stack

Reading items[top] when top is -1 reads outside the array and returns a garbage value. Always check is_empty() first.

3. Off-by-one with top

If top starts at -1, increment before storing on push and read before decrementing on pop. Mixing up the order skips slot 0 or overwrites the top item.

4. Forgetting to free a linked list stack

If the program ends with items still on a linked list stack, those nodes leak. Pop everything (or free the list) before you finish.

Practice exercise

#include <stdio.h>

#define CAPACITY 50

int main(void) {
    const char *word = "DESSERTS";
    char stack[CAPACITY];
    int top = -1;

    for (int i = 0; word[i] != '\0' && top < CAPACITY - 1; i++) {
        top++;
        stack[top] = word[i];      /* push */
    }

    while (top != -1) {
        putchar(stack[top]);       /* pop */
        top--;
    }
    putchar('\n');
    return 0;
}

STRESSED

What's next?

A stack serves the newest item first. Next, learn its opposite, the queue in C, which serves the oldest item first, just like a line at a coffee shop.