Pattern Guide
Stack & Queue Patterns
"LIFO for matching/nesting. FIFO for BFS/order. Deque for sliding extremes."
Stack and queue problems appear in ~20% of interviews. Stack handles matching brackets, expression evaluation, and monotonic patterns. Queue drives BFS. Deque handles sliding window minimum/maximum. Learn which structure fits which signal.
18 min readgraph problems →
Problems you can solve with this pattern
9 problems · click any to start solving
Universal bracket matching template
// Valid parentheses: push open brackets, pop+check on close brackets
var isValid = function(s) {
const stack = [];
const match = { ')': '(', ']': '[', '}': '{' };
for (const c of s) {
if ('([{'.includes(c)) stack.push(c);
else if (stack.pop() !== match[c]) return false;
}
return stack.length === 0;
};
// Min add to make valid — count unmatched open/close
var minAddToMakeValid = function(s) {
let open = 0, close = 0;
for (const c of s) {
if (c === '(') open++;
else if (open > 0) open--; // matched
else close++; // unmatched close
}
return open + close;
};Stack and queue are the two most fundamental linear data structures after arrays. Stack is LIFO — last in, first out. Queue is FIFO — first in, first out. Most "bracket matching," "expression parsing," "next greater element," and "valid sequence" problems are stack problems. BFS and level-order traversal use queues. Sliding window min/max use a monotonic deque.
| Signal in Problem | Structure | Pattern |
|---|---|---|
| "Valid/balanced parentheses" | Stack | Push open, pop on close, check match |
| "Next greater/smaller element" | Monotonic stack | Maintain decreasing/increasing stack |
| "Evaluate expression" | Stack | Operand/operator stacks or postfix eval |
| "Level order / BFS" | Queue | Enqueue neighbors, process level by level |
| "Sliding window min/max" | Monotonic deque | Pop from back when new > back (max deque) |
| "Nearest smaller to left/right" | Monotonic stack | Process left→right, maintain ascending stack |
| "Implement queue using stacks" | Two stacks | Inbox stack + outbox stack (lazy transfer) |
Stack Pattern: Bracket Matching Template
Universal bracket matching template
// Valid parentheses: push open brackets, pop+check on close brackets
var isValid = function(s) {
const stack = [];
const match = { ')': '(', ']': '[', '}': '{' };
for (const c of s) {
if ('([{'.includes(c)) stack.push(c);
else if (stack.pop() !== match[c]) return false;
}
return stack.length === 0;
};
// Min add to make valid — count unmatched open/close
var minAddToMakeValid = function(s) {
let open = 0, close = 0;
for (const c of s) {
if (c === '(') open++;
else if (open > 0) open--; // matched
else close++; // unmatched close
}
return open + close;
};Monotonic Stack Template
Monotonic stack stays sorted (increasing or decreasing). When you push a new element, pop everything that violates the order. The popped elements' "answer" is the new element (it was the next greater/smaller for them).
- Next Greater Element: maintain decreasing stack (pop when new > top)
- Next Smaller Element: maintain increasing stack (pop when new < top)
- Previous Greater: same idea but process left→right; stack gives you what's "still waiting" to the left
- Next Greater Element: maintain decreasing stack (pop when new > top)
- Next Smaller Element: maintain increasing stack (pop when new < top)
- Previous Greater: same idea but process left→right; stack gives you what's "still waiting" to the left
Next Greater Element — O(n) with monotonic stack
// For each element, find the next element to the right that is greater
// Brute force: O(n²). Monotonic stack: O(n)
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // indices of elements waiting for their "next greater"
for (let i = 0; i < nums.length; i++) {
// pop all elements smaller than nums[i] — nums[i] is their answer
while (stack.length && nums[stack.at(-1)] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
// remaining elements in stack have no next greater → -1 (already set)
return result;
}
// Circular variant: run two passes (or use modulo)
function nextGreaterCircular(nums) {
const n = nums.length;
const result = new Array(n).fill(-1);
const stack = [];
for (let i = 0; i < 2 * n; i++) {
while (stack.length && nums[stack.at(-1)] < nums[i % n])
result[stack.pop()] = nums[i % n];
if (i < n) stack.push(i);
}
return result;
}Monotonic Deque for Sliding Window
Sliding window maximum — O(n) with deque
// For each window of size k, find the maximum
// Brute force: O(n*k). Deque: O(n)
var maxSlidingWindow = function(nums, k) {
const deque = []; // stores indices, front = max of current window
const result = [];
for (let i = 0; i < nums.length; i++) {
// remove elements outside window
while (deque.length && deque[0] < i - k + 1) deque.shift();
// remove smaller elements from back (they can never be the max)
while (deque.length && nums[deque.at(-1)] < nums[i]) deque.pop();
deque.push(i);
// window is fully formed when i >= k-1
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
};Stack pattern decision guide:
- "Matching pairs (brackets, tags)" → push open, pop+check on close
- "Next greater/smaller" → monotonic stack, pop when condition breaks
- "Largest rectangle / area under histogram" → monotonic stack with area calculation on pop
- "Expression evaluation" → two stacks (numbers + operators) or postfix evaluation
- "Sliding window max/min" → monotonic deque (front = answer, pop from back when new element is better)
- "Nested structure (decode string, mini interpreter)" → stack saves state at each nesting level
- "Matching pairs (brackets, tags)" → push open, pop+check on close
- "Next greater/smaller" → monotonic stack, pop when condition breaks
- "Largest rectangle / area under histogram" → monotonic stack with area calculation on pop
- "Expression evaluation" → two stacks (numbers + operators) or postfix evaluation
- "Sliding window max/min" → monotonic deque (front = answer, pop from back when new element is better)
- "Nested structure (decode string, mini interpreter)" → stack saves state at each nesting level