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 new plates on top and take plates from the top only. The last plate you put is the first you remove.

Top -> [ 3 ]
        [ 2 ]
        [ 1 ]
        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 ] -> null

Why: We add the first item; it becomes the top

Step 2: Push 2 onto stack

Top -> [ 2 ] -> [ 1 ] -> null

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

Step 3: Push 3 onto stack

Top -> [ 3 ] -> [ 2 ] -> [ 1 ] -> null

Why: Again, new item on top, keeping order

Step 4: Pop top item from stack

Top -> [ 2 ] -> [ 1 ] -> null

Why: Remove the last added item, following LIFO

Result:

Top -> [ 2 ] -> [ 1 ] -> null
Popped item: 3

Annotated Code

DSA C#

using System;

public class StackNode
{
    public int Data;
    public StackNode Next;
    public StackNode(int data)
    {
        Data = data;
        Next = null;
    }
}

public class Stack
{
    private StackNode top;

    public Stack()
    {
        top = null;
    }

    public void Push(int data)
    {
        StackNode newNode = new StackNode(data);
        newNode.Next = top; // link new node to current top
        top = newNode; // update top to new node
    }

    public int Pop()
    {
        if (top == null) throw new InvalidOperationException("Stack is empty");
        int value = top.Data; // get data from top
        top = top.Next; // move top down one node
        return value;
    }

    public override string ToString()
    {
        StackNode current = top;
        string result = "Top -> ";
        while (current != null)
        {
            result += "[ " + current.Data + " ] -> ";
            current = current.Next;
        }
        result += "null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        Stack stack = new Stack();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        Console.WriteLine(stack.ToString());
        int popped = stack.Pop();
        Console.WriteLine(stack.ToString());
        Console.WriteLine("Popped item: " + popped);
    }
}

newNode.Next = top; // link new node to current top

connect new node to current top to keep stack order

top = newNode; // update top to new node

update top pointer to new node -- new item is now on top

int value = top.Data; // get data from top

store data from top node before removal

top = top.Next; // move top down one node

remove top node by moving top pointer down

Output

Top -> [ 3 ] -> [ 2 ] -> [ 1 ] -> null

Top -> [ 2 ] -> [ 1 ] -> null

Popped item: 3

Complexity Analysis

Time: O(1) because push and pop only change the top pointer without traversing

Space: O(n) because each push adds one node to the stack

vs Alternative: Compared to arrays where resizing or shifting can be costly, linked stack operations are always fast and constant time

Edge Cases

Pop from empty stack

Throws an exception to prevent invalid removal

DSA C#

if (top == null) throw new InvalidOperationException("Stack is empty");

When to Use This Pattern

When you see a problem needing last added item accessed first, think stack and LIFO to manage order efficiently.

Common Mistakes

Mistake: Forgetting to update the top pointer after push or pop
Fix: Always assign top to the new node after push and to top.Next after pop

Summary

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

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

The key is always adding and removing from the top only.

Practice

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

easy

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

B. First In, First Out - the first element added is the first to be removed

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

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

Solution

1. Step 1: Understand LIFO meaning

   LIFO means the last item you put in is the first one you take out.

2. Step 2: Apply to stack behavior

   Stacks follow LIFO, so the last pushed element is popped first.

3. Final Answer:

   Last In, First Out - the last element added is the first to be removed -> Option C

4. Quick Check:

   LIFO = Last In, First Out [OK]

Hint: Remember stack is like a stack of plates, last added removed first [OK]

Common Mistakes:

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

2. Which of the following is the correct way to push an integer 10 onto a stack named myStack in C#?

easy

A. myStack.Enqueue(10);

B. myStack.Push(10);

C. myStack.Insert(10);

D. myStack.Add(10);

Solution

1. Step 1: Recall stack push method

   In C#, the method to add an element to a stack is Push.

2. Step 2: Check method names

   Add and Insert are not stack methods; Enqueue is for queues.

3. Final Answer:

   myStack.Push(10); -> Option B

4. Quick Check:

   Push() adds element to stack [OK]

Hint: Use Push() to add elements to stack in C# [OK]

Common Mistakes:

• Using Add() or Insert() which are not stack methods
• Confusing stack with queue methods like Enqueue()
• Forgetting parentheses in method call

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

Stack<int> stack = new Stack<int>();
stack.Push(5);
stack.Push(10);
stack.Push(15);
Console.WriteLine(stack.Pop());
Console.WriteLine(stack.Peek());

medium

A. 15
10

B. 5
10

C. 10
15

D. 15
15

Solution

1. Step 1: Trace Push operations

   Elements pushed in order: 5 (bottom), 10, 15 (top).

2. Step 2: Trace Pop and Peek

   Pop removes and returns 15 (top). Peek returns new top 10 without removing.

3. Final Answer:

   15\n10 -> Option A

4. Quick Check:

   Pop() = 15, Peek() = 10 [OK]

Hint: Pop returns top and removes it; Peek returns top without removing [OK]

Common Mistakes:

• Mixing Pop and Peek outputs
• Assuming Pop does not remove element
• Confusing order of pushed elements

4. Identify the error in the following C# code snippet using a stack:

Stack<string> stack = new Stack<string>();
stack.Push("apple");
stack.Push("banana");
string fruit = stack.Pop();
string topFruit = stack.Top();

medium

A. Stack must be initialized with capacity

B. Pop() cannot be assigned to a string variable

C. Push() method requires two arguments

D. Stack does not have a method named Top()

Solution

1. Step 1: Check stack methods

   Stack in C# has Peek() to view top element, not Top().

2. Step 2: Validate other statements

   Pop() returns string, Push() takes one argument, no capacity needed.

3. Final Answer:

   Stack does not have a method named Top() -> Option D

4. Quick Check:

   Use Peek() to view top element [OK]

Hint: Use Peek() to see top element, not Top() [OK]

Common Mistakes:

• Using Top() instead of Peek()
• Thinking Pop() returns void
• Assuming Push() needs capacity argument

5. Given a stack with elements pushed in this order: 1, 2, 3, 4, 5. You pop two elements, then push 6 and 7. What is the order of elements if you pop all remaining elements one by one?

hard

A. 7, 6, 3, 2, 1

B. 3, 2, 6, 7

C. 5, 4, 6, 7

D. 7, 6, 3, 2

Solution

1. Step 1: Track initial pushes

   Stack after pushes: bottom 1,2,3,4,5 top.

2. Step 2: Pop two elements

   Pop removes 5 then 4; stack now 1,2,3 (bottom to top).

3. Step 3: Push 6 and 7

   Stack now: 1,2,3,6,7 (bottom to top).

4. Step 4: Pop all remaining elements

   Pop order (first popped to last): 7,6,3,2,1.

5. Final Answer:

   7, 6, 3, 2, 1 -> Option A

6. Quick Check:

   Pop order after operations = 7,6,3,2,1 [OK]

Hint: Pop removes last pushed; track pushes and pops stepwise [OK]

Common Mistakes:

• Forgetting to remove popped elements
• Mixing push and pop order
• Ignoring elements still in stack after operations