Why Stack Implementation Using Array in DSA Rust?

The Big Idea

What if you could instantly access only the last thing you added, without any hassle or mistakes?

The Scenario

Imagine you have a pile of books on your desk. You want to add a new book on top or take the top book off quickly. Doing this by searching through the whole pile every time would be tiring and slow.

The Problem

If you try to find or remove a book from the middle of the pile manually, it takes a lot of time and you might drop or lose track of books. This is like managing data without a clear order, which is confusing and error-prone.

The Solution

A stack using an array works like that pile of books but with clear rules: you only add or remove the top book. This makes adding and removing very fast and simple, avoiding mistakes and confusion.

Before vs After

✗ Before

let mut books = vec!["Book1", "Book2", "Book3"];
// To remove top book manually
books.pop();
// To add a new book
books.push("Book4");

✓ After

struct Stack {
    items: Vec<String>,
}

impl Stack {
    fn push(&mut self, item: String) {
        self.items.push(item);
    }
    fn pop(&mut self) -> Option<String> {
        self.items.pop()
    }
}

What It Enables

It lets you manage data in a simple, fast way where only the last added item is accessed first, perfect for undo actions, expression evaluation, and more.

Real Life Example

Think of the undo button in a text editor: it remembers your last action and removes it first when you press undo, just like a stack.

Key Takeaways

Manual searching and removing is slow and error-prone.

Stack with array adds/removes only at the top, making it fast and simple.

This method is great for tasks needing last-in-first-out order.

Practice

1. What is the main purpose of using an array to implement a stack?

easy

A. To store elements in a first-in-first-out order

B. To store elements in a fixed-size, last-in-first-out order

C. To sort elements automatically

D. To allow random access to elements anywhere

Solution

1. Step 1: Understand stack behavior

   A stack stores elements in last-in-first-out order, meaning the last element added is the first to be removed.

2. Step 2: Role of array in stack

   An array provides a fixed-size container to hold elements in order, supporting push and pop operations at one end.

3. Final Answer:

   To store elements in a fixed-size, last-in-first-out order -> Option B

4. Quick Check:

   Stack = LIFO with fixed size [OK]

Hint: Stack means last-in-first-out, arrays hold fixed-size data [OK]

Common Mistakes:

• Confusing stack with queue (FIFO)
• Thinking array sorts elements automatically
• Assuming random access is main stack feature

2. Which of the following is the correct Rust syntax to declare a fixed-size array of 5 integers initialized to zero for stack storage?

easy

A. let stack: [i32; 5] = [0; 5];

B. let stack = [0, 5];

C. let stack: Vec<i32> = Vec::new();

D. let stack = (0; 5);

Solution

1. Step 1: Identify fixed-size array syntax in Rust

   Rust fixed-size arrays use syntax: let name: [type; size] = [initial_value; size];

2. Step 2: Match options to syntax

   let stack: [i32; 5] = [0; 5]; matches this exactly: let stack: [i32; 5] = [0; 5]; initializes 5 integers to zero.

3. Final Answer:

   let stack: [i32; 5] = [0; 5]; -> Option A

4. Quick Check:

   Fixed-size array syntax = let stack: [i32; 5] = [0; 5]; [OK]

Hint: Fixed-size array uses [type; size] and [value; size] syntax [OK]

Common Mistakes:

• Using Vec instead of fixed-size array
• Incorrect array initialization syntax
• Confusing tuple syntax with array

3. What will be the output of the following Rust code implementing a stack push operation?

let mut stack: [i32; 3] = [0; 3];
let mut top = -1;

// Push function
fn push(stack: &mut [i32; 3], top: &mut i32, value: i32) {
    if *top < 2 {
        *top += 1;
        stack[*top as usize] = value;
    }
}

push(&mut stack, &mut top, 10);
push(&mut stack, &mut top, 20);
println!("{:?}", stack);

medium

A. [20, 10, 0]

B. [0, 10, 20]

C. [10, 20, 0]

D. [0, 0, 0]

Solution

1. Step 1: Trace push calls and stack changes

   Initially, stack = [0, 0, 0], top = -1. First push: top becomes 0, stack[0] = 10 -> [10, 0, 0]. Second push: top becomes 1, stack[1] = 20 -> [10, 20, 0].

2. Step 2: Print final stack state

   Printing stack shows [10, 20, 0].

3. Final Answer:

   [10, 20, 0] -> Option C

4. Quick Check:

   Push adds at top index, stack = [10, 20, 0] [OK]

Hint: Track top index and update array at that position [OK]

Common Mistakes:

• Not updating top index before assignment
• Confusing array indices order
• Assuming push adds at end regardless of top

4. Identify the error in this Rust stack pop function and select the correct fix:

fn pop(stack: &[i32; 3], top: &mut i32) -> Option<i32> {
    if *top >= 0 {
        let val = stack[*top as usize];
        *top -= 1;
        Some(val)
    } else {
        None
    }
}

medium

A. Change stack parameter to mutable: &mut [i32; 3]

B. Remove top parameter and use global variable

C. Change return type to i32 instead of Option<i32>

D. No error, function is correct

Solution

1. Step 1: Analyze the pop function code

   The function takes an immutable reference to the stack (&[i32; 3]) and a mutable reference to top. It only reads from the stack at index *top and decrements top.

2. Step 2: Verify compilation and logic

   No writes to the stack array occur, so an immutable reference is sufficient and correct. The function handles empty stack with None and returns the popped value properly.

3. Final Answer:

   No error, function is correct -> Option D

4. Quick Check:

   Immutable stack reference OK for read-only access in pop [OK]

Hint: Pop reads stack immutably and mutates top separately; no stack mutation needed [OK]

Common Mistakes:

• Assuming stack must be mutable for pop operations
• Suggesting unnecessary global variables
• Incorrectly changing return type from Option<i32>

5. Given a fixed-size stack implemented using an array of size 4, which sequence of operations will cause a stack overflow error?

let mut stack: [i32; 4] = [0; 4];
let mut top = -1;

// Push function
fn push(stack: &mut [i32; 4], top: &mut i32, value: i32) {
    if *top < 3 {
        *top += 1;
        stack[*top as usize] = value;
    } else {
        println!("Stack Overflow");
    }
}

// Operations:
push(&mut stack, &mut top, 5);
push(&mut stack, &mut top, 10);
push(&mut stack, &mut top, 15);
push(&mut stack, &mut top, 20);
push(&mut stack, &mut top, 25);

hard

A. The last push call with value 25 causes overflow

B. The first push call with value 5 causes overflow

C. No overflow occurs with these operations

D. Overflow occurs at the third push call with value 15

Solution

1. Step 1: Understand stack size and top limit

   Stack size is 4, so top can go from -1 to 3 (indices 0 to 3).

2. Step 2: Trace push calls and top value

   Push 5: top=0 Push 10: top=1 Push 15: top=2 Push 20: top=3 Push 25: top=3 already, so condition *top < 3 fails, triggers overflow.

3. Final Answer:

   The last push call with value 25 causes overflow -> Option A

4. Quick Check:

   Stack size 4, 5th push overflows [OK]

Hint: Stack max index = size-1; pushing beyond causes overflow [OK]

Common Mistakes:

• Counting top starting at 0 instead of -1
• Assuming overflow at fewer pushes
• Ignoring condition check in push