Dynamic Stack Using Resizable Array in DSA Rust - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation?

No→Pop Operation?

↓

Check Capacity

↓

Resize Array

↓

Add Element

↓

Update Top Index

↓

Repeat

This flow shows how a dynamic stack using a resizable array handles push and pop operations, resizing the array when full and preventing pop when empty.

Execution Sample

DSA Rust

stack = DynamicStack::new()
stack.push(10)
stack.push(20)
stack.push(30)
stack.pop()
stack.push(40)

This code creates a dynamic stack, pushes three elements, pops one, then pushes another.

Execution Table

Step	Operation	Array Capacity	Top Index	Array Contents	Pointer Changes	Visual State
1	Initialize stack	2	-1	[]	top = -1	[]
2	Push 10	2	0	[10, _]	top: -1 -> 0	[10]
3	Push 20	2	1	[10, 20]	top: 0 -> 1	[10 -> 20]
4	Push 30 (resize needed)	2 -> 4	2	[10, 20, 30, _]	resize array, top: 1 -> 2	[10 -> 20 -> 30]
5	Pop (remove 30)	4	1	[10, 20, 30, _]	top: 2 -> 1	[10 -> 20]
6	Push 40	4	2	[10, 20, 40, _]	top: 1 -> 2	[10 -> 20 -> 40]

💡 No more operations, stack ends with top index 2 and capacity 4.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6
top	-1	0	1	2	1	2
capacity	2	2	2	4	4	4
array	[]	[10, _]	[10, 20]	[10, 20, 30, _]	[10, 20, 30, _]	[10, 20, 40, _]

Key Moments - 3 Insights

Why do we resize the array when pushing the third element?

The initial capacity is 2, so when top index reaches 1 (full), pushing another element requires resizing to hold more elements, as shown in step 4 of the execution_table.

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

Popping only moves the top index down to exclude the last element logically; the array still holds the old value until overwritten, as seen in step 5 where array contents remain but top index changes.

What happens if we pop when the stack is empty?

The stack checks if top index is -1 (empty). If yes, it prevents popping to avoid underflow. This is shown in the concept_flow where pop operation checks for empty before removing.

Visual Quiz - 3 Questions

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

A 0

B 1

C 2

D -1

💡 Hint

Check Step 3 in execution_table under 'Top Index' column.

At which step does the array capacity increase?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look for 'resize array' note in the 'Pointer Changes' column in execution_table.

If we pop twice after step 6, what will be the top index?

A 0

B 1

C -1

D 2

💡 Hint

After step 6 top is 2; popping twice reduces top by 2, see variable_tracker for 'top' changes.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses an array with a top index to track stack top.
- Push adds element at top+1; pop removes element at top.
- When array is full, resize doubles capacity.
- Pop on empty stack is prevented to avoid errors.
- Top index starts at -1 (empty stack).

Full Transcript

This visualization shows a dynamic stack implemented with a resizable array. The stack starts empty with capacity 2 and top index -1. Each push adds an element at the next top position. When pushing the third element, the array resizes to capacity 4 to hold more elements. Popping moves the top index down but does not erase the array content immediately. The stack prevents popping when empty to avoid underflow. The variable tracker shows how top index and capacity change after each operation. The visual quiz tests understanding of top index positions and resizing steps.

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It does not require resizing or copying elements.

B. It can grow or shrink in size as needed during runtime.

C. It always has a fixed maximum size.

D. It uses less memory than a linked list stack.

Solution

1. Step 1: Understand fixed vs dynamic size

   A fixed-size array stack has a set capacity that cannot change during runtime, limiting the number of elements it can hold.

2. Step 2: Analyze dynamic stack behavior

   A dynamic stack using a resizable array can increase or decrease its capacity by resizing the underlying array, allowing it to handle more or fewer elements as needed.

3. Final Answer:

   It can grow or shrink in size as needed during runtime. -> Option B

4. Quick Check:

   Dynamic resizing = flexible size [OK]

Hint: Dynamic stack resizes array to fit elements [OK]

Common Mistakes:

• Thinking dynamic stack has fixed size
• Confusing linked list with array stack
• Assuming no resizing needed

2. Which Rust code snippet correctly doubles the capacity of a vector when the stack is full?

easy

A. if stack.len() == stack.capacity() { stack.reserve(stack.capacity()); }

B. if stack.len() == stack.capacity() { stack.reserve(1); }

C. if stack.len() == stack.capacity() { stack.reserve(stack.len() / 2); }

D. if stack.len() == stack.capacity() { stack.reserve(0); }

