Stack Implementation Using Array in DSA Rust - Build from Scratch

Stack Implementation Using Array

📖 Scenario: Imagine you are managing a stack of books. You can only add a book on top or remove the top book. This is how a stack works in programming, using an array to hold the books.

🎯 Goal: You will build a simple stack using an array in Rust. You will add items (push), remove items (pop), and see the current stack.

📋 What You'll Learn

Create an array to hold stack elements

Create a variable to track the top of the stack

Write a function to push elements onto the stack

Write a function to pop elements from the stack

Print the stack after operations

💡 Why This Matters

🌍 Real World

Stacks are used in undo features, browser history, and expression evaluation.

💼 Career

Understanding stack implementation helps in system programming and algorithm design.

1

Create the stack array and top index

Create a mutable array called stack with size 5 and type i32, initialized with zeros. Also create a mutable variable called top and set it to -1 to track the top of the stack.

DSA Rust

let mut stack: [i32; 5] = [0; 5];
let mut top: i32 = -1;
// Your code here

Hint

Use let mut stack: [i32; 5] = [0; 5]; to create the array and let mut top: i32 = -1; for the top index.

2

Write the push function

Add a function called push that takes a mutable reference to stack, a mutable reference to top, and an i32 value called item. Inside, increase top by 1 and assign item to stack[top as usize]. Assume the stack is not full.

DSA Rust

fn main() {
    let mut stack: [i32; 5] = [0; 5];
    let mut top: i32 = -1;
}

// Write the push function below
// Your code here

Hint

Define push with parameters stack, top, and item. Increase *top by 1 and assign item to stack[*top as usize].

3

Write the pop function

Add a function called pop that takes a mutable reference to top and returns an Option. If top is less than 0, return None. Otherwise, return Some of the current top index and then decrease top by 1.

DSA Rust

fn main() {
    let mut stack: [i32; 5] = [0; 5];
    let mut top: i32 = -1;
}

fn push(stack: &mut [i32; 5], top: &mut i32, item: i32) {
    *top += 1;
    stack[*top as usize] = item;
}

// Write the pop function below
// Your code here

Hint

Define pop with parameter top. Return None if *top < 0. Otherwise, save *top in a variable, decrease *top by 1, and return Some of the saved value.

4

Push and pop items, then print the stack

In main, push the values 10, 20, and 30 onto the stack using push. Then pop one item using pop. Finally, print the current stack elements from index 0 to top inclusive, separated by spaces.

DSA Rust

fn main() {
    let mut stack: [i32; 5] = [0; 5];
    let mut top: i32 = -1;

    // Push 10, 20, 30
    // Pop one item
    // Print stack elements from 0 to top
    // Your code here
}

fn push(stack: &mut [i32; 5], top: &mut i32, item: i32) {
    *top += 1;
    stack[*top as usize] = item;
}

fn pop(top: &mut i32) -> Option {
    if *top < 0 {
        None
    } else {
        let popped = *top;
        *top -= 1;
        Some(popped)
    }
}

Hint

Call push three times with 10, 20, 30. Call pop once. Then print elements from 0 to top with spaces.

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