Stack Implementation and Applications
A stack is a Last-In-First-Out (LIFO) data structure. While conceptually simple, the choice of underlying implementation affects memory and performance. Stacks are the foundation of recursion, parsing, and expression evaluation.
Array vs Linked List Backing
An array-backed stack keeps a top index. Pushing increments top and writing to the array. It is highly cache-friendly but occasionally suffers an O(N) resize penalty.
A linked-list-backed stack pushes by inserting a new node at the head. It never resizes, meaning strictly O(1) operations, but it suffers from memory fragmentation and the overhead of node allocation.
- Array: Fast, cache-friendly, amortized O(1)
- Linked List: No resizing, fragmented memory, strict O(1)
- Both implementations hide the underlying structure
Validating Parentheses
A classic stack application is checking if a string of brackets (e.g., {[()]}) is valid. As you scan the string, every opening bracket is pushed onto the stack.
When a closing bracket is encountered, you pop the top of the stack and check if it matches. If the stack is empty too early, or not empty at the end, the string is invalid.
- Push opening brackets
- Pop and match closing brackets
- Ensures correct nesting and order
Terms, operations, and practical uses
Core operations
- PushAdding an element to the top of the stack. O(1) time complexity.
- PopRemoving and returning the element at the top of the stack. O(1) time complexity.
- Peek / TopLooking at the element on the top of the stack without removing it.
Implementation details
- Array BackingUsing a dynamic array and an integer 'top' index. Extremely cache-friendly but occasionally requires O(N) resizing.
- Linked List BackingInserting and removing strictly at the 'head' node. No resizing overhead, but causes memory fragmentation.
- Stack OverflowAn error that occurs when a stack exceeds its allocated memory limit, most famously caused by infinite recursion.
Practical applications
- Call StackThe internal structure used by the OS and runtime to track active function calls, local variables, and return addresses.
- Expression ParsingUsing stacks to validate nested parentheses, brackets, or XML/HTML tags.
- Shunting-YardDijkstra's algorithm for parsing mathematical equations from human-readable Infix notation to machine-friendly Postfix notation.
Validating Parentheses
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs.keys():
if not stack or stack[-1] != pairs[char]:
return False
stack.pop()
return len(stack) == 0
print('Valid:', is_valid("{[()]}"))#include <iostream>
#include <stack>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (pairs.count(c)) {
if (st.empty() || st.top() != pairs[c]) return false;
st.pop();
}
}
return st.empty();
}
int main() {
cout << (isValid("{[()]}") ? "True" : "False") << endl;
return 0;
}import java.util.*;
class Main {
public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.peek() != pairs.get(c)) return false;
stack.pop();
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println(isValid("{[()]}"));
}
}String: '{ [ ( ) ] }'Valid: TrueRun the example step by step
Expression Evaluation
Computers evaluate mathematical expressions using stacks. Expressions are often converted from Infix (e.g., 3 + 4) to Postfix/Reverse Polish Notation (e.g., 3 4 +) using the Shunting-Yard algorithm.
To evaluate Postfix, you push numbers onto a stack. When an operator is encountered, you pop the top two numbers, apply the operator, and push the result back.
- Infix is for humans, Postfix is for machines
- Shunting-Yard converts Infix to Postfix
- Postfix evaluation uses a single operand stack
Call Stack and Recursion
The most ubiquitous stack is the Call Stack used by the operating system and programming languages to manage function calls. When a function is called, its local variables and return address are pushed.
When the function finishes, its frame is popped, and execution resumes at the return address. Recursion is simply a process pushing its own function onto the call stack repeatedly.
- Tracks active function calls
- Stores local variables and parameters
- Stack Overflow occurs when recursion is too deep