Stack Concept & Implementation

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Module 4, Chapter 5: Classic Backtracking Problems Time to complete: ~20 minutes

Table of Contents

1. The LIFO Principle
2. Implementing a Stack with a Python List
3. Complexity of Stack Operations
4. The Call Stack Was a Stack All Along
5. Summary & Next Steps

1. The LIFO Principle

A stack is a collection where the last item added is the first one removed — Last In, First Out (LIFO). Picture a stack of plates: you add to the top, and you remove from the top; you can't grab a plate from the middle without removing everything above it first.

push(1) → [1]
push(2) → [1, 2]
push(3) → [1, 2, 3]
pop()   → returns 3, stack is now [1, 2]     ← the LAST one in was the FIRST one out

2. Implementing a Stack with a Python List

Python's built-in list already behaves exactly like a stack when you restrict yourself to operating on its end — no custom class is required for most purposes:

stack = []
 
stack.append(1)      # push
stack.append(2)
stack.append(3)
print(stack)          # [1, 2, 3]
 
top = stack.pop()     # pop — removes and returns the LAST item
print(top)              # 3
print(stack)             # [1, 2]
 
peek = stack[-1]         # peek — look at the top without removing it
print(peek)                # 2

If you want the stack behavior enforced explicitly (so nothing accidentally operates on the front of the list), a thin wrapper class makes the intent unambiguous:

class Stack:
    def __init__(self):
        self._items = []
 
    def push(self, item):
        self._items.append(item)
 
    def pop(self):
        return self._items.pop()
 
    def peek(self):
        return self._items[-1]
 
    def is_empty(self):
        return len(self._items) == 0
 
    def __len__(self):
        return len(self._items)

3. Complexity of Stack Operations

All three core operations work at the end of the underlying list — exactly the end Module 2 identified as cheap for Python lists:

This is precisely why a stack is implemented using the end of a list rather than the front — .pop(0) or .insert(0, x) at the front would be O(n), as Module 2 covered. Chapter 3 of this module revisits that exact cost when building a queue, where the front is the active end instead.

4. The Call Stack Was a Stack All Along

Module 4's call stack diagrams were, quite literally, a stack: each function call is "pushed" on invocation and "popped" on return, and the most recently called (and not-yet-returned) function is always the one currently executing — the definition of LIFO. Naming it explicitly now should make that connection concrete: recursion and the stack data structure are two views of the same underlying idea.

5. Summary & Next Steps

Key Takeaways

• A stack is LIFO — the last item pushed is the first popped.
• Python's list, used only at its end (.append/.pop()), is a stack — O(1) for push, pop, and peek.
• Never use the front of a list for stack operations — that reintroduces the O(n) shifting cost Module 2 warned about.
• The call stack from Module 4 is a real-world instance of this exact data structure.

Concept Check

1. Why is .append() / .pop() (no argument) the right choice for a stack, but .insert(0, x) / .pop(0) is not?
2. What does "LIFO" stand for, and how does the plate-stack analogy capture it?
3. In what sense is the recursive call stack from Module 4 literally a stack?

Next Chapter

→ Chapter 2: Stack Applications

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index