Stack Implementation Using Array in DSA Rust - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Check if stack is full?

Yes→Cannot push, stack overflow

No↓

Add element at top index

↓

Increment top pointer

↓

Push done

↓

Check if stack is empty?

Yes→Cannot pop, stack underflow

No↓

Return element at top

↓

Decrement top pointer

↓

Pop done

↓

End

The stack uses an array and a top pointer. Push adds element at top if not full. Pop removes element from top if not empty.

Execution Sample

DSA Rust

let mut stack = Vec::new();
stack.push(10);
stack.push(20);
let x = stack.pop();
println!("{:?}", stack);

This code pushes 10 and 20 onto the stack, then pops the top element, and prints the remaining stack.

Execution Table

Step	Operation	Top Index	Array State	Pointer Changes	Visual State
1	Initialize stack	-1	[]	top = -1	Empty stack: []
2	Push 10	0	[10]	top: -1 -> 0	10 -> null
3	Push 20	1	[10, 20]	top: 0 -> 1	10 -> 20 -> null
4	Pop	0	[10, 20]	top: 1 -> 0	10 -> null (20 removed)
5	Print stack	0	[10, 20]	top: 0	10 -> null
6	Pop	-1	[10, 20]	top: 0 -> -1	Empty stack: []
7	Pop (underflow)	-1	[10, 20]	top: -1	Cannot pop, stack underflow
8	Push 30	0	[30, 20]	top: -1 -> 0	30 -> null

💡 Execution stops after stack underflow is detected at step 7.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
top	-1	-1	0	1	0	0	-1	-1	0
stack array	[]	[]	[10]	[10, 20]	[10, 20]	[10, 20]	[10, 20]	[10, 20]	[30, 20]

Key Moments - 3 Insights

Why does the top index start at -1 instead of 0?

The top index is -1 initially to indicate the stack is empty. When we push the first element, top moves to 0 (step 2 in execution_table). This helps easily check if stack is empty (top == -1).

Why does popping not remove the element from the array physically?

Popping just moves the top pointer down (step 4 and 6). The element stays in the array but is considered outside the stack. This is efficient and common in array-based stacks.

What happens when we try to pop from an empty stack?

At step 7, top is -1, so popping is not allowed. This is called stack underflow, and the operation is stopped to avoid errors.

Visual Quiz - 3 Questions

Look at the execution_table, what is the top index after pushing 20?

A 1

B 0

C -1

D 2

💡 Hint

Check step 3 in execution_table under 'Top Index'

At which step does the stack become empty again after popping?

A Step 4

B Step 6

C Step 7

D Step 5

💡 Hint

Look at 'Top Index' and 'Visual State' columns in execution_table

If we push 40 after step 7, what will be the new top index?

A 0

B 1

C -1

D 2

💡 Hint

After underflow at step 7, top is -1, so pushing moves it to 0 (see step 8)

Concept Snapshot

Stack using array:
- Use an array and a top pointer (start at -1)
- Push: increment top, add element at top
- Pop: remove element at top, decrement top
- Check overflow (top == max) before push
- Check underflow (top == -1) before pop

Full Transcript

A stack is a data structure where elements are added and removed from the top only. We use an array and a top pointer starting at -1 to track the top element. When pushing, we increase top by one and place the new element there. When popping, we remove the element at top and decrease top by one. If top is -1, the stack is empty and pop is not allowed (underflow). If top reaches the array's max size, push is not allowed (overflow). The execution table shows step-by-step how the array and top pointer change with each push and pop operation.

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