Understanding Stacks in Detail
A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle: the most recently added element is the first one to be removed. You can only add (push) or remove (pop) elements from one end, called the top. This strict access pattern makes stacks surprisingly powerful for a wide range of problems.
Think of a stack like a pile of plates in a cafeteria. You always take the plate from the top of the pile and add new plates on top. You cannot pull a plate from the middle or bottom without first removing everything above it. This real-world analogy perfectly captures the LIFO behavior.
Stacks are one of the most important data structures in all of computing. Your computer uses a call stack to manage function calls and local variables. Compilers use stacks to parse expressions and check balanced brackets. Web browsers use stacks for the back button. Undo functionality in every text editor is a stack. Despite their simplicity, stacks are tested heavily in coding interviews because they elegantly solve an entire category of problems involving nesting, matching, and backtracking.
How Stacks Work Internally
LIFO Principle
LIFO means the last element pushed onto the stack is the first one to be popped. If you push A, B, C in order, popping gives you C, B, A. This reversal property is fundamental to many stack applications (e.g., reversing a string, undo operations).
Two Implementations
A stack can be implemented using an array or a linked list. Array-based stacks use a "top" index that increments on push and decrements on pop. Linked list-based stacks use the head as the top — push prepends a node, pop removes the head. Both give O(1) push and pop.
The Call Stack
Every running program has a call stack managed by the operating system. When a function is called, a stack frame (containing parameters, local variables, and return address) is pushed. When the function returns, its frame is popped. Stack overflow errors happen when too many frames are pushed (usually from infinite recursion), exceeding the stack memory limit.
Abstract Data Type (ADT)
A stack is an ADT — it defines what operations are available (push, pop, peek, isEmpty) but not how they are implemented. This abstraction means you can swap the underlying implementation (array vs linked list) without changing the code that uses the stack.
Memory Layout
How the stack is stored in memory depends on the underlying implementation choice.
Array-Based Stack
Uses a contiguous block of memory with a top index variable. Push increments top and writes to that index. Pop reads from top and decrements. This is cache-friendly and memory-efficient but has a fixed capacity (or requires amortized resizing for dynamic arrays). Most production stacks use this approach.
Linked List-Based Stack
Uses heap-allocated nodes where each node points to the one below it. Push creates a new node at the head, pop removes the head. There is no capacity limit (besides available memory), but each element carries pointer overhead (8 bytes per node on 64-bit systems) and has poor cache locality.
The System Call Stack
The program call stack is a special region of memory (typically 1-8 MB) that grows downward from high addresses. Each function call pushes a frame containing the return address, saved registers, and local variables. This is not a data structure you create — it is managed by the CPU and OS automatically.
Core Operations Explained
A stack exposes a minimal, elegant interface. Every operation is O(1), making stacks one of the fastest data structures available.
Complexity Analysis
All stack operations are O(1). This is because a stack only ever accesses or modifies the top element — no traversal, no shifting, no searching.
Operation Complexity
| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
| isEmpty | O(1) |
| Size | O(1) |
| Search | O(n) |
Space Complexity
A stack of n elements uses O(n) memory. An array-based stack may have some unused capacity (up to 2x), while a linked list-based stack uses exactly the memory needed plus pointer overhead per node. The choice of backing structure depends on whether you prioritize memory efficiency (array) or unbounded growth (linked list).
Common Interview Patterns
Stack problems appear very frequently in interviews because they elegantly solve matching, nesting, and "nearest previous" problems. These four patterns cover the vast majority of stack questions.
Valid Parentheses (LeetCode 20)
EasyGiven a string containing (, ), {, }, [, ], determine if the input is valid (every open bracket has a matching close bracket in the correct order). This is the classic stack problem and often the first one interviewers ask.
Min Stack (LeetCode 155)
MediumDesign a stack that supports push, pop, top, and retrieving the minimum element — all in O(1) time. Tests your ability to augment a standard data structure with additional capabilities.
Evaluate Reverse Polish Notation (LeetCode 150)
MediumEvaluate an arithmetic expression in Reverse Polish Notation (postfix). This is how calculators and compilers internally evaluate expressions. Tokens are either numbers or operators (+, -, *, /).
Next Greater Element / Monotonic Stack
MediumFor each element in an array, find the next element that is greater. This pattern extends to Daily Temperatures, Stock Span, Largest Rectangle in Histogram, and Trapping Rain Water.
Stack vs Queue
Stacks and queues are the two fundamental restricted-access data structures. The choice between them depends entirely on the required processing order.
| Feature | Stack | Queue |
|---|---|---|
| Order | LIFO — Last In, First Out | FIFO — First In, First Out |
| Primary Use | Backtracking, nesting, undo | Scheduling, BFS, buffering |
| Access Point | Top only (one end) | Front and rear (both ends) |
| Function Calls | Call stack, recursion | Task queues, message queues |
| DFS vs BFS | Stack for Depth-First Search | Queue for Breadth-First Search |
| Implementation | Array or linked list | Array (circular) or linked list |
When to Use Stacks
Use a stack whenever you need to process elements in reverse order, track nested or matching pairs, or implement backtracking. If you find yourself thinking "I need to remember what came before and handle the most recent first," that is a stack.
Expression Parsing
Compilers and calculators use stacks to convert infix expressions to postfix, evaluate postfix expressions, and check balanced parentheses. The shunting-yard algorithm is entirely stack-based.
Undo/Redo Operations
Every text editor, graphic design tool, and IDE uses a stack for undo (pop last action) and a second stack for redo. Each action is pushed, and undoing pops it and pushes it onto the redo stack.
DFS & Backtracking
Depth-First Search on graphs and trees can be implemented iteratively using an explicit stack. Backtracking problems (maze solving, N-Queens, Sudoku) use the call stack implicitly through recursion or an explicit stack.
Common Mistakes to Avoid
Stack Underflow
Calling pop or peek on an empty stack causes a runtime error. Always check isEmpty() before popping. In interviews, explicitly mention this edge case — interviewers look for it.
Using Stack When Queue is Needed
A common mistake is using a stack for BFS (breadth-first search). BFS requires FIFO order — use a queue. Stacks are for DFS. Mixing them up produces incorrect traversal orders.
Stack Overflow in Recursion
Recursive functions use the call stack. Deep recursion (e.g., processing a linked list of 1 million nodes recursively) can overflow the system stack. Convert deep recursion to an iterative approach with an explicit stack to avoid this limit.
Not Recognizing Stack Problems
Many interview problems are stack problems in disguise. Key signals: matching/pairing (brackets, HTML tags), "nearest previous/next" queries, expression evaluation, or any problem where you process items in reverse order. Train yourself to recognize these patterns.