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.

Practice

1. What does the LIFO principle mean in the context of a stack?

easy

A. First In, First Out - the first element added is removed first

B. Last In, First Out - the last element added is removed first

C. Last In, First Out - the first element added is removed first

D. First In, Last Out - the first element added is removed last

Solution

1. Step 1: Understand LIFO meaning

   LIFO means the last element added to the stack is the first one to be removed.

2. Step 2: Match with options

   Last In, First Out - the last element added is removed first correctly describes this behavior as "Last In, First Out".

3. Final Answer:

   Last In, First Out - the last element added is removed first -> Option B

4. Quick Check:

   LIFO = Last In, First Out [OK]

Hint: Remember stack removes newest item first [OK]

Common Mistakes:

• Confusing LIFO with FIFO
• Thinking first added is removed first
• Mixing up order of insertion and removal

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

easy

A. s.push = x;

B. s.push(x);

C. push(x, s);

D. push(s, x);

Solution

1. Step 1: Identify correct function call syntax in C

   In C, stack operations are usually functions like push(stack, element).

2. Step 2: Check options

   push(s, x); uses push(s, x); which is the correct syntax for pushing x onto stack s.

3. Final Answer:

   push(s, x); -> Option D

4. Quick Check:

   Function call push(stack, element) = push(s, x) [OK]

Hint: In C, function calls have parameters in parentheses [OK]

Common Mistakes:

• Using object.method() syntax (not C style)
• Swapping parameter order
• Assigning instead of calling function

3. Consider the following C code using a stack with push and pop operations:

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

What is the value returned by the last pop operation?

medium

A. 30

B. 20

C. 10

D. Error - stack empty

Solution

1. Step 1: Trace stack after each operation

   After push 10: stack = [10]
   After push 20: stack = [10, 20]
   pop(): removes 20, stack = [10]
   push 30: stack = [10, 30]
   pop(): removes 30

2. Step 2: Identify last pop value

   The last pop removes 30, so it returns 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Last pop returns last pushed element 30 [OK]

Hint: Last pushed is first popped, track stack top [OK]

Common Mistakes:

• Assuming FIFO order
• Forgetting previous pop removed top
• Mixing values pushed and popped

4. The following C code snippet is intended to pop an element from a stack 's'. What is the error?

int pop(Stack *s) {
    if (s->top == -1) {
        return -1;
    }
    return s->items[s->top++];
}

medium

A. The function returns -1 on empty stack

B. The stack pointer is not checked for NULL

C. The top index is incremented instead of decremented

D. The return type should be void

Solution

1. Step 1: Analyze pop operation logic

   Pop should return the top element and then decrease the top index.

2. Step 2: Identify error in index update

   Code uses s->top++ which increases top, wrong for pop. It should be s->top-- to remove top element.

3. Final Answer:

   The top index is incremented instead of decremented -> Option C

4. Quick Check:

   Pop decreases top index, not increases [OK]

Hint: Pop must decrease top index after returning element [OK]

Common Mistakes:

• Using post-increment instead of decrement
• Ignoring empty stack check
• Wrong return type for pop

5. You have a stack initially empty. You perform these operations:

push(s, 5);
push(s, 10);
pop(s);
push(s, 15);
push(s, 20);
pop(s);
pop(s);

What is the final state of the stack (from top to bottom)?

hard

A. 5

B. 10 -> 5

C. 15 -> 5

D. Empty stack

Solution

1. Step 1: Trace stack after each operation

   push 5: stack = [5]
   push 10: stack = [5, 10]
   pop: removes 10, stack = [5]
   push 15: stack = [5, 15]
   push 20: stack = [5, 15, 20]
   pop: removes 20, stack = [5, 15]
   pop: removes 15, stack = [5]

2. Step 2: Determine final stack state

   After all operations, stack has only 5 left at bottom and top.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Only 5 remains after pops [OK]

Hint: Track pushes and pops carefully to find final stack [OK]

Common Mistakes:

• Forgetting to remove top on pop
• Mixing order of elements
• Assuming stack is empty after pops