Stack
A stack is a last-in-first-out (LIFO) data structure where elements are added and removed from the same end. Stacks are ideal for problems involving matching pairs (like parentheses), maintaining a monotonic sequence, or processing nested structures. The monotonic stack variant is particularly powerful for "next greater/smaller element" problems.
When to Use
- →You need to match opening and closing brackets or tags
- →You need to find the next greater or smaller element for each position
- →You need to evaluate expressions or handle nested structures
- →You need to maintain elements in increasing or decreasing order
- →You need to process elements in reverse order of their arrival
Approach
For matching problems (valid parentheses), push opening symbols onto the stack and pop when you see a closing symbol. If the popped element doesn't match or the stack is empty when it shouldn't be, the input is invalid.
The monotonic stack pattern maintains elements in sorted order. For "next greater element" problems, iterate through the array and pop elements from the stack that are smaller than the current element — the current element is the answer for each popped element. This processes each element at most twice (once pushed, once popped) for O(n) total.
For histogram/area problems, use a monotonic increasing stack. When you encounter a bar shorter than the stack's top, pop and calculate the area using the popped bar's height and the width between the current position and the new stack top.
Code Template
// Valid parentheses pattern
function isValid(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const char of s) {
if ('({['.includes(char)) {
stack.push(char);
} else {
if (stack.pop() !== pairs[char]) return false;
}
}
return stack.length === 0;
}
// Monotonic stack — next greater element
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // stores indices
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[i] > nums[stack[stack.length - 1]]) {
const idx = stack.pop();
result[idx] = nums[i];
}
stack.push(i);
}
return result;
}