Stack Implementation Using Array in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust stack push/pop sequence?

Consider a stack implemented using a fixed-size array in Rust. What will be printed after the following operations?

DSA Rust

struct Stack {
    data: [i32; 3],
    top: usize,
}

impl Stack {
    fn new() -> Self {
        Stack { data: [0; 3], top: 0 }
    }

    fn push(&mut self, val: i32) {
        if self.top < 3 {
            self.data[self.top] = val;
            self.top += 1;
        }
    }

    fn pop(&mut self) -> Option<i32> {
        if self.top == 0 {
            None
        } else {
            self.top -= 1;
            Some(self.data[self.top])
        }
    }

    fn print_stack(&self) {
        for i in (0..self.top).rev() {
            print!("{} -> ", self.data[i]);
        }
        println!("null");
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(10);
    stack.push(20);
    stack.push(30);
    stack.pop();
    stack.push(40);
    stack.print_stack();
}

A 20 -> 10 -> null

B 30 -> 20 -> 10 -> null

C 40 -> 20 -> 10 -> null

D 40 -> 30 -> 20 -> 10 -> null

💡 Hint

Remember that pop removes the top element and push adds on top.

The stack starts empty. We push 10, 20, 30 in order. The stack is now 30 (top), 20, 10 (bottom). Then pop removes 30. Then push 40 adds 40 on top. So the stack is 40 (top), 20, 10 (bottom). Printing from top to bottom gives 40 -> 20 -> 10 -> null.

❓ Predict Output

intermediate

What error occurs when pushing beyond stack capacity?

Given the same stack implementation, what happens if we push 4 elements into a stack of size 3?

DSA Rust

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4); // pushing beyond capacity
    stack.print_stack();
}

A Compilation error due to array size mismatch

B Runtime panic due to index out of bounds

C Prints: 4 -> 3 -> 2 -> 1 -> null

D Prints: 3 -> 2 -> 1 -> null

💡 Hint

Check the push method's condition for adding elements.

The push method only adds elements if top < 3. The fourth push is ignored because the stack is full. So the stack remains with 3 elements: 3 (top), 2, 1 (bottom). Printing shows 3 -> 2 -> 1 -> null.

🔧 Debug

advanced

Identify the bug causing incorrect pop behavior

This Rust stack implementation sometimes returns wrong values on pop. What is the bug?

DSA Rust

struct Stack {
    data: [i32; 3],
    top: usize,
}

impl Stack {
    fn new() -> Self {
        Stack { data: [0; 3], top: 0 }
    }

    fn push(&mut self, val: i32) {
        if self.top <= 3 {
            self.data[self.top] = val;
            self.top += 1;
        }
    }

    fn pop(&mut self) -> Option<i32> {
        if self.top == 0 {
            None
        } else {
            let val = self.data[self.top - 1];
            self.top -= 1;
            Some(val)
        }
    }
}

A In pop, accessing data at self.top causes out-of-bounds error

B pop should increment top instead of decrement

C top should be usize, not i32

D In push, condition should be < instead of <= to avoid overflow

💡 Hint

Check the index used to access data in pop before decrementing top.

In pop, self.data[self.top] accesses an index equal to top, which is out of bounds since top points to next free slot. The correct index is self.top - 1 before decrementing top.

🧠 Conceptual

advanced

Why use an array for stack implementation?

Which is the main advantage of using a fixed-size array to implement a stack compared to a linked list?

A Arrays use less memory than linked lists because they store pointers

B Faster push and pop operations due to contiguous memory and cache friendliness

C Dynamic resizing is easier with arrays than linked lists

D Arrays allow insertion at any position efficiently

💡 Hint

Think about memory layout and speed of access.

Arrays store elements contiguously in memory, which makes push and pop operations faster due to better cache usage. Linked lists require extra memory for pointers and have non-contiguous memory, which can slow access.

🚀 Application

expert

What is the stack content after this sequence of operations?

Given a stack of size 4 implemented using an array, what is the printed stack after these operations?

DSA Rust

let mut stack = Stack::new();
stack.push(5);
stack.push(10);
stack.pop();
stack.push(15);
stack.push(20);
stack.pop();
stack.push(25);
stack.print_stack();

A 25 -> 15 -> 5 -> null

B 20 -> 15 -> 5 -> null

C 25 -> 20 -> 15 -> 5 -> null

D 15 -> 5 -> null

💡 Hint

Track each push and pop carefully, updating the stack top.

Operations step-by-step:
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]
push 25: stack = [5,15,25]
Printed top to bottom: 25 -> 15 -> 5 -> null

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