Stack Concept and LIFO Principle in DSA C

Mental Model

A stack is a collection where the last item added is the first one taken out. This is called Last In, First Out (LIFO).

Analogy: Think of a stack of plates: you put a new plate on top and take the top plate off first.

Top
 ↑
[ 3 ]
[ 2 ]
[ 1 ]
Bottom
null

Dry Run Walkthrough

Input: Start with empty stack, push 1, push 2, push 3, then pop one item

Goal: Show how items are added and removed following LIFO order

Step 1: Push 1 onto empty stack

Top ↑
[ 1 ]
Bottom
null

Why: First item becomes the top of the stack

Step 2: Push 2 onto stack

Top ↑
[ 2 ]
[ 1 ]
Bottom
null

Why: New item goes on top, previous top moves down

Step 3: Push 3 onto stack

Top ↑
[ 3 ]
[ 2 ]
[ 1 ]
Bottom
null

Why: Newest item is always on top

Step 4: Pop top item (3) from stack

Top ↑
[ 2 ]
[ 1 ]
Bottom
null

Why: Remove the last added item first, following LIFO

Result:

Top ↑
[ 2 ]
[ 1 ]
Bottom
null
Popped item: 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#define MAX 100

// Stack structure using array
typedef struct {
    int items[MAX];
    int top;
} Stack;

// Initialize stack
void init(Stack *s) {
    s->top = -1; // empty stack
}

// Check if stack is empty
int isEmpty(Stack *s) {
    return s->top == -1;
}

// Check if stack is full
int isFull(Stack *s) {
    return s->top == MAX - 1;
}

// Push item onto stack
void push(Stack *s, int item) {
    if (isFull(s)) {
        printf("Stack overflow\n");
        return;
    }
    s->items[++(s->top)] = item; // add item and move top up
}

// Pop item from stack
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack underflow\n");
        return -1; // error value
    }
    return s->items[(s->top)--]; // return top item and move top down
}

// Print stack from top to bottom
void printStack(Stack *s) {
    printf("Top ↑\n");
    for (int i = s->top; i >= 0; i--) {
        printf("[ %d ]\n", s->items[i]);
    }
    printf("Bottom\nnull\n");
}

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

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

    printStack(&s);

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

    printStack(&s);

    return 0;
}

s->items[++(s->top)] = item; // add item and move top up

push new item on top, increment top pointer

return s->items[(s->top)--]; // return top item and move top down

pop top item, decrement top pointer

Output

Top ↑

[ 3 ]

[ 2 ]

[ 1 ]

Bottom

null

Popped item: 3

Top ↑

[ 2 ]

[ 1 ]

Bottom

null

Complexity Analysis

Time: O(1) for push and pop because operations only change the top pointer and one element

Space: O(n) where n is the max stack size because we store all elements in an array

vs Alternative: Compared to linked list stack, array stack is simpler and faster but fixed size; linked list stack can grow dynamically but uses extra memory for pointers

Edge Cases

Pop from empty stack

Prints 'Stack underflow' and returns -1 to indicate error

DSA C

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

Push to full stack

Prints 'Stack overflow' and does not add item

DSA C

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

When to Use This Pattern

When you see a problem requiring last added item to be accessed or removed first, use the stack pattern because it follows Last In, First Out order.

Common Mistakes

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

Mistake: Incrementing top after adding item instead of before causes wrong indexing
Fix: Increment top before assigning new item to keep top pointing to last added

Summary

A stack stores items so the last one added is the first one removed (LIFO).

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

The key is to always add and remove items from the top only.