Solution

1. Step 1: Understand vector capacity and reserve method

   The vector's capacity is the total space allocated. To double capacity, we add capacity() more space using reserve(capacity()).

2. Step 2: Check each option's reserve argument

   if stack.len() == stack.capacity() { stack.reserve(stack.capacity()); } reserves current capacity again, doubling it. Others reserve too little or zero, not doubling.

3. Final Answer:

   if stack.len() == stack.capacity() { stack.reserve(stack.capacity()); } -> Option A

4. Quick Check:

   Reserve current capacity to double [OK]

Hint: Reserve current capacity to double vector size [OK]

Common Mistakes:

• Reserving fixed small number instead of doubling
• Using zero in reserve causing no growth
• Confusing len() with capacity()

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

struct Stack {
    data: Vec<i32>,
}

impl Stack {
    fn new() -> Self {
        Stack { data: Vec::new() }
    }
    fn push(&mut self, val: i32) {
        self.data.push(val);
    }
    fn pop(&mut self) -> Option<i32> {
        self.data.pop()
    }
    fn print(&self) {
        for v in self.data.iter().rev() {
            print!("{} -> ", v);
        }
        println!("null");
    }
}

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

medium

A. 20 -> 10 -> null

B. 30 -> 20 -> null

C. 10 -> 30 -> null

D. 30 -> 10 -> null

Solution

1. Step 1: Trace push and pop operations

   Push 10: stack = [10]; Push 20: stack = [10, 20]; Pop: removes 20, stack = [10]; Push 30: stack = [10, 30]

2. Step 2: Understand print order

   Print iterates in reverse order: top is last element pushed, so prints 30 then 10, then null.

3. Final Answer:

   30 -> 10 -> null -> Option D

4. Quick Check:

   Stack top to bottom = 30, 10 [OK]

Hint: Pop removes last pushed; print reverses vector [OK]

Common Mistakes:

• Forgetting pop removes last element
• Printing in wrong order (not reversed)
• Confusing push order with print order

4. Identify the bug in this Rust code snippet for a dynamic stack push method:

fn push(&mut self, val: i32) {
    if self.data.len() == self.data.capacity() {
        self.data.reserve(self.data.len());
    }
    self.data.push(val);
}

medium

A. reserve argument should be capacity(), not len()

B. reserve should be called after push, not before

C. No bug; code works correctly

D. push should be called only if capacity is not full

Solution

1. Step 1: Check the resizing logic

   When self.data.len() == self.data.capacity(), the stack is full. reserve(self.data.len()) requests additional space for len() more elements. Since len() == capacity() at this point, it doubles the capacity.

2. Step 2: Verify correctness

   reserve(self.data.capacity()) would be equivalent here. The code safely resizes before push, preventing issues, and works correctly. (Rust Vec::push auto-resizes too, but manual is valid.)

3. Final Answer:

   No bug; code works correctly -> Option C

4. Quick Check:

   len() == capacity() when called, so doubles [OK]

Hint: When full, reserve(len()) == reserve(capacity()), doubles size [OK]

Common Mistakes:

• Reserving too little space (e.g., reserve(1))
• Calling reserve after push causing potential panic
• Assuming push auto-resizes without manual check

5. You want to implement a dynamic stack in Rust that shrinks its capacity when the number of elements falls below one-quarter of the capacity to save memory. Which approach correctly achieves this behavior?

hard

A. After pop, if len() < capacity() / 4, call data.shrink_to(len())

B. After pop, if len() < capacity() / 2, call data.reserve(len())

C. After pop, if len() < capacity() / 4, call data.reserve(capacity() / 2)

D. After pop, if len() < capacity() / 4, do nothing; shrinking is automatic

Solution

1. Step 1: Understand shrinking condition

   We want to shrink when elements are less than 25% of capacity to save memory.

2. Step 2: Use shrink_to method correctly

   Calling shrink_to(len()) reduces capacity to fit current elements, freeing unused space.

3. Step 3: Analyze options

   After pop, if len() < capacity() / 4, call data.shrink_to(len()) correctly checks condition and calls shrink_to(len()). Others either use wrong methods or do nothing.

4. Final Answer:

   After pop, if len() < capacity() / 4, call data.shrink_to(len()) -> Option A

5. Quick Check:

   Shrink when quarter full using shrink_to(len()) [OK]

Hint: Shrink vector capacity with shrink_to(len()) when quarter full [OK]

Common Mistakes:

• Using reserve instead of shrink_to for shrinking
• Shrinking at half capacity instead of quarter
• Assuming automatic shrinking without code