A stack is a Last In, First Out (LIFO) data structure. The last thing we put in is the first thing we take out. Think of a stack of plates — we always add and remove from the top.
In simple language, a stack is a collection where we can only interact with the top element. We push things on, we pop things off. That’s it.
Stack Operations
Every stack supports these core operations, all in O(1) time:
- push(item) — add to the top
- pop() — remove from the top
- peek() / top() — look at the top without removing
- isEmpty() — check if the stack is empty
Using Stacks in Each Language
We don’t usually build stacks from scratch. Every language has a built-in way to use one.
// JavaScript -- just use an array
const stack = [];
stack.push(10); // push
stack.push(20);
stack.push(30);
stack.pop(); // 30 -- removes from top
stack[stack.length - 1]; // 20 -- peek at top
stack.length === 0; // false -- isEmpty check# Python -- just use a list
stack = []
stack.append(10) # push
stack.append(20)
stack.append(30)
stack.pop() # 30 -- removes from top
stack[-1] # 20 -- peek at top
len(stack) == 0 # False -- isEmpty check// Java -- use ArrayDeque (faster than Stack class)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10); // push
stack.push(20);
stack.push(30);
stack.pop(); // 30 -- removes from top
stack.peek(); // 20 -- peek at top
stack.isEmpty(); // false -- isEmpty checkJava note: Don’t use java.util.Stack — it’s a legacy class from Java 1.0 with thread synchronization overhead. Use ArrayDeque instead.
The Call Stack Connection
Every time our program calls a function, it goes on the call stack. When the function returns, it gets popped off. This is why stack overflow happens — too many function calls (usually from infinite recursion) and the call stack runs out of space.
// The call stack in action
function a() { return b(); } // a() waits on call stack
function b() { return c(); } // b() waits on call stack
function c() { return 42; } // c() runs, pops off, then b, then a
a(); // Call stack: [a] -> [a, b] -> [a, b, c] -> [a, b] -> [a] -> []# The call stack in action
def a(): return b() # a() waits on call stack
def b(): return c() # b() waits on call stack
def c(): return 42 # c() runs, pops off, then b, then a
a() # Call stack: [a] -> [a, b] -> [a, b, c] -> [a, b] -> [a] -> []// The call stack in action
static int a() { return b(); } // a() waits on call stack
static int b() { return c(); } // b() waits on call stack
static int c() { return 42; } // c() runs, pops off, then b, then a
// Call stack: [a] -> [a, b] -> [a, b, c] -> [a, b] -> [a] -> []Understanding the call stack helps us reason about recursion and convert recursive solutions to iterative ones using an explicit stack.
Classic Problem: Valid Parentheses
Given a string with (), {}, [], determine if every opening bracket has a matching closing bracket in the right order. This is THE classic stack problem.
The idea: push opening brackets, pop when we see a closing bracket. If the popped bracket doesn’t match, it’s invalid.
// Valid parentheses -- O(n) time, O(n) space
function isValid(s) {
const stack = [];
const pairs = { ')': '(', '}': '{', ']': '[' };
for (const ch of s) {
if ('({['.includes(ch)) {
stack.push(ch); // opening bracket: push
} else {
if (stack.pop() !== pairs[ch]) return false; // must match
}
}
return stack.length === 0; // stack must be empty at the end
}# Valid parentheses -- O(n) time, O(n) space
def is_valid(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '({[':
stack.append(ch) # opening bracket: push
else:
if not stack or stack.pop() != pairs[ch]:
return False # must match
return len(stack) == 0 # stack must be empty at the end// Valid parentheses -- O(n) time, O(n) space
static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', '}', '{', ']', '[');
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '{' || ch == '[') {
stack.push(ch); // opening bracket: push
} else {
if (stack.isEmpty() || stack.pop() != pairs.get(ch))
return false; // must match
}
}
return stack.isEmpty(); // stack must be empty at the end
}Classic Problem: Next Greater Element
Given an array, for each element, find the next element to the right that’s larger. If there’s none, the answer is -1.
Brute force is O(n²). With a stack, we can do it in O(n).
The trick: we iterate from right to left, maintaining a stack of elements we’ve seen. We pop off anything smaller than the current element (they can never be the “next greater” for anything to the left).
// Next greater element -- O(n) with a stack
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices
for (let i = nums.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] <= nums[i]) {
stack.pop(); // pop smaller elements -- they're useless now
}
if (stack.length) {
result[i] = stack[stack.length - 1]; // top is next greater
}
stack.push(nums[i]);
}
return result;
}
// [4, 5, 2, 10] -> [5, 10, 10, -1]# Next greater element -- O(n) with a stack
def next_greater_element(nums):
result = [-1] * len(nums)
stack = [] # stores values
for i in range(len(nums) - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop() # pop smaller elements -- they're useless now
if stack:
result[i] = stack[-1] # top is next greater
stack.append(nums[i])
return result
# [4, 5, 2, 10] -> [5, 10, 10, -1]// Next greater element -- O(n) with a stack
static int[] nextGreaterElement(int[] nums) {
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && stack.peek() <= nums[i]) {
stack.pop(); // pop smaller elements -- they're useless now
}
if (!stack.isEmpty()) {
result[i] = stack.peek(); // top is next greater
}
stack.push(nums[i]);
}
return result;
}
// [4, 5, 2, 10] -> [5, 10, 10, -1]Min Stack Concept
A Min Stack is a stack that also supports getMin() in O(1) time. The trick is maintaining a second stack that tracks the minimum at each level.
We push to the min stack whenever the new value is less than or equal to the current minimum. We pop from the min stack whenever we pop the current minimum from the main stack.
// Min Stack -- all operations in O(1)
class MinStack {
constructor() {
this.stack = [];
this.minStack = []; // tracks minimums
}
push(val) {
this.stack.push(val);
// push to minStack if it's empty or val <= current min
if (!this.minStack.length || val <= this.getMin()) {
this.minStack.push(val);
}
}
pop() {
if (this.stack.pop() === this.getMin()) {
this.minStack.pop(); // min was removed, pop from minStack too
}
}
top() { return this.stack[this.stack.length - 1]; }
getMin() { return this.minStack[this.minStack.length - 1]; }
}# Min Stack -- all operations in O(1)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # tracks minimums
def push(self, val):
self.stack.append(val)
# push to min_stack if it's empty or val <= current min
if not self.min_stack or val <= self.get_min():
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.get_min():
self.min_stack.pop() # min was removed
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]// Min Stack -- all operations in O(1)
class MinStack {
Deque<Integer> stack = new ArrayDeque<>();
Deque<Integer> minStack = new ArrayDeque<>();
void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
void pop() {
if (stack.pop().equals(minStack.peek())) {
minStack.pop();
}
}
int top() { return stack.peek(); }
int getMin() { return minStack.peek(); }
}When to Think “Stack”
Here’s a mental checklist. If the problem involves any of these, consider using a stack:
- Matching pairs (parentheses, HTML tags)
- Most recent first processing (undo, browser back button)
- Next greater/smaller element problems
- Expression evaluation (postfix, infix)
- DFS traversal (iterative version uses an explicit stack)
- Recursion simulation (any recursion can be converted to a stack)
Stacks are simple but incredibly versatile. Master the patterns above and we’ll be able to spot stack problems in interviews immediately.