A stack is a linear data structure that enforces last-in, first-out (LIFO) access — elements are inserted (pushed) and removed (popped) only from one end (the top) — providing O(1) push, pop, and peek.
A stack is a pile: you can only add to the top and remove from the top — the last thing you put in is always the first thing you take out.
Last-in, first-out (LIFO)
A stack enforces one rule: you can only interact with the top. Push adds an item to the top. Pop removes and returns the top item. Peek looks at the top item without removing it. This constraint is LIFO — the most recently pushed item is always the one that gets popped next.
from collections import deque
# Python list as a stack (append/pop at end — O(1))
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
stack.append(30) # push 30
print(stack[-1]) # peek: 30 (top)
print(stack.pop()) # pop: 30
print(stack.pop()) # pop: 20
print(stack) # [10]Complexity table
| Operation | Average | Worst | Notes |
|---|---|---|---|
| Push (insert at top) | O(1) | O(1) | Add to top |
| Pop (remove from top) | O(1) | O(1) | Remove from top |
| Peek / Top | O(1) | O(1) | Read without removing |
| Search | O(n) | O(n) | No random access; must pop |
| Space | O(n) | O(n) |
Where stacks appear
The call stack is a stack — every function call pushes a frame; every return pops it. Stack overflow is when it gets full. Undo/redo: every edit pushes an action onto the undo stack; undoing pops it. Browser back button: each page visit pushes the URL; back pops it. Expression evaluation: parsing 3 + 4 * 5 correctly uses a stack for operator precedence. Balanced parentheses checking: push on open bracket, pop on close, check match.
def is_balanced(s):
stack = []
pairs = {")":"(", "]":"[", "}":"{"}
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in ")]}":
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0
print(is_balanced("({[]})")) # True
print(is_balanced("({[})")) # FalseImplementing a stack using an array vs. linked list
Array-backed stack (Python list, Java ArrayList): push/pop at end — O(1) amortised. Cache-friendly; all operations touch the same cache line. Linked list stack: push/pop at head — O(1) exact. No reallocation, but worse cache performance. For most uses, array-backed is faster in practice.
import java.util.ArrayDeque;
import java.util.Deque;
// Java: use ArrayDeque, not legacy Stack class
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10); // O(1)
stack.push(20);
stack.push(30);
System.out.println(stack.peek()); // 30 — top
System.out.println(stack.pop()); // 30 — removed
// ArrayDeque is faster than Stack (no synchronisation overhead)Depth-first search (DFS) and the stack
Recursive DFS uses the call stack implicitly. Iterative DFS replaces the call stack with an explicit stack. Push the start node; repeatedly: pop, process, push unvisited neighbours. The LIFO order ensures the algorithm explores one path as deeply as possible before backtracking — identical to recursive DFS but without risk of stack overflow.
def dfs_iterative(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop() # LIFO
if node not in visited:
visited.add(node)
print(node, end=" ")
for neighbour in graph[node]:
if neighbour not in visited:
stack.append(neighbour)append() and pop() at the end are both O(1). But collections.deque is more explicit and offers O(1) operations at both ends.Stack class is deprecated. Java's legacy java.util.Stack extends Vector, which is synchronised — adding overhead to every operation. Use ArrayDeque as a stack in modern Java code.The operand stack in the JVM
The Java Virtual Machine is a stack-based virtual machine. Each JVM thread has an operand stack (separate from the call stack) that bytecode instructions operate on directly. iadd pops two integers from the operand stack, adds them, and pushes the result. invokevirtual pushes a new stack frame for the called method. This stack-based architecture simplifies the JVM specification and allows the JVM to run on machines with any register set. Contrast with register-based VMs (Dalvik/ART on Android) which map operations directly to registers.
Monotonic stacks
A monotonic stack is a stack that maintains elements in a monotonically increasing or decreasing order. When pushing a new element, pop all elements that violate the ordering first. Used for O(n) algorithms that would otherwise be O(n²): "next greater element," "largest rectangle in histogram" (Cormen et al. exercise 6.5-6), "trapping rainwater." The key insight: each element is pushed and popped at most once — O(n) total even though there is a nested loop in the code.
CLRS (4th ed.), §10.1 — Stacks and queues. JVM Specification §2.6 — Frames (operand stack). Knuth TAOCP Vol. 1, §2.2.1 — Sequential allocation.