Dynamic Stack Using Resizable Array in DSA Python

Mental Model

A dynamic stack grows its storage automatically when full, so you never run out of space while adding items.

Analogy: Imagine a backpack that magically expands when you try to put in more books than it can hold, so you never have to leave a book behind.

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

Dry Run Walkthrough

Input: Start with stack holding [1, 2, 3], capacity 3, push 4, then push 5

Goal: Show how the stack resizes when pushing beyond capacity and keeps all elements

Step 1: Push 4, stack is full so resize array to double capacity (3 -> 6)

Stack array: [1, 2, 3, 4, null, null]
Top index: ↑ 3
Capacity: 6

Why: We need more space to add the new element without losing old ones

Step 2: Push 5, add element at next free spot

Stack array: [1, 2, 3, 4, 5, null]
Top index: ↑ 4
Capacity: 6

Why: There is enough space now, so just add the element

Result:

Stack array: [1, 2, 3, 4, 5, null]
Top index: ↑ 4
Capacity: 6

Annotated Code

DSA Python

class DynamicStack:
    def __init__(self):
        self.capacity = 3
        self.stack = [None] * self.capacity
        self.top = -1

    def push(self, value):
        if self.top + 1 == self.capacity:
            self._resize()
        self.top += 1
        self.stack[self.top] = value

    def _resize(self):
        new_capacity = self.capacity * 2
        new_stack = [None] * new_capacity
        for i in range(self.capacity):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

    def pop(self):
        if self.top == -1:
            return None
        value = self.stack[self.top]
        self.stack[self.top] = None
        self.top -= 1
        return value

    def __str__(self):
        if self.top == -1:
            return "Stack is empty"
        return " -> ".join(str(self.stack[i]) for i in range(self.top + 1)) + " -> null"

# Driver code
stack = DynamicStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)  # Before resizing
stack.push(4)  # Triggers resize
print(stack)  # After pushing 4
stack.push(5)
print(stack)  # After pushing 5

if self.top + 1 == self.capacity:

Check if stack is full before pushing

self._resize()

Double the capacity and copy elements to new array

self.top += 1 self.stack[self.top] = value

Add new element at next free position

Output

1 -> 2 -> 3 -> null

1 -> 2 -> 3 -> 4 -> null

1 -> 2 -> 3 -> 4 -> 5 -> null

Complexity Analysis

Time: O(1) average for push because resizing happens rarely; O(n) worst case when resizing copies all elements

Space: O(n) because the stack uses an array that grows with the number of elements

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

Edge Cases

Pushing into an empty stack

Element is added at position 0 without resizing

DSA Python

if self.top + 1 == self.capacity:

Popping from an empty stack

Returns None safely without error

DSA Python

if self.top == -1:

Pushing elements exactly at capacity boundary

Triggers resize to double capacity before adding new element

DSA Python

if self.top + 1 == self.capacity:

When to Use This Pattern

When you need a stack that can grow without a fixed limit, use a dynamic stack with resizing to handle unknown input sizes safely.

Common Mistakes

Mistake: Not resizing before pushing when stack is full, causing index errors
Fix: Always check if stack is full and resize before adding new element

Mistake: Forgetting to update capacity after resizing
Fix: Update the capacity variable after copying elements to new array

Summary

It implements a stack that automatically grows its storage when full.

Use it when you want a stack without a fixed size limit and unknown number of pushes.

The key insight is to double the array size and copy elements before pushing when full.