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.

Practice

1. Why do we use a stack data structure in programming?

easy

A. To store data in random order

B. To keep track of function calls and return addresses

C. To sort numbers quickly

D. To store large amounts of data permanently

Solution

1. Step 1: Understand the purpose of a stack

   A stack stores data in a last-in, first-out order, which is perfect for tracking function calls and returns.

2. Step 2: Identify common uses of stack

   Stacks are mainly used to keep track of function calls, especially in recursion, where the last called function must finish first.

3. Final Answer:

   To keep track of function calls and return addresses -> Option B

4. Quick Check:

   Stack = function call tracking [OK]

Hint: Stack = last-in, first-out for function calls [OK]

Common Mistakes:

• Thinking stack stores data randomly
• Confusing stack with queue
• Assuming stack sorts data

2. Which of the following is the correct way to push an element onto a stack in C?

easy

A. stack[++top] = value;

B. stack[top] = value++;

C. stack[top++] = value;

D. stack[top--] = value;

Solution

1. Step 1: Understand stack push operation

   To push, we first increase the top index, then assign the value at that position.

2. Step 2: Check each option

   stack[++top] = value; increments top before assignment, which is correct. stack[top++] = value; assigns then increments, which may overwrite. stack[top] = value++; increments value, not top. stack[top--] = value; decrements top, which is wrong for push.

3. Final Answer:

   stack[++top] = value; -> Option A

4. Quick Check:

   Push = increment top then assign [OK]

Hint: Push means increment top first, then assign [OK]

Common Mistakes:

• Incrementing after assignment causes overwrite
• Decrementing top on push
• Incrementing value instead of top

3. What will be the output of the following C code snippet?

int stack[3];
int top = -1;
stack[++top] = 10;
stack[++top] = 20;
stack[++top] = 30;
printf("%d", stack[top]);

medium

A. 10

B. 20

C. 30

D. Runtime error

Solution

1. Step 1: Trace stack push operations

   Initially, top = -1. After first push, top=0, stack[0]=10. Second push: top=1, stack[1]=20. Third push: top=2, stack[2]=30.

2. Step 2: Check printed value

   printf prints stack[top], which is stack[2] = 30.

3. Final Answer:

   30 -> Option C

4. Quick Check:

   Last pushed value = 30 [OK]

Hint: Last pushed value is at stack[top] [OK]

Common Mistakes:

• Printing stack[0] instead of stack[top]
• Confusing top index after pushes
• Assuming runtime error without overflow

4. Identify the error in this stack pop function in C:

int pop(int stack[], int *top) {
    if (*top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[*top--];
}

medium

A. Incorrect decrement of top pointer

B. Missing check for stack overflow

C. Returning wrong stack element

D. No error, function is correct

Solution

1. Step 1: Understand pointer decrement in return statement

   The expression stack[*top--] uses post-decrement on *top, but *top-- decrements the pointer, not the value it points to.

2. Step 2: Correct way to decrement top value

   It should be stack[(*top)--] to decrement the value pointed by top after accessing stack.

3. Final Answer:

   Incorrect decrement of top pointer -> Option A

4. Quick Check:

   Use (*top)-- to decrement value, not pointer [OK]

Hint: Use (*top)-- to decrement value, not pointer [OK]

Common Mistakes:

• Using *top-- instead of (*top)--
• Ignoring pointer vs value decrement
• Not checking stack underflow

5. You want to reverse a string using a stack in C. Which approach correctly uses the stack to solve this problem?

hard

A. Use a queue instead of a stack to reverse the string

B. Push characters only if they are vowels, then pop to reverse

C. Pop characters first, then push them back to reverse

D. Push each character of the string onto the stack, then pop all characters to form the reversed string

Solution

1. Step 1: Understand stack reversal logic

   Pushing all characters onto the stack stores them in order. Popping them reverses the order due to last-in, first-out behavior.

2. Step 2: Evaluate options

   Push each character of the string onto the stack, then pop all characters to form the reversed string correctly pushes all characters then pops to reverse. Push characters only if they are vowels, then pop to reverse only pushes vowels, losing other characters. Pop characters first, then push them back to reverse pops before pushing, which is invalid. Use a queue instead of a stack to reverse the string suggests queue, which reverses order differently.

3. Final Answer:

   Push each character of the string onto the stack, then pop all characters to form the reversed string -> Option D

4. Quick Check:

   Stack reversal = push all, then pop all [OK]

Hint: Push all chars, then pop all to reverse [OK]

Common Mistakes:

• Pushing only some characters
• Popping before pushing
• Using queue instead of stack for reversal