Stacks
A stack is a last-in, first-out collection: the most recently added item is the first removed. This simple rule models undo histories, function calls, and nested structures.
The stack ADT
A stack supports push (add an item to the top), pop (remove and return the top item), and peek or top (look at the top item without removing it), plus isEmpty. Only the top is accessible. The order is LIFO: last in, first out, like a pile of plates where you take the one you put on most recently.
Implementations
A dynamic array makes a natural stack: push appends to the end and pop removes from the end, both O(1) amortised. A singly linked list also works, pushing and popping at the head in O(1) worst case. Python programmers simply use a list with append and pop; Java offers ArrayDeque, and C++ std::stack.
Errors and edge cases
Popping or peeking an empty stack is an error, called underflow, and code must check isEmpty first or handle the exception. A fixed-capacity stack can overflow when full. The term 'stack overflow' for runaway recursion comes from the call stack running out of space.
The call stack
Programs use a stack to manage function calls. Each call pushes a frame holding parameters, local variables, and the return address; returning pops it. Recursion works because each call has its own frame. Any recursive algorithm can be rewritten iteratively with an explicit stack, which avoids call-stack depth limits.
Balanced brackets
To check whether brackets such as (), [], and {} are balanced, scan the text: push each opening bracket; on a closing bracket, pop and check that it matches. If a pop finds the wrong type or an empty stack, or the stack is non-empty at the end, the text is unbalanced. Compilers and editors use the same idea for nested code.
Evaluating expressions
In postfix notation (reverse Polish notation), operators follow their operands: 3 4 + 2 * means (3 + 4) x 2. A stack evaluates it: push numbers; on an operator, pop two operands, apply it, and push the result. Dijkstra's shunting-yard algorithm uses a stack of operators to convert ordinary infix expressions into postfix, respecting precedence.
Other uses
Undo and redo features keep stacks of actions. Browsers keep a back stack of visited pages. Depth-first search uses a stack, explicitly or through recursion. Backtracking algorithms, such as maze solving and puzzle search, push choices and pop them to retreat from dead ends.
Worked example
Evaluate 5 1 2 + 4 * + 3 -. Push 5, 1, 2. '+' pops 2 and 1, pushes 3: stack [5, 3]. Push 4: [5, 3, 4]. '*' pops 4 and 3, pushes 12: [5, 12]. '+' pops 12 and 5, pushes 17: [17]. Push 3, then '-' pops 3 and 17 and pushes 17 - 3 = 14. The result is 14, the value of 5 + (1 + 2) x 4 - 3.
Key takeaways
A stack is LIFO with push, pop, peek, and isEmpty, all O(1). Implement it with a dynamic array (end) or a linked list (head). Guard against underflow and overflow. The call stack holds a frame per function call; recursion can be replaced by an explicit stack. Stacks check balanced brackets, evaluate postfix expressions, and power shunting-yard parsing, undo, browser history, depth-first search, and backtracking.
Flashcard
Last-in, first-out collection
Check your understanding
Which bracket string would the stack-based check reject?