Stacks and their operations
Precise definitions, operations, array/linked implementations, overflow/underflow, algorithms, complexities, and classic applications of stacks with runnable Python examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Engineers use stacks to manage last-in-first-out (LIFO) workflows such as function calls (the runtime call stack), undo/redo in editors, backtracking in AI search, and expression evaluation in compilers and calculators. Understanding stacks ensures you can implement and reason about recursion, parsing, depth-first search, and many algorithms that require controlled reversal of order.
Key ideas
Definition — LIFO property: If elements are pushed in the order a1, a2, …, an, they are popped in the reverse order an, …, a2, a1.
Definition — Stack ADT: A specification with the following operations (names may vary by language):
- push(x): Insert element x at the top.
- pop(): Remove and return the top element. Precondition: stack is not empty.
- peek() / top(): Return (but do not remove) the top element. Precondition: stack is not empty.
- isEmpty(): Return true if the stack has no elements.
- isFull() (for fixed-capacity implementations): Return true if no more elements can be pushed.
- Optional: size(): Return the number of elements.
Definition — Overflow: An error condition when push is attempted on a full stack (only relevant for fixed-capacity representations like arrays without dynamic growth).
Definition — Underflow: An error condition when pop (or peek) is attempted on an empty stack.
Complexity laws (RAM model assumptions):
- push, pop, peek run in O(1) time.
- isEmpty, isFull, size run in O(1) time.
- Space is O(n) for n elements stored. Assumptions: random access to array cells is O(1); pointer operations are O(1); dynamic array append at the end is amortized O(1). For a linked-list stack, size() is O(1) only if a separate count is maintained; otherwise computing size by traversal is O(n).
Representation 1 — Array-based stack (static capacity):
- Data: array A[0..capacity−1], integer top index.
- Initialization: top = −1 (stack empty).
- Invariants: 0 ≤ top ≤ capacity−1 when non-empty; elements occupy A[0..top]; the current top element is at A[top].
- Conditions: isEmpty ⇔ top = −1; isFull ⇔ top = capacity−1.
- Algorithms:
- push(x): if isFull → overflow; else top ← top+1; A[top] ← x.
- pop(): if isEmpty → underflow; else x ← A[top]; top ← top−1; return x.
- peek(): if isEmpty → underflow; else return A[top].
Representation 2 — Linked-list-based stack:
- Data: singly linked list with head pointer referencing the top node. Each node has fields (data, next).
- Initialization: head = null.
- Invariants: head points to the most recently pushed node, and following next pointers enumerates the stack from top to bottom.
- Algorithms:
- push(x): create node N with N.data ← x, N.next ← head; head ← N.
- pop(): if head = null → underflow; else x ← head.data; head ← head.next; free removed node; return x.
- peek(): if head = null → underflow; else return head.data.
- This has no overflow unless memory is exhausted.
Correctness invariant for both representations: After any sequence of pushes and pops, the object returned by peek() (if any) is exactly the most recently pushed item that has not been popped. Proof sketch by induction on operation sequence length: base case (empty) holds; push maintains invariant by moving top to new element; pop maintains by removing current top and exposing previous one.
Common applications (know the mapping from problem to stack):
- Parentheses/brackets matching: push opening brackets; when a closing bracket arrives, check top has matching type; at the end stack must be empty.
- Infix→postfix (Reverse Polish) conversion: use operator stack to handle precedence and associativity; output operands in order; pop operators according to rules.
- Postfix expression evaluation: scan tokens left to right; push operands; on operator, pop required operands, compute, push result; final stack has single result.
- Recursion and call stack: each function call pushes an activation record; return pops it. This explains how local variables and return addresses are managed.
- DFS and backtracking: push next nodes/choices; pop to backtrack.
Overflow/underflow detection derivation for array-based stack:
- We assert empty ⇔ top = −1 (by initialization and only increments/decrements by push/pop). Therefore underflow occurs exactly when pop or peek is called with top = −1.
- We assert full ⇔ top = capacity−1 (since top increases by one per push and cannot exceed last valid index). Therefore overflow occurs exactly when push is called with top = capacity−1.
What to draw for exam diagrams:
- Array-based stack snapshot: draw a vertical column of boxes labeled A[0] at bottom up to A[capacity−1] at top; shade or mark boxes up to index top; draw an arrow labeled “top” pointing at the current top index. Also annotate values inside boxes and show capacity.
- Linked-list stack: draw nodes as boxes with two fields (data | next). The left field shows the element; the right shows an arrow to the next node. Draw a pointer labeled “head/top” pointing to the first node. If empty, draw head/top → null.
- Operator stack during infix→postfix: two areas — an output list (queue/line) and a stack drawn as above. Show pushing and popping of operators with precedence labels (e.g., ^ higher than *,/ higher than +,−), and indicate associativity (e.g., ^ is right-associative).
Precedence and associativity rules used in conversion/evaluation (typical in programming languages and exam problems):
- Highest to lowest precedence: ^, then *, /, then +, −.
- Associativity: ^ is right-associative; *, /, +, − are left-associative. Assumption: operands are symbols (identifiers) or numbers; unary operators are not handled unless specified.
Error handling policy to state in answers: Underflow and overflow should be detected and reported; undefined operations (e.g., division by zero in evaluation) should be reported as errors; after an error, the stack’s representation invariants must still hold (do not partially modify top/head).
Formulas
This is a programming topic. Remember these signatures/syntax and invariants:
push(x)— insert x at top; pre: not full (if fixed-capacity); post: top element becomes x.y = pop()— remove and return top; pre: not empty; post: size decreases by 1.t = peek()— read top; pre: not empty; post: stack unchanged.isEmpty()— true iff size == 0.isFull()— true iff size == capacity (fixed-capacity only).- Array stack invariants:
-1 ≤ top ≤ capacity − 1,isEmpty ⇔ top = −1,isFull ⇔ top = capacity − 1. - Linked stack invariants:
head = null ⇔ empty,headpoints to most recently pushed node. - Time costs (RAM model):
cost(push) = Θ(1),cost(pop) = Θ(1),cost(peek) = Θ(1). - Python list-at-end operations:
stack.append(x)for push;stack.pop()for pop;stack[-1]for peek. - Python deque operations:
dq.append(x),dq.pop(),dq[-1]— O(1) at ends.
Worked examples
Example 1 — Postfix (Reverse Polish) expression evaluation using a stack Assumptions: tokens are space-separated; operands are integers; operators are +, -, *, /, ^; division uses true division but the sample yields an integer.
Python program:
# Evaluate a postfix expression using a stack
# Input: one line, space-separated tokens (integers and operators + - * / ^)
# Output: the final value
def apply(op, b, a): # note: a is the left operand, b is the right operand
if op == '+':
return a + b
if op == '-':
return a - b
if op == '*':
return a * b
if op == '/':
return a / b # true division
if op == '^':
return a ** b
raise ValueError(f"Unknown operator: {op}")
def evaluate_postfix(expr):
stack = []
for tok in expr.strip().split():
if tok.lstrip('-').isdigit():
stack.append(int(tok))
else:
if len(stack) < 2:
raise ValueError("Underflow: not enough operands")
b = stack.pop()
a = stack.pop()
res = apply(tok, b, a)
stack.append(res)
if len(stack) != 1:
raise ValueError("Invalid expression: stack should contain exactly one result")
return stack.pop()
if __name__ == "__main__":
expr = input().strip()
val = evaluate_postfix(expr)
# Print as int if it is mathematically an integer, else as float
if isinstance(val, float) and val.is_integer():
print(int(val))
else:
print(val)
Sample input:
10 2 8 * + 3 -
Exact output:
23
Explanation (stack trace): push 10; push 2; push 8; see '': pop 8,2 → 28=16 push; see '+': pop 16,10 → 10+16=26 push; see '-': pop 3,26 → 26-3=23 push; end → 23.
Example 2 — Infix to postfix conversion using a stack (Shunting-yard) Assumptions: operands are single letters or digits without spaces; operators are +, −, *, /, ^; parentheses allowed; ^ is right-associative.
Python program:
# Convert infix to postfix (Reverse Polish) using operator stack
# Input: one line string (e.g., (A+B)*C-(D-E)^(F+G))
# Output: postfix string (e.g., AB+C*DE-FG+^-)
def precedence(op):
if op == '^':
return 3
if op in ('*', '/'):
return 2
if op in ('+', '-'):
return 1
return 0
def is_right_associative(op):
return op == '^'
def infix_to_postfix(s):
out = []
st = [] # operator stack
for ch in s.strip():
if ch.isalnum(): # operand
out.append(ch)
elif ch == '(': # left parenthesis
st.append(ch)
elif ch == ')': # pop until matching '('
while st and st[-1] != '(':
out.append(st.pop())
if not st:
raise ValueError("Mismatched parentheses")
st.pop() # discard '('
else: # operator
while st and st[-1] != '(':
top = st[-1]
if (precedence(top) > precedence(ch)) or \
(precedence(top) == precedence(ch) and not is_right_associative(ch)):
out.append(st.pop())
else:
break
st.append(ch)
while st:
if st[-1] in '()':
raise ValueError("Mismatched parentheses")
out.append(st.pop())
return ''.join(out)
if __name__ == "__main__":
expr = input().strip()
print(infix_to_postfix(expr))
Sample input:
(A+B)*C-(D-E)^(F+G)
Exact output:
AB+C*DE-FG+^-
Example 3 — Balanced parentheses/brackets checker Assumptions: brackets allowed: (), {}, []. Any other characters are ignored.
Python program:
# Check if brackets in a string are balanced using a stack
# Input: one line string (e.g., {[()]})
# Output: Balanced OR Not Balanced
pairs = {')': '(', ']': '[', '}': '{'}
def is_balanced(s):
st = []
for ch in s:
if ch in '([{':
st.append(ch)
elif ch in ')]}':
if not st or st[-1] != pairs[ch]:
return False
st.pop()
return len(st) == 0
if __name__ == "__main__":
s = input().strip()
print("Balanced" if is_balanced(s) else "Not Balanced")
Sample input:
{[()]}
Exact output:
Balanced
Model theory to remember (summarised):
- The stack ADT has O(1) push/pop/peek; array vs linked implementations differ by overflow behavior and memory layout; typical applications include expression parsing/evaluation, recursion support, DFS/backtracking, and delimiter matching.
Common mistakes
- Off-by-one errors in array index: initializing top = 0 instead of −1; confusing isFull condition.
- Reversing operand order during postfix evaluation: computing b op a instead of a op b after popping (remember second pop is left operand a, first pop is right operand b).
- Mishandling associativity in infix→postfix: treating ^ as left-associative and incorrectly popping equal-precedence operators.
- Forgetting to empty remaining operators from stack at end of infix traversal.
- Not checking for mismatched parentheses (leftover '(' on stack or trying to pop past it).
- In Python, using list.pop(0) or insert(0, x) which are O(n); for stacks, always operate at the end: append/pop() only.
- Printing float with .0 when the exam expects integer; decide and state the evaluation rule, or choose inputs that yield integers.
For your exam
- Short notes: Compare array vs linked implementations — initialization, memory use, overflow behavior, typical use-cases, invariants. Include a neat diagram with labels (array indices, top/head pointer).
- Algorithms: Write pseudocode for push/pop/peek for both representations; include pre/post-conditions and error handling. Derive isEmpty/isFull conditions and justify using invariants.
- Programs: Implement postfix evaluation; infix→postfix conversion with precedence/associativity; balanced parentheses checker. Include sample inputs/outputs and explain a few stack states.
- Applications: Explain how the call stack supports recursion; how DFS can be implemented with an explicit stack. Reference related topics by name (e.g., Expression conversion and postfix evaluation; Graph traversal: DFS and BFS; Recursion and the stack) without re-teaching them.
- Diagrams: Draw array-based and linked-list stacks clearly, with “top”/“head” labels, and show a push/pop step.
- Scoring tips: State assumptions (operand set, operator precedence/associativity), mention complexity O(1) per op, and handle edge cases (underflow/overflow, mismatched parentheses).
Quick check
- In an array-based stack of capacity 5 with top = 3, which indices hold valid elements and what is the next index written by push?
- During infix→postfix, when the current token is '+' and the stack top is '*', should you pop the stack? Explain in one line.
- While evaluating the postfix expression "5 1 2 + 4 * + 3 -", what is the final result?
Answers: 1) Valid: indices 0 to 3; next push writes index 4. 2) Yes; '' has higher precedence than '+', so pop '' to output before pushing '+'. 3) 14.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?