A stack is a collection with one rule: the last thing you put in is the first thing you take out (LIFO — last in, first out). You can only touch the top: push adds to it, pop removes from it, peek looks at it without removing it. That sounds almost too simple to interview on, but interviewers reach for it constantly because so much of computing is secretly a stack — your language runtime's function-call mechanism, the undo button in every editor, the back button in every browser, the recursion your own code performs. If you understand why a stack is the natural fit for "the most recent thing needs to be undone/returned-to/finished first," you understand a large slice of how software actually runs underneath the code you write.
Every time a function is called, the runtime pushes a new "stack frame" holding that call's local variables, its parameters, and the address to resume at when it returns. When the function returns, that frame is popped and control resumes exactly where it left off in the caller's frame, which is now back on top. This has to be LIFO: g cannot finish before f resumes, because f is literally waiting on g's result — the call that started most recently is unavoidably the one that must finish first. That is also why deep, unbounded recursion crashes with a stack overflow: every unreturned call keeps its frame on the stack, and the stack has a fixed size.
This is why a stack is the natural structure to implement recursion iteratively (an explicit stack of "work items" replacing the call stack) and why DFS on a tree or graph — which is really "go deep, then backtrack to the most recent unexplored branch" — is either written with recursion (using the call stack for free) or with an explicit stack.
Both give O(1) push and pop, but for different reasons and with different real costs. An array-backed stack does push/pop at the end, so unlike inserting into the middle of an array, no shifting is required — that's the trick that makes it O(1) instead of the array's usual O(n) insertion. The catch is capacity: a static array can overflow and needs a fixed upper bound decided up front, while a dynamic array (Python's list, Java's ArrayDeque) resizes itself, trading a rare O(n) copy for amortized O(1). A linked-list stack never overflows (barring actual out-of-memory) and never pays a resize cost, but every node is a separate heap allocation with a pointer, which is slower to access due to cache misses and costs extra memory for the pointers themselves. In practice, most languages' default stack/array-list implementations are array-backed, because the resize cost is rare and the cache-friendliness wins on average.
def eval_postfix(tokens):
st = []
for tok in tokens:
if tok.lstrip("-").isdigit():
st.append(int(tok))
else:
b = st.pop()
a = st.pop()
if tok == "+": st.append(a + b)
elif tok == "-": st.append(a - b)
elif tok == "*": st.append(a * b)
elif tok == "/": st.append(a / b)
return st.pop()lstrip("-") also accepts negatives like -5) is pushed.2 1 - the stack is [.., 2, 1], so b = 1, a = 2, and the answer is a - b = 1, not −1.Infix notation (3 + 4 * 2) needs a human or a parser to know that * binds tighter than +, and parentheses to override that when needed. Postfix removes the ambiguity entirely: because every operator appears immediately after the two operands it applies to, a single left-to-right scan with a stack is enough — no lookahead, no precedence rules, no parentheses. That is exactly why calculators, compilers and virtual machines (the JVM, Python's bytecode interpreter) evaluate expressions in a postfix-like form internally: it turns "parse a nested expression tree" into "scan a flat list once."
The evaluation algorithm: scan left to right; push every number; when you hit an operator, pop the top two numbers (second-popped is the left operand, first-popped is the right operand), apply the operator, and push the result back. At the end exactly one value remains on the stack — the answer.
def next_greater_elements(nums):
result = [-1] * len(nums)
st = [] # indices, values decreasing
for i, x in enumerate(nums):
while st and nums[st[-1]] < x:
result[st.pop()] = x
st.append(i)
return resultresult starts as all −1, meaning "no greater element found (yet)".result slot to fill.while nums[st[-1]] < x: the new value x is the first bigger thing to the right of every smaller waiting index, so pop each one and record x.i; it now waits for its own greater element. The stack stays decreasing.A monotonic stack keeps its elements in strictly increasing (or decreasing) order at all times, by popping anything that violates that order before pushing. Here the stack holds indices whose values are decreasing from bottom to top; when a new value arrives that's bigger than the top, every index it pops has just found its "next greater element" — namely the new value — so we record the answer and discard that index for good, it will never be popped or examined again.
The loop looks like nested loops (a while inside a for), which reads like O(n²), but it isn't: every index is pushed onto the stack exactly once and popped at most once across the entire run, not once per outer iteration. Total push operations are n, total pop operations are at most n, so total work is O(n) — this is the classic "amortized analysis via a global counter" argument, the same style of reasoning used to prove dynamic array append is amortized O(1).
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
st = []
for ch in s:
if ch in "([{":
st.append(ch)
elif ch in ")]}":
if not st or st.pop() != pairs[ch]:
return False
return not stpairs maps each closer to the opener it needs.not st) has nothing to close, so fail. Checking this first also stops pop() from crashing.([)] case.return not st: leftover openers like ((( mean something was never closed.Balanced-parentheses checking is the textbook proof that a stack tracks "what still needs to be closed, most-recent-first." Every opening bracket is pushed; every closing bracket must match whatever is currently on top (the most recently opened, still-unclosed bracket) — if it doesn't match, or the stack is empty when a closer arrives, the string is invalid. At the end the stack must be empty, or something was opened and never closed. This exact pattern — "the most recent open thing must close first" — is why a stack (not a queue) is also the right structure for undo/redo (the most recent action is the first one undone), a browser's back button (the most recently visited page is the first one you go back to), and DFS/backtracking (the most recently opened branch is the next one explored when you retreat from a dead end).
push(x): place x at the top and advance the top reference (append to the array, or make x the new head node).pop(): read the value at the top, move the top reference back one position (shrink the array by one, or move head to head.next), and return that value.peek()/top(): return the value at the top without moving anything.is_empty(): true when there is no top element (array length 0, or head is None).An array-backed stack, postfix evaluation, the monotonic-stack Next Greater Element algorithm, and balanced-bracket checking.
class Stack:
"""Array-backed stack using a Python list; append/pop both operate on the end, which is why they're O(1)."""
def __init__(self):
self._data = []
def push(self, x):
self._data.append(x)
def pop(self):
return self._data.pop()
def peek(self):
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def eval_postfix(tokens):
"""Evaluate a postfix (RPN) expression given as a list of tokens."""
st = Stack()
for tok in tokens:
if tok.lstrip("-").isdigit():
st.push(int(tok))
else:
b = st.pop()
a = st.pop()
if tok == "+": st.push(a + b)
elif tok == "-": st.push(a - b)
elif tok == "*": st.push(a * b)
elif tok == "/": st.push(a / b)
return st.pop()
def next_greater_elements(nums):
"""Monotonic decreasing stack: for each element find the next element to its right that's greater."""
result = [-1] * len(nums)
st = [] # holds INDICES, values at those indices are decreasing bottom to top
comparisons = 0
for i, x in enumerate(nums):
while st and nums[st[-1]] < x:
comparisons += 1
result[st.pop()] = x
st.append(i)
return result, comparisons
def is_balanced(s):
pairs = {")": "(", "]": "[", "}": "{"}
st = []
for ch in s:
if ch in "([{":
st.append(ch)
elif ch in ")]}":
if not st or st.pop() != pairs[ch]:
return False
return not st
expr = ["3", "4", "+", "2", "1", "-", "*"]
print("postfix", expr, "=", eval_postfix(expr))
expr2 = ["5", "1", "2", "+", "4", "*", "+", "3", "-"] # 5 + ((1+2)*4) - 3
print("postfix", expr2, "=", eval_postfix(expr2))
nums = [2, 1, 2, 4, 3]
res, cmp_count = next_greater_elements(nums)
print("nums :", nums)
print("NGE :", res)
print("total push+pop comparisons:", cmp_count, "(each index pushed once, popped at most once)")
tests = ["(a+b)*[c-d]", "([)]", "{[()]}", "((("]
for t in tests:
print(f"balanced({t!r}) =", is_balanced(t))
# Output:
# postfix ['3', '4', '+', '2', '1', '-', '*'] = 7
# postfix ['5', '1', '2', '+', '4', '*', '+', '3', '-'] = 14
# nums : [2, 1, 2, 4, 3]
# NGE : [4, 2, 4, -1, -1]
# total push+pop comparisons: 3 (each index pushed once, popped at most once)
# balanced('(a+b)*[c-d]') = True
# balanced('([)]') = False
# balanced('{[()]}') = True
# balanced('(((') = FalseStack wraps a Python list: push is append, pop is pop(), peek reads [-1]. All three touch only the end of the list, so all are O(1).eval_postfix is the code from the postfix diagram, run on two expressions: 7 and 14.next_greater_elements is the monotonic stack from above; it also counts pops (3 here), which never exceed n.is_balanced runs on four strings: two balanced, one with crossed brackets, one with unclosed openers.is_empty() before popping — popping an empty stack is a common source of crashes in bracket-matching and evaluation code.-, /): the second value popped is the left operand, the first value popped is the right operand.while inside a for — it's O(n) because the total number of pushes and pops across the whole run is bounded by n, not by n per outer iteration.Q: Why is a stack the natural structure for function call management?
A: A call can only return after every call it made has returned, so the most recently started, still-unfinished call is always the next one to finish — that's exactly LIFO. Each call pushes a frame with its locals and return address; returning pops that frame and resumes the caller, which is now on top again. Unbounded recursion overflows this stack because frames accumulate faster than they're popped.
Q: Why is postfix notation easier for a computer to evaluate than infix?
A: In postfix every operator directly follows its two operands, so a single left-to-right scan with a stack determines the entire evaluation order — no precedence table and no parentheses are ever needed. Infix requires knowing operator precedence and handling parentheses before you can decide what to compute first, which needs a parser, not just a scan.
Q: Walk through evaluating a postfix expression with a stack.
A: Scan tokens left to right. Push every operand. On an operator, pop the top two values — the first pop is the right operand, the second pop is the left operand — apply the operator, and push the result. For 3 4 + 2 1 - *: push 3, push 4, pop 4 and 3 for + giving 7 and pushing it, push 2, push 1, pop 1 and 2 for - giving 1 and pushing it, then pop 1 and 7 for * giving 7. One value remains: the answer.
Q: What is a monotonic stack, and why does the Next-Greater-Element algorithm run in O(n) total even though it looks like nested loops?
A: A monotonic stack maintains its elements in strictly increasing or decreasing order by popping anything that would break that order before pushing the new element. In NGE, every index is pushed exactly once and popped at most once over the algorithm's entire run — not once per outer-loop iteration — so total stack operations are bounded by 2n, giving O(n) overall despite the visually nested while-inside-for.
Q: How would you check if a string of parentheses is balanced using a stack?
A: Push every opening bracket. On a closing bracket, it must match whatever is on top of the stack (pop and compare) — a mismatch, or a closing bracket with nothing on the stack, means unbalanced immediately. After scanning the whole string, it's balanced only if the stack is empty (nothing was left unclosed).
Q: What's a real-world example where a stack is clearly the right structure, and why not a queue?
A: Undo in a text editor: pressing undo should reverse the most recently performed action, not the very first action you took in the session — that's LIFO, so a stack of actions is correct. A queue would undo actions in the order they were originally done (oldest first), which is the opposite of what "undo" means.
Follow-up: What breaks if you implement undo with a queue instead of a stack?
A: The first undo would revert your very first edit instead of your latest one, which is not what any user expects from "undo" — it would need to drain the entire queue to reach the most recent action, or you'd have to reverse the queue's iteration order, at which point you've effectively rebuilt a stack anyway.
Follow-up: Can you implement a queue using two stacks? Roughly how?
A: Yes — keep an "in" stack for enqueues and an "out" stack for dequeues; when the out stack is empty, pop everything off the in stack and push it onto the out stack, which reverses the order so the oldest enqueued element ends up on top of the out stack. This is covered in full on the queues page; the key insight is that each element only ever gets transferred once, so it's still amortized O(1) per operation.
Follow-up: How would you design a stack that also supports getMin() in O(1)?
A: Keep a second, auxiliary stack alongside the main one that tracks the minimum seen so far at each depth — push the current minimum (either the new value or the previous minimum, whichever is smaller) onto it every time you push onto the main stack, and pop from both together. Each stack stays perfectly in sync, so the top of the min-stack is always the minimum of exactly what's currently in the main stack, in O(1) time and O(n) extra space.
A stack is the wrong choice whenever you need anything other than "access the most recently added item." If you need first-in-first-out processing — serving requests in arrival order, breadth-first traversal, task scheduling by arrival — a queue is correct and a stack will silently give you the wrong order rather than erroring. If you need to access arbitrary elements by position or search efficiently, an array or hash table is the right tool; a stack's restricted interface is a feature when you want to enforce LIFO discipline (and catch bugs where something is accessed out of order), but a liability when you genuinely need random access. And if the real requirement is "process by priority, not by arrival or recency," neither a stack nor a queue is right — that's what a priority queue (a heap) is for.