Why Stack Exists and What Problems It Solves in DSA Python - Why This Pattern

Mental Model

A stack helps us keep track of things in the order they happen, so we can go back step-by-step in reverse order.

Analogy: Think of a stack like a stack of plates: you add plates on top and take plates from the top only, so the last plate you put is the first one you take out.

Top -> [Plate3]
        [Plate2]
        [Plate1]
        null

Dry Run Walkthrough

Input: Scenario: You have tasks A, B, C to do in order, but you want to finish the last task first.

Goal: Show how stack helps to do tasks in reverse order easily.

Step 1: Push task A onto the stack

Top -> [A]
        null

Why: We start by adding the first task to the stack.

Step 2: Push task B onto the stack

Top -> [B]
        [A]
        null

Why: Add the second task on top of the first, so B is done before A.

Step 3: Push task C onto the stack

Top -> [C]
        [B]
        [A]
        null

Why: Add the third task on top, so C is done first.

Step 4: Pop the top task (C) to do it

Top -> [B]
        [A]
        null

Why: We do the last added task first, following the stack order.

Step 5: Pop the next task (B) to do it

Top -> [A]
        null

Why: Next, do the second last task.

Step 6: Pop the last task (A) to do it

Top -> null

Why: Finally, do the first task added.

Result:

Top -> null
All tasks done in reverse order: C, B, A

Annotated Code

DSA Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)  # add item on top

    def pop(self):
        if not self.is_empty():
            return self.items.pop()  # remove and return top item
        return None

    def is_empty(self):
        return len(self.items) == 0

    def __str__(self):
        return 'Top -> ' + ' -> '.join(reversed(self.items)) + ' -> null'

# Driver code to show why stack helps
stack = Stack()

# Push tasks A, B, C
stack.push('A')
stack.push('B')
stack.push('C')
print(stack)  # Show stack after pushes

# Pop tasks to do them in reverse order
print('Doing task:', stack.pop())
print(stack)
print('Doing task:', stack.pop())
print(stack)
print('Doing task:', stack.pop())
print(stack)

self.items.append(item) # add item on top

push adds new item on top of stack

return self.items.pop() # remove and return top item

pop removes and returns the top item to process it

Output

Top -> C -> B -> A -> null

Doing task: C

Top -> B -> A -> null

Doing task: B

Top -> A -> null

Doing task: A

Top -> null

Complexity Analysis

Time: O(1) for push and pop because these operations only add or remove the top item without scanning the whole stack

Space: O(n) where n is the number of items because all items are stored in the stack

vs Alternative: Compared to using a list without stack rules, stack ensures last-in-first-out order with simple O(1) operations instead of costly searches or shifts

Edge Cases

Pop from empty stack

Returns None safely without error

DSA Python

if not self.is_empty():

When to Use This Pattern

When you need to reverse order or remember the last thing added first, think of using a stack because it naturally follows last-in-first-out order.

Common Mistakes

Mistake: Trying to pop from an empty stack without checking
Fix: Always check if the stack is empty before popping to avoid errors

Summary

A stack stores items so you can add and remove them in reverse order.

Use a stack when you need to process things in the opposite order they arrive.

The key is last-in-first-out: the last thing you add is the first you take out.