Stack Implementation Using Array in DSA Rust

Mental Model

A stack is a collection where you add and remove items only from the top, like a stack of plates.

Analogy: Imagine a stack of plates in your kitchen. You can only add a new plate on top or take the top plate off. You cannot take a plate from the middle or bottom without disturbing the top ones.

Top -> [item3] -> [item2] -> [item1] -> null
Index ->    2        1        0

Dry Run Walkthrough

Input: Create an empty stack with capacity 3, then push 10, push 20, pop, push 30

Goal: Show how the stack changes after each push and pop operation

Step 1: Initialize empty stack with capacity 3

Stack: [] (empty), top = -1

Why: We start with no items and top at -1 to indicate empty

Step 2: Push 10 onto stack

Stack: [10], top = 0

Why: Add first item at index 0 and update top to 0

Step 3: Push 20 onto stack

Stack: [10, 20], top = 1

Why: Add second item at index 1 and update top to 1

Step 4: Pop top item (20) from stack

Stack: [10], top = 0

Why: Remove item at top index 1 and move top back to 0

Step 5: Push 30 onto stack

Stack: [10, 30], top = 1

Why: Add new item at index 1 and update top to 1

Result:

Stack: [10, 30], top = 1

Annotated Code

DSA Rust

struct Stack {
    data: Vec<i32>,
    capacity: usize,
    top: isize,
}

impl Stack {
    fn new(capacity: usize) -> Self {
        Stack {
            data: Vec::with_capacity(capacity),
            capacity,
            top: -1,
        }
    }

    fn push(&mut self, value: i32) -> Result<(), &str> {
        if self.top + 1 == self.capacity as isize {
            return Err("Stack overflow");
        }
        self.top += 1;
        if self.data.len() > self.top as usize {
            self.data[self.top as usize] = value;
        } else {
            self.data.push(value);
        }
        Ok(())
    }

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

    fn print_stack(&self) {
        if self.top == -1 {
            println!("Stack is empty");
            return;
        }
        for i in (0..=self.top as usize).rev() {
            print!("{}", self.data[i]);
            if i != 0 {
                print!(" -> ");
            }
        }
        println!(" -> null");
    }
}

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

if self.top + 1 == self.capacity as isize { return Err("Stack overflow"); }

Check if stack is full before pushing

self.top += 1;

Move top pointer up to next free position

if self.data.len() > self.top as usize { self.data[self.top as usize] = value; } else { self.data.push(value); }

Add value at top index, either overwrite or push new

if self.top == -1 { return None; }

Check if stack is empty before popping

let val = self.data[self.top as usize]; self.top -= 1; Some(val)

Return top value and move top pointer down

for i in (0..=self.top as usize).rev() { print!("{}", self.data[i]); if i != 0 { print!(" -> "); } }

Print stack from top to bottom

Output

30 -> 10 -> null

Complexity Analysis

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

Space: O(n) where n is capacity because we allocate fixed space for the stack

vs Alternative: Compared to linked list stack, array stack uses fixed space but has faster access and less overhead

Edge Cases

Push on full stack

Returns error 'Stack overflow' and does not add item

DSA Rust

if self.top + 1 == self.capacity as isize { return Err("Stack overflow"); }

Pop from empty stack

Returns None indicating no item to pop

DSA Rust

if self.top == -1 { return None; }

Push after pop

Allows pushing new item at the freed top position

DSA Rust

self.top += 1;

When to Use This Pattern

When you need last-in-first-out order with fast add/remove at one end, use stack with array for simple and fast implementation.

Common Mistakes

Mistake: Not checking for stack overflow before pushing
Fix: Add condition to check if top reached capacity before adding new item

Mistake: Not checking for empty stack before popping
Fix: Return None or error if top is -1 before popping

Mistake: Printing stack from bottom to top instead of top to bottom
Fix: Print elements starting from top index down to zero

Summary

Implements a stack using a fixed-size array with push and pop at the top.

Use when you want simple last-in-first-out behavior with fast operations.

Remember the top pointer moves up on push and down on pop, controlling the stack size.

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