Stacks

A stack is a linear data structure that follows the LIFO principle — Last In, First Out. Think of a stack of plates: you add new plates to the top, and you remove plates from the top. The last plate you placed on the stack is the first one you take off. This simple rule makes stacks perfect for tasks like tracking function calls, undo history in editors, parsing expressions, and backtracking algorithms.

Core Operations

push — add an element to the top of the stack
pop — remove and return the top element
peek (or top) — look at the top element without removing it
isEmpty — check whether the stack has any elements
isFull — for a fixed-size array implementation, check whether there is room left

Implementing a Stack with an Array

The simplest way to build a stack in C is with a fixed-size array plus an integer that tracks the index of the top element. Pushing increments the top index and writes to that slot; popping reads the slot and decrements the index.

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int top; /* index of the top element; -1 means empty */
} Stack;

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

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

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

int push(Stack *s, int value) {
    if (isFull(s)) {
        return 0; /* failure */
    }
    s->items[++(s->top)] = value;
    return 1; /* success */
}

int pop(Stack *s, int *outValue) {
    if (isEmpty(s)) {
        return 0; /* failure */
    }
    *outValue = s->items[(s->top)--];
    return 1; /* success */
}

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

int main(void) {
    Stack s;
    int value;

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

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

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

    return 0;
}

Note

The array-based stack has a fixed capacity (`MAX_SIZE`). Once it is full, `push` fails until something is popped. This is fine when you know a reasonable upper bound in advance.

Implementing a Stack with a Linked List

A linked-list-based stack has no fixed size limit (aside from available memory). Every push allocates a new node and makes it the new head; every pop removes the head node.

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

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

typedef struct {
    Node *top;
} LinkedStack;

void initLinkedStack(LinkedStack *s) {
    s->top = NULL;
}

int lsIsEmpty(const LinkedStack *s) {
    return s->top == NULL;
}

int lsPush(LinkedStack *s, int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        return 0;
    }
    node->data = value;
    node->next = s->top;
    s->top = node;
    return 1;
}

int lsPop(LinkedStack *s, int *outValue) {
    if (lsIsEmpty(s)) {
        return 0;
    }
    Node *old = s->top;
    *outValue = old->data;
    s->top = old->next;
    free(old);
    return 1;
}

int main(void) {
    LinkedStack s;
    int value;

    initLinkedStack(&s);
    lsPush(&s, 1);
    lsPush(&s, 2);
    lsPush(&s, 3);

    while (lsPop(&s, &value)) {
        printf("Popped: %d\n", value);
    }

    return 0;
}

Worked Example: Balanced Parentheses Checker

A classic use of a stack is checking whether the brackets in an expression are balanced — every opening bracket must be closed by the matching type, in the correct order. Every time we see an opening bracket we push it; every time we see a closing bracket we pop and check it matches.

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

#define MAX_SIZE 100

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

void csInit(CharStack *s) { s->top = -1; }
int csIsEmpty(const CharStack *s) { return s->top == -1; }
void csPush(CharStack *s, char c) { s->items[++(s->top)] = c; }
char csPop(CharStack *s) { return s->items[(s->top)--]; }

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

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

    for (size_t i = 0; i < strlen(expr); i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            csPush(&s, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (csIsEmpty(&s) || !isMatchingPair(csPop(&s), c)) {
                return 0;
            }
        }
    }
    return csIsEmpty(&s);
}

int main(void) {
    const char *tests[] = { "(a + [b * c])", "(a + [b)]", "{[()]}", "([)" };

    for (int i = 0; i < 4; i++) {
        printf("%-15s -> %s\n", tests[i], isBalanced(tests[i]) ? "balanced" : "NOT balanced");
    }

    return 0;
}

Tip

The balanced-parentheses check is a common interview question and the foundation for how compilers and expression evaluators validate syntax before parsing further.

Array vs Linked List: Which Should You Use?

Aspect	Array-based stack	Linked-list-based stack
Maximum size	Fixed at creation	Limited only by available memory
Memory overhead	None per element	Extra pointer per node
Cache locality	Good (contiguous memory)	Poorer (nodes scattered on the heap)
Implementation complexity	Very simple	Requires malloc/free discipline

Warning

With the linked-list implementation, always `free` popped nodes when you are done with them, and never dereference `s->top` without first checking `lsIsEmpty` — popping from an empty stack is undefined behavior.