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.

Practice

1. Why do we use a stack data structure in programming?

easy

A. To sort numbers automatically

B. To keep track of function calls and return in the correct order

C. To store data in random order for quick access

D. To store data permanently on disk

Solution

1. Step 1: Understand the nature of stack

   A stack works on Last In First Out (LIFO) principle, meaning the last item added is the first to be removed.

2. Step 2: Relate stack to function calls

   Function calls are nested and must return in reverse order of calling, which matches LIFO behavior of stack.

3. Final Answer:

   To keep track of function calls and return in the correct order -> Option B

4. Quick Check:

   Stack = Function call tracking [OK]

Hint: Stack follows LIFO, perfect for tracking nested calls [OK]

Common Mistakes:

• Thinking stack sorts data automatically
• Confusing stack with queue (FIFO)
• Assuming stack stores data permanently

2. Which of the following is the correct way to push an element 'x' onto a stack named stack in Python?

easy

A. stack.push(x)

B. stack.add(x)

C. stack.append(x)

D. stack.insert(x)

Solution

1. Step 1: Recall Python list methods for stack

   Python uses list to implement stack; append() adds element to the top.

2. Step 2: Check other options

   push() and add() are not list methods; insert() inserts at specific index, not top.

3. Final Answer:

   stack.append(x) -> Option C

4. Quick Check:

   Use append() to push in Python stack [OK]

Hint: Use append() to add on top of Python list stack [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using insert() without index argument
• Confusing add() with append()

3. What will be the output of the following Python code?

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())
print(stack)

medium

A. 3
[1, 2]

B. 1
[2, 3]

C. 2
[1, 3]

D. 3
[3, 2, 1]

Solution

1. Step 1: Trace stack after append operations

   After appending 1, 2, 3, stack = [1, 2, 3]

2. Step 2: Understand pop() behavior

   pop() removes and returns last element, so pop() returns 3 and stack becomes [1, 2]

3. Final Answer:

   3 [1, 2] -> Option A

4. Quick Check:

   pop() returns last item, stack updates [OK]

Hint: pop() removes last added element in stack [OK]

Common Mistakes:

• Thinking pop() removes first element
• Confusing append() with insert()
• Expecting stack to be unchanged after pop()

4. The following code is intended to reverse a list using a stack, but it has an error. What is the error?

def reverse_list(lst):
    stack = []
    for item in lst:
        stack.push(item)
    reversed_lst = []
    while stack:
        reversed_lst.append(stack.pop())
    return reversed_lst

print(reverse_list([1, 2, 3]))

medium

A. Using push() method which does not exist for Python lists

B. Using pop() incorrectly without parentheses

C. Not initializing reversed_lst before use

D. Loop condition should be 'while not stack'

Solution

1. Step 1: Check stack operations in Python

   Python lists do not have push() method; append() should be used to add elements.

2. Step 2: Verify other parts of code

   pop() is used correctly with parentheses; reversed_lst is initialized; while stack is correct to check non-empty list.

3. Final Answer:

   Using push() method which does not exist for Python lists -> Option A

4. Quick Check:

   Use append() not push() for Python list stack [OK]

Hint: Python list uses append(), not push() [OK]

Common Mistakes:

• Using push() instead of append()
• Forgetting parentheses on pop()
• Incorrect while loop condition

5. You want to check if a string has balanced parentheses using a stack. Which approach correctly solves this problem?

hard

A. Use a queue to enqueue '(' and dequeue when ')' found

B. Count total '(' and ')' characters; if counts equal, parentheses are balanced

C. Replace all '(' with ')' and check if string is palindrome

D. Push '(' onto stack; pop when ')' found; if stack empty at end, parentheses are balanced

Solution

1. Step 1: Understand balanced parentheses logic

   Each '(' must be matched by a ')' in correct order; stack helps track unmatched '('.

2. Step 2: Explain stack approach

   Push '(' onto stack; on encountering ')', pop stack; if stack empty at end, parentheses are balanced.

3. Step 3: Evaluate other options

   Counting characters ignores order; palindrome check is unrelated; queue (FIFO) does not match nesting order.

4. Final Answer:

   Push '(' onto stack; pop when ')' found; if stack empty at end, parentheses are balanced -> Option D

5. Quick Check:

   Stack tracks open parentheses for balance [OK]

Hint: Use stack push/pop to match parentheses pairs [OK]

Common Mistakes:

• Only counting parentheses without order check
• Using queue instead of stack for nesting
• Ignoring unmatched parentheses inside string