Stack
Last-In First-Out — the structure behind function calls, expression evaluation, and backtracking. The monotonic stack pattern alone appears in dozens of interview problems.
What is a Stack?
A stack is a linear data structure where all insertions and removals happen at the same end, called the top. The Last-In First-Out (LIFO) discipline means the most recently added element is always removed first — like a stack of plates where you always take from the top.
The call stack is the most pervasive stack in computing: every function call pushes a new frame with its local variables and return address, and returning from a function pops that frame. Stack overflow errors occur when recursion is too deep and the call stack runs out of memory. Beyond the call stack, stacks power undo/redo systems, browser navigation history, compiler bracket matching, and iterative depth-first search.
Applications
Operating systems use the call stack to track the active chain of function invocations and to implement interrupts. Text editors maintain an undo stack of operations; a redo stack holds undone actions. Compilers parse arithmetic expressions and check bracket matching with stacks. Web browsers keep a navigation stack so the back button always returns to the previous page. DFS graph traversal can replace recursion with an explicit stack to avoid call-stack overflow on large graphs.
Representations
The most performant stack in Rust uses Vec<T> as the backing store. Push appends to the end; pop removes from the end. Both are O(1) amortised with excellent cache locality because elements are contiguous in memory.
struct Stack<T> {
data: Vec<T>,
}
impl<T> Stack<T> {
fn new() -> Self {
Stack { data: Vec::new() }
}
fn push(&mut self, val: T) {
self.data.push(val);
}
fn pop(&mut self) -> Option<T> {
self.data.pop()
}
fn peek(&self) -> Option<&T> {
self.data.last()
}
fn is_empty(&self) -> bool {
self.data.is_empty()
}
fn size(&self) -> usize {
self.data.len()
}
}
fn main() {
let mut s: Stack<i32> = Stack::new();
s.push(1); s.push(2); s.push(3);
println!("top: {:?}", s.peek()); // Some(3)
println!("pop: {:?}", s.pop()); // Some(3)
println!("top: {:?}", s.peek()); // Some(2)
}A linked-list-backed stack avoids amortised cost — every push is strictly O(1) — but has higher constant factors due to per-node heap allocation. For nearly all practical purposes, the Vec-backed variant is faster because of cache locality.
Operations and Time Complexity
| Operation | Time | Space | Notes |
|---|---|---|---|
| push | O(1) amortised | O(1) | O(n) on capacity doubling, rare |
| pop | O(1) | O(1) | Returns None if empty |
| peek / top | O(1) | O(1) | Borrow top element without removing |
| is_empty | O(1) | O(1) | |
| size | O(1) | O(1) | |
| search | O(n) | O(1) | Linear scan from top |
Fundamental Algorithms and Problems
Balanced Parentheses
Determine whether a string of brackets ()[]{} is valid. Push every opening bracket. When a closing bracket arrives, the top of the stack must be its matching opener — pop and continue. If the stack is empty when a closer arrives, or the top does not match, the string is invalid. A valid string leaves an empty stack after processing all characters.
fn is_valid(s: &str) -> bool {
let mut stack: Vec<char> = Vec::new();
for ch in s.chars() {
match ch {
'(' | '[' | '{' => stack.push(ch),
')' => if stack.pop() != Some('(') { return false; },
']' => if stack.pop() != Some('[') { return false; },
'}' => if stack.pop() != Some('{') { return false; },
_ => {}
}
}
stack.is_empty()
}
fn main() {
println!("{}", is_valid("({[]})")); // true
println!("{}", is_valid("([)]")); // false
println!("{}", is_valid("{[")); // false
}Next Greater Element
For each element in an array, find the first element to its right that is strictly greater. The O(n²) approach checks every pair. The monotonic stack approach maintains a stack of indices whose next-greater element has not yet been found, keeping them in decreasing order of value. Scanning left to right: pop every index whose value is less than the current element — the current element is their answer — then push the current index. Elements still on the stack when the scan ends have no greater element to their right.
fn next_greater(arr: &[i32]) -> Vec<i32> {
let n = arr.len();
let mut result = vec![-1i32; n];
let mut stack: Vec<usize> = Vec::new(); // indices, decreasing value order
for i in 0..n {
while let Some(&top) = stack.last() {
if arr[top] < arr[i] {
result[top] = arr[i];
stack.pop();
} else {
break;
}
}
stack.push(i);
}
result
}
fn main() {
let arr = [4, 5, 2, 10, 8];
println!("{:?}", next_greater(&arr)); // [5, 10, 10, -1, -1]
}Evaluate Reverse Polish Notation
Reverse Polish Notation places operators after their operands: ["2","1","+","3","*"] means (2+1)*3 = 9. Push numbers onto the stack. When an operator arrives, pop two operands (the second pop is the left operand), apply the operation, and push the result. The final element on the stack is the answer. This evaluation strategy is how many stack-based virtual machines (JVM, CPython) execute bytecode.
fn eval_rpn(tokens: &[&str]) -> i32 {
let mut stack: Vec<i32> = Vec::new();
for &t in tokens {
match t {
"+" | "-" | "*" | "/" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
stack.push(match t {
"+" => a + b,
"-" => a - b,
"*" => a * b,
_ => a / b,
});
}
_ => stack.push(t.parse().unwrap()),
}
}
stack[0]
}
fn main() {
println!("{}", eval_rpn(&["2","1","+","3","*"])); // 9
println!("{}", eval_rpn(&["4","13","5","/","+"])); // 6
println!("{}", eval_rpn(&["10","6","9","3","+","-11","*","/","*","17","+","5","+"])); // 22
}Min Stack
Design a stack that supports push, pop, top, and get_min, all in O(1). The key insight: maintain a parallel min-stack. Each element of the min-stack records the minimum value in the main stack at that depth. When pushing, push min(val, current_min) onto the min-stack. When popping, pop both stacks in tandem. The top of the min-stack is always the current minimum — no searching required.
struct MinStack {
data: Vec<i32>,
mins: Vec<i32>,
}
impl MinStack {
fn new() -> Self {
MinStack { data: Vec::new(), mins: Vec::new() }
}
fn push(&mut self, val: i32) {
let current_min = self.mins.last().copied().unwrap_or(i32::MAX);
self.data.push(val);
self.mins.push(val.min(current_min));
}
fn pop(&mut self) -> Option<i32> {
self.mins.pop();
self.data.pop()
}
fn top(&self) -> Option<i32> {
self.data.last().copied()
}
fn get_min(&self) -> Option<i32> {
self.mins.last().copied()
}
}
fn main() {
let mut s = MinStack::new();
s.push(5); s.push(3); s.push(7); s.push(1); s.push(4);
println!("min: {:?}", s.get_min()); // Some(1)
s.pop(); // removes 4
println!("min: {:?}", s.get_min()); // Some(1)
s.pop(); // removes 1
println!("min: {:?}", s.get_min()); // Some(3)
}Largest Rectangle in Histogram
Given bar heights, find the area of the largest rectangle that fits entirely within contiguous bars. The monotonic stack approach maintains a stack of bar indices in increasing height order. When a bar shorter than the stack's top is encountered, the top bar cannot extend further right. Pop it and compute the rectangle it forms: height is heights[popped], width extends from the new stack top (exclusive) to the current index (exclusive). Appending a sentinel height of 0 at the end ensures all bars are processed.
fn largest_rectangle(heights: &[i32]) -> i32 {
let n = heights.len();
let mut stack: Vec<usize> = Vec::new();
let mut max_area = 0i32;
for i in 0..=n {
let h = if i == n { 0 } else { heights[i] };
while let Some(&top) = stack.last() {
if heights[top] > h {
stack.pop();
let width = match stack.last() {
Some(&prev) => i - prev - 1,
None => i,
};
max_area = max_area.max(heights[top] * width as i32);
} else {
break;
}
}
stack.push(i);
}
max_area
}
fn main() {
println!("{}", largest_rectangle(&[2,1,5,6,2,3])); // 10
println!("{}", largest_rectangle(&[2,4])); // 4
}