Why Stack Exists and What Problems It Solves in DSA C - Why This Pattern

Mental Model

A stack is a way to keep things in order so you can only add or remove the last thing you put in. It helps solve problems where you need to remember things in reverse order.

Analogy: Think of a stack like a stack of plates: you put new plates on top and take plates from the top only. You can't take a plate from the middle without removing the ones above it first.

Top -> [Plate3] -> [Plate2] -> [Plate1] -> null
↑ (top points here)

Dry Run Walkthrough

Input: Push plates 1, 2, 3 onto stack; then pop one plate

Goal: Show how stack keeps last-in-first-out order and solves reverse order problems

Step 1: Push plate 1 onto empty stack

Top -> [1] -> null

Why: We start by adding the first plate to the stack

Step 2: Push plate 2 on top of plate 1

Top -> [2] -> [1] -> null

Why: New plate goes on top, so it will be removed first

Step 3: Push plate 3 on top of plate 2

Top -> [3] -> [2] -> [1] -> null

Why: Stack grows by adding plates on top

Step 4: Pop top plate (plate 3) from stack

Top -> [2] -> [1] -> null

Why: We remove the last plate added, showing last-in-first-out

Result:

Top -> [2] -> [1] -> null
Popped plate: 3

Annotated Code

DSA C

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

#define MAX 10

typedef struct Stack {
    int items[MAX];
    int top;
} Stack;

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

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

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

void push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++(s->top)] = value; // add plate on top
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1;
    }
    return s->items[(s->top)--]; // remove plate from top
}

void printStack(Stack* s) {
    printf("Top -> ");
    for (int i = s->top; i >= 0; i--) {
        printf("[%d] -> ", s->items[i]);
    }
    printf("null\n");
}

int main() {
    Stack s;
    init(&s);

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

    printStack(&s);

    int popped = pop(&s);
    printf("Popped plate: %d\n", popped);

    printStack(&s);

    return 0;
}

s->items[++(s->top)] = value; // add plate on top

push plate on top of stack -- last-in

return s->items[(s->top)--]; // remove plate from top

pop plate from top -- first-out

Output

Top -> [3] -> [2] -> [1] -> null

Popped plate: 3

Top -> [2] -> [1] -> null

Complexity Analysis

Time: O(1) because push and pop only add or remove the top element without scanning

Space: O(n) because stack stores up to n elements in an array

vs Alternative: Compared to arrays where removing last element is O(1) but removing from front or middle is O(n), stack strictly enforces last-in-first-out to keep operations simple and fast

Edge Cases

Empty stack pop

Prints underflow message and returns -1 safely

DSA C

if (isEmpty(s)) { printf("Stack underflow\n"); return -1; }

Full stack push

Prints overflow message and does not add element

DSA C

if (isFull(s)) { printf("Stack overflow\n"); return; }

When to Use This Pattern

When you see problems needing to reverse order or remember last things first, reach for the stack pattern because it naturally handles last-in-first-out order efficiently.

Common Mistakes

Mistake: Trying to pop from an empty stack without checking causes errors
Fix: Always check if stack is empty before popping to avoid underflow

Summary

Stack stores items so the last added is the first removed (last-in-first-out).

Use stack when you need to reverse order or track recent items only.

The key insight is that you only add or remove from the top, like a stack of plates.