The Core Idea: Last In, First Out
Picture a stack of plates. You add a plate to the top, and when you need one, you take it from the top. You cannot pull a plate from the middle without lifting everything above it. That is a stack: the last item you put in is the first item you get back — last in, first out (LIFO).
This single rule is what makes stacks useful. Whenever a problem has a 'the most recent thing must be handled first' shape — matching brackets, undoing edits, tracking which function called which — a stack captures that ordering for free. It is easiest to feel this when you watch items push on and pop off one at a time.
Push, Pop, and Peek
A stack exposes three operations. Push adds an element to the top. Pop removes and returns the top element. Peek (sometimes called top) reads the top without removing it. Most implementations also offer isEmpty and size. Because all the action happens at one end, each operation runs in O(1) — no shifting or searching required.
Under the hood, a stack is usually a thin wrapper over a dynamic array (a Python list or a JavaScript array) or a singly linked list. With an array you push and pop at the tail; with a linked list you add and remove at the head. The one case to guard is popping from an empty stack — 'stack underflow' — which should raise an error rather than fail silently.
What Stacks Are Good For
Four patterns cover most stack problems. Balanced-parentheses checking pushes each opening bracket and pops when it meets a closing one, verifying the pair matches. A monotonic stack keeps its elements in sorted order to answer 'next greater element' style questions in linear time. Depth-first search and recursion both lean on a stack — an explicit one or the language's call stack — to remember where to backtrack. And undo/redo in an editor is literally two stacks of past states.
class Stack:
def __init__(self):
self._items = []
def push(self, item):
self._items.append(item) # add to top, O(1)
def pop(self):
if not self._items:
raise IndexError("pop from empty stack")
return self._items.pop() # remove top, O(1)
def peek(self):
if not self._items:
raise IndexError("peek from empty stack")
return self._items[-1] # read top, no removal
def is_empty(self):
return not self._items
def __len__(self):
return len(self._items)Array-backed push/pop are amortized O(1): an occasional resize costs O(n) but averages out over many operations. A linked-list backing gives true worst-case O(1) per operation at the cost of an extra pointer per node.
When to use it
- Validating nested structure: parentheses, brackets, HTML/XML tags, or JSON.
- Reversing a sequence, or processing items in the opposite order they arrived.
- Implementing depth-first search, or converting a recursive algorithm into an iterative one.
- Next-greater / next-smaller element and histogram problems solved with a monotonic stack.
Watch out for
- Popping or peeking without first checking for an empty stack, which triggers an underflow error or an out-of-bounds read.
- Reaching into the middle of the stack. If you find yourself indexing elements other than the top, a stack is probably the wrong tool — consider an array, deque, or heap.
- Operating on the slow end. Pushing or popping at the front of a dynamic array is O(n); always work on the end that gives O(1).
Stacks are interview bread and butter, especially at Indian placement drives and product-company loops. The classic warm-up is 'valid parentheses'; from there interviewers escalate to monotonic-stack problems (next greater element, daily temperatures, largest rectangle in a histogram), expression evaluation, and 'design a min-stack that returns the minimum in O(1)'. What they are really testing is whether you recognize the LIFO shape hidden inside a problem, whether you handle the empty-stack edge case cleanly, and whether you can state the O(1) time and O(n) space trade-offs. Being able to rewrite a recursive solution as an explicit stack is a strong signal that you understand how recursion works underneath.