Dynamic Stack Using Resizable Array in DSA Python - Build from Scratch

Dynamic Stack Using Resizable Array

📖 Scenario: Imagine you are building a simple stack data structure that can grow when needed, like a stack of plates that can get taller if more plates are added.

🎯 Goal: You will create a dynamic stack using a list that resizes itself when it gets full. You will implement push and pop operations and see how the stack changes.

📋 What You'll Learn

Create a list called stack to hold stack elements

Create an integer variable capacity to track the current size limit of the stack

Create an integer variable top to track the index of the top element in the stack

Implement a push function that adds an element to the stack and doubles the capacity if full

Implement a pop function that removes and returns the top element from the stack

Print the stack after push and pop operations to see the current elements

💡 Why This Matters

🌍 Real World

Dynamic stacks are used in many programs where the number of items is not fixed, like undo features or expression evaluation.

💼 Career

Understanding dynamic data structures like resizable stacks is important for software development and technical interviews.

1

Create the initial stack and variables

Create a list called stack with size 2 filled with None, an integer variable capacity set to 2, and an integer variable top set to -1.

DSA Python

# Create stack list, capacity, and top variables
# Your code here

Hint

Think of stack as a list with empty slots, capacity as how many slots it has, and top as the position of the last added item.

2

Add a function to push elements with resizing

Define a function called push that takes a parameter value. Inside, check if top + 1 equals capacity. If yes, double the capacity, create a new list with double size, copy old elements, and assign it to stack. Then increase top by 1 and set stack[top] to value.

DSA Python

stack = [None, None]
capacity = 2
top = -1

# Define push function to add value and resize if needed
# Your code here

Hint

Remember to use global to modify variables outside the function. Copy elements one by one to the new bigger list.

3

Add a function to pop elements from the stack

Define a function called pop that returns the top element from stack. If top is -1, return None. Otherwise, store stack[top] in a variable, set stack[top] to None, decrease top by 1, and return the stored value.

DSA Python

stack = [None, None]
capacity = 2
top = -1

def push(value):
    global stack, capacity, top
    if top + 1 == capacity:
        capacity *= 2
        new_stack = [None] * capacity
        for i in range(top + 1):
            new_stack[i] = stack[i]
        stack = new_stack
    top += 1
    stack[top] = value

# Define pop function to remove and return top element
# Your code here

Hint

Check if the stack is empty by seeing if top is -1. Remove the top element and update top.

4

Test the stack by pushing and popping elements

Call push(10), push(20), push(30), then print the stack and capacity. Next, call pop() and print the popped value, then print the stack and capacity again.

DSA Python

stack = [None, None]
capacity = 2
top = -1

def push(value):
    global stack, capacity, top
    if top + 1 == capacity:
        capacity *= 2
        new_stack = [None] * capacity
        for i in range(top + 1):
            new_stack[i] = stack[i]
        stack = new_stack
    top += 1
    stack[top] = value

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

# Push 10, 20, 30; print stack and capacity
# Pop one element; print popped value, stack and capacity
# Your code here

Hint

After pushing 3 elements, the stack should resize from 2 to 4. Popping removes the last pushed element.