Dynamic Stack Using Resizable Array in DSA Rust

Mental Model

A stack is a collection where you add and remove items only from the top. When the stack is full, we make the storage bigger automatically to hold more items.

Analogy: Imagine a stack of plates. You can only add or take the top plate. If the stack gets too tall for your shelf, you get a bigger shelf to hold more plates.

Stack array: [ 1, 2, 3, _, _ ]
Top index: ↑ (points to 3)
Capacity: 5
Size: 3

Dry Run Walkthrough

Input: Start with empty stack capacity 2, push 1, push 2, push 3 (causes resize), pop once

Goal: Show how the stack grows when full and how pop removes the top item

Step 1: Push 1 onto empty stack

Stack array: [ 1, _ ]
Top index: ↑ (points to 1)
Capacity: 2
Size: 1

Why: Add first item at position 0, stack size increases

Step 2: Push 2 onto stack

Stack array: [ 1, 2 ]
Top index: ↑ (points to 2)
Capacity: 2
Size: 2

Why: Add second item at position 1, stack is now full

Step 3: Push 3 triggers resize: double capacity to 4, copy old items, then add 3

Stack array: [ 1, 2, 3, _ ]
Top index: ↑ (points to 3)
Capacity: 4
Size: 3

Why: Stack full, so resize to hold more items before adding new one

Step 4: Pop removes top item 3

Stack array: [ 1, 2, _, _ ]
Top index: ↑ (points to 2)
Capacity: 4
Size: 2

Why: Remove top item and decrease size, top moves down

Result:

Stack array: [ 1, 2, _, _ ]
Top index: ↑ (points to 2)
Capacity: 4
Size: 2

Annotated Code

DSA Rust

struct DynamicStack {
    data: Vec<i32>,
    size: usize,
}

impl DynamicStack {
    fn new() -> Self {
        Self {
            data: Vec::with_capacity(2),
            size: 0,
        }
    }

    fn push(&mut self, value: i32) {
        if self.size == self.data.capacity() {
            // Resize: double capacity
            let new_capacity = self.data.capacity() * 2;
            let mut new_data = Vec::with_capacity(new_capacity);
            // Copy old elements
            for i in 0..self.size {
                new_data.push(self.data[i]);
            }
            self.data = new_data;
        }
        if self.size < self.data.len() {
            self.data[self.size] = value;
        } else {
            self.data.push(value);
        }
        self.size += 1;
    }

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

    fn print_stack(&self) {
        print!("Stack: ");
        for i in 0..self.size {
            print!("{} ", self.data[i]);
        }
        println!();
    }
}

fn main() {
    let mut stack = DynamicStack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3); // triggers resize
    stack.print_stack();
    stack.pop();
    stack.print_stack();
}

if self.size == self.data.capacity() {

Check if stack is full and needs resizing

let new_capacity = self.data.capacity() * 2;

Calculate new capacity by doubling current capacity

for i in 0..self.size { new_data.push(self.data[i]); }

Copy existing elements to new larger storage

self.size += 1;

Increase stack size after adding new element

if self.size == 0 { return None; }

Handle pop on empty stack by returning None

self.size -= 1;

Decrease stack size when popping top element

Output

Stack: 1 2 3 

Stack: 1 2 

Complexity Analysis

Time: O(1) average for push and pop because resizing happens rarely; resizing is O(n) but amortized over many pushes

Space: O(n) because the stack stores all pushed elements in a resizable array

vs Alternative: Compared to a fixed-size array stack, dynamic resizing avoids overflow but uses extra space and occasional copying

Edge Cases

Pop from empty stack

Returns None safely without error

DSA Rust

if self.size == 0 { return None; }

Push when stack is exactly full

Triggers resize doubling capacity before adding new element

DSA Rust

if self.size == self.data.capacity() { ... }

Push after resize

New element added correctly to resized storage

DSA Rust

self.data.push(value);

When to Use This Pattern

When you need a stack that can grow beyond a fixed size without knowing max size upfront, use a dynamic stack with resizing array to handle growth efficiently.

Common Mistakes

Mistake: Not copying old elements to new larger array during resize
Fix: Copy all existing elements to the new array before replacing the old one

Mistake: Increasing size before adding element causing index out of bounds
Fix: Add element first, then increase size

Mistake: Popping from empty stack without checking size
Fix: Check if size is zero and return None before popping

Summary

Implements a stack that grows automatically by resizing its array when full.

Use when you want a stack but don't know the maximum number of items in advance.

The key is to double the array size when full and copy old items to avoid overflow.

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