Stacks

Analogy categoryAnalogies

Introduction

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle: the most recently added element is the first one removed. Think of a stack of plates — you add a plate to the top and you remove from the top, never from the bottom or the middle. Stacks are the backbone of function call management, undo/redo features, expression evaluation, and backtracking algorithms.

🏏

Cricket analogy: A stack mirrors how a captain manages bowling changes under pressure — the last bowler brought on is often the first one reconsidered when a change is needed, exactly like a stack of plates where you only add and remove from the top, never the bottom.

Syntax

python

# Python does not have a dedicated Stack class; a list works well
stack = []

# Push (add to the top)
stack.append(10)
stack.append(20)
stack.append(30)

# Peek (look at the top without removing)
top = stack[-1]

# Pop (remove from the top)
removed = stack.pop()

# Check if empty
is_empty = len(stack) == 0

Explanation

A Python list is a good choice for a stack because append() and pop() both operate on the end of the list in O(1) amortized time, with no shifting of other elements. Avoid using pop(0) or insert(0, x) for stack-like behavior — those operate on the front of the list and cost O(n) because every remaining element must shift. For a stack, all activity must stay at one end. The collections.deque class also supports O(1) append/pop from both ends and is a common alternative when you want an explicit, purpose-built container.

🏏

Cricket analogy: Using a simple list as a bowling-change stack works because adding or removing the latest bowler at the end is O(1) with no reshuffling, but inserting or removing a bowler from the front of the list costs O(n) since the whole order must shift — for stack behavior, all activity must stay at one end, and a double-ended queue is a purpose-built alternative.

Example

python

def is_balanced(expression: str) -> bool:
    """Check whether brackets in an expression are balanced using a stack."""
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False

    return len(stack) == 0


print(is_balanced("{[a+(b*c)]-d}"))  # True
print(is_balanced("{[a+(b*c)]-d}}")) # False

Complexity

With a list-backed stack: push (append) is O(1) amortized, pop is O(1), peek is O(1), and searching for an arbitrary element is O(n). Space complexity is O(n) for n elements. Because every operation touches only the top, stacks are extremely cache-friendly and predictable in performance, which is why they underlie the call stack used by every recursive function.

🏏

Cricket analogy: Pushing a new bowling change onto the stack is O(1) amortized, popping the latest change back off is O(1), peeking at who's currently bowling is O(1), but finding whether a specific bowler was ever used requires an O(n) scan, and because every operation touches only the top, it's as predictable as the reliable death-over specialist every captain wants.

Key Takeaways

Stacks follow LIFO: the last element pushed is the first popped.
Use list.append()/list.pop() (or collections.deque) for O(1) push/pop in Python — never pop(0).
Common uses: undo/redo, expression parsing, balanced-bracket checks, and simulating recursion.
Peek accesses the top element without removing it, also O(1).
Stack overflow in recursion is a real-world consequence of unbounded LIFO growth on the call stack.

Practice what you learned

1. Which principle defines a stack's behavior?

2. In Python, which pair of list operations gives O(1) push and pop for a stack?

3. What real-world mechanism is directly modeled by a stack?

4. In the balanced-parentheses algorithm, what causes the function to return False when a closing bracket is encountered?

Was this page helpful?

Queues

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#Stacks#Syntax#Explanation#Example#Complexity#StudyNotes#SkillVeris