Stack Implementation in C

Analogy categoryAnalogies

1. Introduction

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle: the last element pushed onto the stack is the first one popped off. Real-world analogies include a stack of plates or the 'undo' history in an editor. Stacks are used heavily in C programs for function call management (the call stack), expression evaluation, parenthesis matching, and depth-first traversal algorithms.

🏏

Cricket analogy: A stack's LIFO principle is like the batting order collapsing under pressure, the last batter who walked in is the first to be dismissed as wickets tumble, mirroring how a stack pops its most recently pushed item first.

A stack can be implemented using either a fixed-size array or a linked list. The array-based version is simpler and faster for a fixed maximum capacity, while a linked list version allows dynamic growth. This lesson focuses on the array-based implementation, since it clearly illustrates the concepts of overflow and underflow.

🏏

Cricket analogy: Choosing array vs linked-list stack implementation is like choosing a fixed 11-player squad for a tournament versus a flexible reserve pool that can grow, the fixed squad being simpler to manage but capped in size.

2. Syntax

#define MAX 100

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

The 'top' field tracks the index of the most recently pushed element. An empty stack is conventionally initialized with 'top = -1'. Pushing increments 'top' and writes to items[top]; popping reads items[top] and decrements 'top'.

🏏

Cricket analogy: The 'top' field tracking the most recent push is like the scoreboard tracking the current batter's position in the order, starting at -1 before play begins, incrementing as each new batter walks in, decrementing as each one is dismissed.

3. Explanation

The three core stack operations are push (add an element to the top), pop (remove and return the top element), and peek/top (view the top element without removing it). Each operation must first check a boundary condition: push must verify the stack is not full (top < MAX - 1), and pop/peek must verify the stack is not empty (top >= 0).

🏏

Cricket analogy: Push, pop, and peek map to sending in a new batter, dismissing the current one, and simply checking who's on strike without removing them, each requiring a boundary check, like verifying there are still wickets in hand before batting continues.

Because the array has a fixed capacity MAX, pushing beyond that capacity is called stack overflow, and popping from an empty stack is called stack underflow. Both are common bugs in stack-based code and must be explicitly guarded against, since C does not perform automatic bounds checking on arrays.

🏏

Cricket analogy: Stack overflow is like trying to send in an 12th batter when only 11 are allowed, and underflow is like the scorer trying to record a dismissal when no batter is actually at the crease, both bugs the umpire must explicitly guard against.

Stack overflow (pushing when top == MAX - 1) and stack underflow (popping when top == -1) are the two classic stack bugs in C. Because C arrays have no built-in bounds checking, writing past items[MAX-1] causes undefined behavior (silent memory corruption), and reading items[-1] does the same. Always check these conditions before every push and pop.

Time complexity: push, pop, and peek are all O(1) for an array-based stack because they only touch the element at index 'top' and increment/decrement an integer — no shifting or traversal is required.

4. Example

#include <stdio.h>

#define MAX 5

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

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

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

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

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

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow: cannot pop\n");
        return -1; /* sentinel value */
    }
    return s->items[(s->top)--];
}

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

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

    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s));

    push(&s, 40);
    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s)); /* triggers underflow */

    return 0;
}

5. Output

text

Popped: 30
Popped: 20
Popped: 40
Popped: 10
Stack underflow: cannot pop
Popped: -1

6. Key Takeaways

A stack follows LIFO: the last element pushed is the first popped.
'top' tracks the current top index; -1 conventionally means empty.
Always guard push against overflow (top == MAX - 1) and pop against underflow (top == -1).
Push, pop, and peek are all O(1) operations for an array-based stack.
Stacks underpin function calls, expression evaluation, and undo/backtracking logic.