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.

Practice

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

easy

A. It always has a fixed capacity.

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

C. It does not require resizing when full.

D. It can grow or shrink automatically as elements are pushed or popped.

Solution

1. Step 1: Understand fixed-size array stack limitation

   A fixed-size array stack has a set capacity and cannot grow beyond it, causing overflow if exceeded.

2. Step 2: Analyze dynamic stack behavior

   A dynamic stack using a resizable array automatically increases or decreases its size when needed, avoiding overflow and wasted space.

3. Final Answer:

   It can grow or shrink automatically as elements are pushed or popped. -> Option D

4. Quick Check:

   Dynamic resizing = automatic growth/shrink [OK]

Hint: Dynamic stacks resize arrays automatically when full or empty [OK]

Common Mistakes:

• Thinking dynamic stack never resizes
• Confusing dynamic stack with linked list stack
• Assuming fixed capacity for dynamic stack

2. Which of the following is the correct way to double the size of the internal array in a dynamic stack implemented in Python?

easy

A. self.array.extend([None] * len(self.array))

B. self.array = self.array * 2

C. self.array = [None] * (len(self.array) * 2)

D. self.array.append(self.array)

Solution

1. Step 1: Understand array resizing in Python list

   To double the size, we add extra None elements equal to current length to the list.

2. Step 2: Check each option

   self.array.extend([None] * len(self.array)) correctly extends the list by adding None elements equal to current length, doubling size.

3. Final Answer:

   self.array.extend([None] * len(self.array)) -> Option A

4. Quick Check:

   Extend with None * current length = double size [OK]

Hint: Use extend with None times current length to double array [OK]

Common Mistakes:

• Using multiplication on list copies elements, not size
• Assigning new list loses old elements
• Appending array inside itself causes nested list

3. Consider this Python code for a dynamic stack push operation:

def push(self, item):
    if self.top == len(self.array):
        self.array.extend([None] * len(self.array))
    self.array[self.top] = item
    self.top += 1

stack = DynamicStack()
stack.push(10)
stack.push(20)
stack.push(30)
print(stack.array[:stack.top])

What will be the printed output?

medium

A. [10, 20, 30]

B. [10, 20, 30, None, None, None]

C. [None, None, None]

D. IndexError

Solution

1. Step 1: Trace push calls and array state

   Initially array is empty or small. On first push, item 10 is placed at index 0, top becomes 1. Similarly for 20 and 30 at indices 1 and 2.

2. Step 2: Print array slice up to top

   Printing array[:top] shows only elements at indices 0,1,2 which are [10, 20, 30].

3. Final Answer:

   [10, 20, 30] -> Option A

4. Quick Check:

   Print array slice up to top = pushed elements [OK]

Hint: Print only up to top index to see current stack elements [OK]

Common Mistakes:

• Printing full array including None values
• Confusing top index with length
• Expecting error due to resizing

4. Given this buggy pop method for a dynamic stack:

def pop(self):
    if self.top == 0:
        return None
    self.top -= 1
    item = self.array[self.top]
    self.array[self.top] = None
    if self.top < len(self.array) // 4:
        self.array = self.array[:len(self.array) // 2]
    return item

What is the main issue with this code?

medium

A. It does not set popped element to None.

B. It does not check for empty stack before popping.

C. It shrinks the array too early, causing frequent resizing.

D. It doubles the array size instead of shrinking.

Solution

1. Step 1: Understand shrinking condition

   The array shrinks when top is less than one-fourth of array length, which can cause frequent resizing if elements fluctuate near this threshold.

2. Step 2: Identify problem with frequent resizing

   Frequent shrinking and expanding wastes time and resources, so better to shrink less aggressively.

3. Final Answer:

   It shrinks the array too early, causing frequent resizing. -> Option C

4. Quick Check:

   Shrink threshold too high = frequent resize [OK]

Hint: Shrink array only when usage is very low to avoid thrashing [OK]

Common Mistakes:

• Ignoring empty stack check (it is present)
• Confusing shrinking with doubling
• Not clearing popped element

5. You want to implement a dynamic stack that minimizes memory usage by shrinking the internal array only when the number of elements is less than 1/8 of the array size. Which change should you make to the pop method's shrinking condition?

def pop(self):
    if self.top == 0:
        return None
    self.top -= 1
    item = self.array[self.top]
    self.array[self.top] = None
    if ???:
        self.array = self.array[:len(self.array) // 2]
    return item

hard

A. if self.top == 0

B. if self.top < len(self.array) // 8

C. if self.top <= len(self.array) // 2

D. if self.top < len(self.array) // 4

Solution

1. Step 1: Understand shrinking threshold

   To shrink only when usage is less than 1/8, the condition must check if top is less than array length divided by 8.

2. Step 2: Match condition to code

   if self.top < len(self.array) // 8 correctly uses 'if self.top < len(self.array) // 8' to trigger shrinking at 1/8 usage.

3. Final Answer:

   if self.top < len(self.array) // 8 -> Option B

4. Quick Check:

   Shrink when usage < 1/8 = condition in if self.top < len(self.array) // 8 [OK]

Hint: Use 1/8 threshold to shrink less often and save memory [OK]

Common Mistakes:

• Using 1/4 threshold shrinks too early
• Using equality instead of less than
• Shrinking when stack is empty only