Stack Concept and LIFO Principle in DSA Rust

Mental Model

A stack is a collection where the last item added is the first one removed. It works like a pile where you only add or remove from the top.

Analogy: Imagine a stack of plates in a cafeteria. You put a new plate on top and take plates from the top only. The last plate you put is the first you take.

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 last-in-first-out order

Step 1: Push 1 onto empty stack

Top -> [ 1 ] -> null

Why: We add the first item at the top

Step 2: Push 2 onto stack

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

Why: New item goes on top, previous items move down

Step 3: Push 3 onto stack

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

Why: Keep adding on top, last pushed is on top

Step 4: Pop top item from stack

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

Why: Remove the last item added, following LIFO

Result:

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

Annotated Code

DSA Rust

struct Stack {
    elements: Vec<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack { elements: Vec::new() }
    }

    fn push(&mut self, value: i32) {
        self.elements.push(value); // add item on top
    }

    fn pop(&mut self) -> Option<i32> {
        self.elements.pop() // remove and return top item
    }

    fn print(&self) {
        print!("Top -> ");
        for &item in self.elements.iter().rev() {
            print!("[ {} ] -> ", item);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.print();
    if let Some(popped) = stack.pop() {
        println!("Popped value: {}", popped);
    }
    stack.print();
}

self.elements.push(value); // add item on top

push new item on top of stack

self.elements.pop() // remove and return top item

pop top item following LIFO

for &item in self.elements.iter().rev() { print!("[ {} ] -> ", item); }

print stack from top to bottom

Output

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

Popped value: 3

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

Complexity Analysis

Time: O(1) for push and pop because we add or remove only from the top

Space: O(n) because we store n elements in the stack

vs Alternative: Compared to a queue, stack operations are simpler since they only happen at one end, making push/pop faster and easier to manage

Edge Cases

Pop from empty stack

Returns None safely without error

DSA Rust

self.elements.pop() // remove and return top item

When to Use This Pattern

When you see a problem needing last-in-first-out order, like undo actions or backtracking, reach for the stack pattern because it naturally supports this order.

Common Mistakes

Mistake: Trying to pop from an empty stack without checking
Fix: Use Option type to safely handle empty stack pop

Summary

Stack stores items so the last added is the first removed.

Use stack when you need to reverse order or track recent actions.

Remember: only add or remove from the top, like a stack of plates.

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 the first to be removed

B. Last 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 added to the stack is the first one to be taken out.

2. Step 2: Match with options

   Last In, First Out - the last element added is the first to be removed correctly states "Last In, First Out" which matches the LIFO principle.

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 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 Rust syntax to push an element 10 onto a stack named stack?

easy

A. stack.push(10);

B. stack.add(10);

C. stack.insert(10);

D. stack.append(10);

Solution

1. Step 1: Recall Rust Vec stack push method

   In Rust, a stack is often implemented using a Vec, and pushing uses the push method.

2. Step 2: Check method names

   Only push is the correct method to add an element at the end of a Vec.

3. Final Answer:

   stack.push(10); -> Option A

4. Quick Check:

   Rust Vec push method = push() [OK]

Hint: Use push() to add elements to Rust Vec stack [OK]

Common Mistakes:

• Using add() which does not exist
• Using insert() without index
• Using append() which expects another collection

3. What will be the output of the following Rust code?

let mut stack = Vec::new();
stack.push(5);
stack.push(10);
let x = stack.pop();
println!("{:?}", x);

medium

A. Some(10)

B. 10

C. None

D. Some(5)

Solution

1. Step 1: Trace stack push operations

   Stack after pushes: [5, 10] (10 is last pushed)

2. Step 2: Trace pop operation

   Pop removes last element 10 and returns Some(10) because pop returns Option type.

3. Final Answer:

   Some(10) -> Option A

4. Quick Check:

   pop() returns Some(last element) = Some(10) [OK]

Hint: pop() returns Some(last pushed) or None if empty [OK]

Common Mistakes:

• Thinking pop returns raw value, not Option
• Confusing order of elements popped
• Expecting None instead of Some value

4. Identify the error in this Rust code snippet that tries to pop from an empty stack:

let mut stack: Vec<i32> = Vec::new();
let value = stack.pop().unwrap();
println!("{}", value);

medium

A. pop() method does not exist on Vec

B. Calling unwrap() on None causes panic

C. stack is not mutable

D. println! macro syntax is incorrect

Solution

1. Step 1: Understand pop() on empty Vec

   pop() returns None if Vec is empty.

2. Step 2: Effect of unwrap() on None

   Calling unwrap() on None causes a runtime panic (crash).

3. Final Answer:

   Calling unwrap() on None causes panic -> Option B

4. Quick Check:

   unwrap() on None = panic [OK]

Hint: Never unwrap pop() without checking if stack is empty [OK]

Common Mistakes:

• Assuming pop() always returns Some
• Ignoring mutability requirement
• Misreading println! syntax

5. Given a stack implemented as a Rust Vec, what will be the content of the stack after the following sequence of operations?

Operations:
1) push(1)
2) push(2)
3) pop()
4) push(3)
5) push(2)
6) pop()

hard

A. Stack after operations is [1, 2]

B. Stack after operations is [1, 2, 3]

C. Stack after operations is [1, 3, 2]

D. Stack after operations is [1, 3]

Solution

1. Step 1: Simulate each operation step-by-step

   Start: [] 1) push(1) -> [1] 2) push(2) -> [1, 2] 3) pop() removes 2 -> [1] 4) push(3) -> [1, 3] 5) push(2) -> [1, 3, 2] 6) pop() removes 2 -> [1, 3]

2. Step 2: Compare final stack with options

   Final stack is [1, 3], which matches Stack after operations is [1, 3].

3. Final Answer:

   Stack after operations is [1, 3] -> Option D

4. Quick Check:

   Trace pushes and pops carefully [OK]

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

Common Mistakes:

• Ignoring pop removes last pushed element
• Mixing order of push and pop
• Assuming pop removes first element