Stack Concept and LIFO Principle in DSA C - Build from Scratch

Stack Concept and LIFO Principle

📖 Scenario: Imagine you have a stack of plates in your kitchen. You can only add a plate on top or remove the top plate. This is called Last In, First Out (LIFO) principle.We will create a simple stack using an array in C to understand how this works.

🎯 Goal: Build a simple stack in C that can hold 5 integer plates, add plates to the stack, and then remove the top plate to see the LIFO principle in action.

📋 What You'll Learn

Create an integer array called stack with size 5

Create an integer variable called top initialized to -1 to track the top of the stack

Write code to push three plates with values 10, 20, and 30 onto the stack

Write code to pop the top plate from the stack

Print the stack contents after the pop operation

💡 Why This Matters

🌍 Real World

Stacks are used in many places like undo features in apps, browser history, and managing function calls in programs.

💼 Career

Understanding stacks and LIFO is essential for software developers, especially when working with recursion, parsing, and memory management.

1

Create the stack array and top variable

Create an integer array called stack with size 5 and an integer variable called top initialized to -1.

DSA C

int stack[5];
int top = -1;
// Your code here

Hint

The stack array holds the plates. The top variable shows the index of the top plate. Start with -1 because the stack is empty.

2

Push three plates onto the stack

Add code to push three plates with values 10, 20, and 30 onto the stack by incrementing top and assigning the values to stack[top].

DSA C

int stack[5];
int top = -1;
// Push 10
// Push 20
// Push 30

Hint

To push a plate, increase top by 1, then put the plate value at stack[top].

3

Pop the top plate from the stack

Add code to pop the top plate by printing stack[top] and then decrementing top by 1.

DSA C

int stack[5];
int top = -1;
top++;
stack[top] = 10;
top++;
stack[top] = 20;
top++;
stack[top] = 30;
// Pop the top plate

Hint

To pop, print the top plate value, then decrease top by 1 to remove it from the stack.

4

Print the stack contents after pop

Use a for loop with variable i from 0 to top to print each plate value in stack[i] separated by spaces.

DSA C

int stack[5];
int top = -1;
top++;
stack[top] = 10;
top++;
stack[top] = 20;
top++;
stack[top] = 30;
printf("Popped plate: %d\n", stack[top]);
top--;
// Print stack contents after pop

Hint

Loop from 0 to top and print each plate value with a space. This shows the stack after popping the top plate.

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