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

Stack Concept and LIFO Principle

📖 Scenario: Imagine you have a stack of books on your desk. You can only add or remove the top book. This is called Last In, First Out (LIFO). We will build a simple stack in Rust to understand this.

🎯 Goal: Create a stack using a Rust vector, add books to it, remove the top book, and print the stack to see the LIFO behavior.

📋 What You'll Learn

Create a vector called stack with initial books: "Book1", "Book2", "Book3"

Create a variable called new_book with the value "Book4"

Push new_book onto stack

Pop the top book from stack

Print the final stack showing the remaining books

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, browser history, and managing tasks where the last added item is handled first.

💼 Career

Understanding stacks helps in software development roles involving data management, algorithm design, and system programming.

1

Create the initial stack

Create a vector called stack with these exact books: "Book1", "Book2", "Book3"

DSA Rust

# Create a vector called stack with "Book1", "Book2", "Book3"
# Your code here

Hint

Use vec!["Book1", "Book2", "Book3"] to create the vector.

2

Add a new book to the stack

Create a variable called new_book with the value "Book4" and push it onto the stack vector

DSA Rust

fn main() {
    let mut stack = vec!["Book1", "Book2", "Book3"];
    
    // Create new_book and push it onto stack
    # Your code here
}

Hint

Use let new_book = "Book4"; and stack.push(new_book);

3

Remove the top book from the stack

Pop the top book from the stack vector using stack.pop()

DSA Rust

fn main() {
    let mut stack = vec!["Book1", "Book2", "Book3"];
    let new_book = "Book4";
    stack.push(new_book);
    
    // Remove the top book from stack
    # Your code here
}

Hint

Use stack.pop(); to remove the last item.

4

Print the final stack

Print the stack vector using println!("{:?}", stack) to show the remaining books

DSA Rust

fn main() {
    let mut stack = vec!["Book1", "Book2", "Book3"];
    let new_book = "Book4";
    stack.push(new_book);
    stack.pop();
    
    // Print the stack
    # Your code here
}

Hint

Use println!("{:?}", stack); to print the vector.

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