Stack

Intuition

A stack is a stack of plates. You can put a new plate on top, and you can take a plate off the top — but you can't reach a plate from the middle without lifting the ones above first. The plate you most recently put down is the first one back off.

This discipline has a name: LIFO, Last-In-First-Out. It maps to exactly the situations where you need to "remember what you were doing" and resume in reverse order — function calls, undo history, parsing nested brackets, depth-first traversal.

How It Works

A stack exposes two core operations:

• push(val) — add val on top. If the stack has a fixed capacity and is already full, raise an overflow error.
• pop() — remove and return the top value. If the stack is empty, raise an underflow error.

Both run in O(1) because the only end that changes is the top — no shifting, no scanning. Under the hood, a stack is usually backed by a dynamic array (self.data in the displayed code) where the "top" is just the last index. append and list.pop() on a Python list are both O(1) amortized.

Many implementations also expose peek() (read the top without removing) and size() / is_empty(). Those are convenience — they're not part of the core LIFO contract.

The visualization caps capacity to give overflow a visible meaning. Real Python lists grow without bound — overflow is a pedagogical constraint, not a property of the data structure.

Step By Step

Starting with an empty stack of capacity 5:

1. push(3) → stack is [3]. The cell appears at the bottom of the column, the top index is 0.
2. push(7) → stack is [3, 7]. New cell stacks above the previous; top index is 1.
3. push(1) → stack is [3, 7, 1].
4. pop() → returns 1. Stack is [3, 7]. The top cell lifts off and fades.
5. pop() → returns 7. Stack is [3].
6. push(9) → stack is [3, 9]. 9 lands where 7 used to be.
7. pop() until empty → returns 9, then 3. One more pop() triggers underflow.

In the visualization, the stack is drawn vertically with thick walls on three sides — the open top is where pushes enter and pops exit. The right-anchor header shows size = N and top = arr[idx] = V, collapsing to "empty" when the stack is empty.

Complexity

Total space: O(n) where n is the number of elements currently in the stack.

Every operation is O(1) because every operation acts on the top end only. No middle access, no scanning. That's the entire reason to choose a stack over, say, a general list: by constraining the interface, you guarantee O(1) cost.

Edge Cases

• Push to a full stack — raises overflow. Bounded stacks are rare in practice; production code usually uses an unbounded list and lets the language runtime grow it.
• Pop from an empty stack — raises underflow. Calling code is expected to guard with is_empty() first, or catch the exception.
• Single-element stack — push then pop returns the same value; size goes 0 → 1 → 0.
• Repeated push of the same value — stacks don't care about duplicates; they're not sets.

Common Mistakes

• Confusing pop with peek. pop mutates — it removes the top. Calling pop "just to look" loses the value if no caller catches the return. Use peek (or index data[-1]) for a non-destructive read.
• Using the wrong end of the array. Stacks must push/pop from the same end. Pushing to the back and popping from the front gives you a queue (FIFO), not a stack.
• Forgetting the empty check. pop() on an empty stack crashes most languages, returns undefined in some. Either way, failing to guard or catch produces a bug far from the actual pop site.
• Reaching past the top. A stack should not expose middle access. If callers start indexing stack.data[k], the LIFO invariant has leaked — switch to a list or a deque instead.
• Recursive code that doesn't realize it's using a stack. Function calls are pushes onto the call stack; returns are pops. A "stack overflow" runtime error is literally the same overflow concept. Translating a recursive algorithm into an explicit stack is often how you escape deep recursion limits.