Stacks
A stack is one of the most fundamental data structures in computer science. Think of a stack of plates in a cafeteria — you can only add or remove plates from the top. This simple constraint makes stacks incredibly powerful for solving many programming problems.
What Is a Stack?#
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first one to be removed.
Real-World Analogies#
- Stack of plates: Add and remove from the top only
- Undo feature: Most recent action is undone first
- Browser back button: Most recently visited page comes first
- Function calls: The most recent function returns first
Key Characteristics#
| Property | Description |
|---|---|
| LIFO Order | Last In, First Out — most recent element is accessed first |
| Single Access Point | Elements are added and removed only from the top |
| Dynamic Size | Can grow and shrink as elements are pushed and popped |
| Restricted Access | Cannot access middle elements directly (only top) |
| Abstract Data Type | Can be implemented using arrays or linked lists |
Stack Operations#
All stack operations work at the top of the stack, making them extremely efficient. Because no element shifting or searching is required, each operation completes in constant time regardless of how many elements the stack contains.
| Operation | Time Complexity | Description |
|---|---|---|
| push(item) | O(1) | Add element to the top |
| pop() | O(1) | Remove and return top element |
| peek() / top() | O(1) | Return top element without removing |
| isEmpty() | O(1) | Check if stack is empty |
| size() | O(1) | Return number of elements |
Visualizing Push and Pop#
Stack Operations
Basic stack operations in Python and JavaScript
Stack Implementation#
While languages provide built-in stack functionality (Python lists, JavaScript arrays), implementing a stack from scratch deepens your understanding of the underlying mechanics.
Array-Based Stack
Implement a stack using a dynamic array
Common Applications#
Stacks are used extensively in programming. Here are the most common applications:
1. Function Call Stack#
When functions call other functions, the system uses a stack to keep track of where to return.
Each entry in the call stack is called a stack frame. It holds the function's local variables, parameters, and a return address — the location in code where execution should resume once the function finishes. This is why deeply recursive functions can cause a stack overflow error: too many frames accumulate and exhaust the memory allocated for the call stack.
2. Undo/Redo Functionality#
Text editors use two stacks to implement undo and redo. When you perform an action (type, delete, format), it is pushed onto the undo stack. Pressing Ctrl+Z pops that action from the undo stack and pushes it onto the redo stack. Pressing Ctrl+Y pops it back from the redo stack and re-applies it. This two-stack design preserves the full action history in both directions — until you take a new action, which clears the redo stack because the future has changed.
3. Expression Evaluation#
Compilers and calculators use stacks to evaluate arithmetic expressions. In postfix notation (also called Reverse Polish Notation), operands are pushed onto the stack one by one; when an operator is encountered, two operands are popped, the operation is applied, and the result is pushed back. For example, 3 4 + means: push 3, push 4, then pop both and push 7. This single-pass approach handles operator precedence without needing parentheses, which is why stacks are central to expression parsing in compilers. Stacks also enable conversion between infix (the familiar a + b), postfix (a b +), and prefix (+ a b) notations.
4. Browser History#
Browsers use two stacks to manage navigation history. As you visit pages, each URL is pushed onto the back stack. Clicking the back button pops the current page off the back stack and pushes it onto the forward stack, restoring the previous page. Clicking forward reverses this. If you navigate to a brand-new page after going back, the forward stack is cleared — which is why forward history disappears the moment you follow a new link.
Classic Stack Algorithms#
Balanced Parentheses#
A fundamental stack problem: check if brackets in a string are properly matched and nested.
Balanced Parentheses
Check if brackets are properly matched using a stack
Reverse a String#
Stacks naturally reverse the order of elements, making string reversal straightforward.
Reverse String Using Stack
Demonstrate LIFO property by reversing a string
Stack vs Other Data Structures#
| Use Case | Best Choice | Why |
|---|---|---|
| LIFO access needed | Stack | Natural fit for undo, parsing, backtracking |
| FIFO access needed | Queue | For breadth-first traversal, scheduling |
| Random access needed | Array | O(1) access to any element |
| Frequent middle insertions | Linked List | O(1) insertion with pointer |
| Both ends access | Deque | O(1) operations at both ends |
When to Use a Stack#
| Scenario | Example |
|---|---|
| Reversing order | Undo operations, reverse strings |
| Matching pairs | Balanced parentheses, HTML tag validation |
| Backtracking | Maze solving, DFS traversal |
| Expression evaluation | Calculator, postfix notation |
| State management | Browser history, navigation |
| Recursive to iterative | Converting recursive algorithms |
Reviewing AI-Generated Code#
Stack code is conceptually straightforward, which means AI tools can generate working solutions quickly. However, AI frequently overlooks critical edge cases — most commonly missing an empty-stack check before a pop or peek, and reversing operand order in non-commutative operations like subtraction and division. When reviewing AI-generated stack code, always trace through boundary inputs: an empty string, a single element, and a sequence that empties the stack partway through.
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Empty stack | Check before pop/peek | Calling pop() without isEmpty check |
| Bracket matching | Correct pairing logic | Not handling all bracket types |
| Stack underflow | Pop more than pushed | Not checking stack size before pop |
| Return values | What pop() returns | Confusing pop() and peek() |
| Expression evaluation | Operator precedence | Wrong order of operands |
Spotting AI Stack Bugs
Common errors in AI-generated stack solutions
Summary#
| Concept | Key Takeaway |
|---|---|
| LIFO Principle | Last In, First Out — most recent element accessed first |
| Core Operations | push(), pop(), peek() — all O(1) time |
| Implementation | Easily implemented with arrays or linked lists |
| Key Applications | Function calls, undo/redo, expression parsing |
| Balanced Brackets | Classic problem solved elegantly with stacks |
| Natural Reversal | Stacks inherently reverse the order of elements |
The stack is simple yet powerful. Its LIFO property makes it the perfect tool for tracking state, reversing sequences, and matching pairs. Master the stack, and you'll have a versatile tool for solving many algorithmic challenges!