Stacks, Queues & Monotonic Stacks
LIFO and FIFO structures behind bracket matching, expression evaluation, BFS, and the powerful monotonic stack for “next greater element” problems.
Stack (LIFO) and queue (FIFO)
A stack is last-in-first-out: push on top, pop from the top. A queue is first-in-first-out: enqueue at the back, dequeue from the front. A deque allows both ends.
| Python | Java | C++ | JavaScript | |
|---|---|---|---|---|
| Stack | list (append/pop) |
ArrayDeque (push/pop) |
stack / vector |
Array (push/pop) |
| Queue | collections.deque |
ArrayDeque (offer/poll) |
queue |
array + head index |
Never use list.pop(0) in Python or array.shift() in a hot JS loop: both are O(n).
Where stacks appear
- Matching: brackets, HTML tags, undo history
- Expression evaluation: Reverse Polish Notation, calculators (operator stack)
- Iterative DFS and the iterative in-order tree traversal
- Monotonic stack: a stack whose values are always increasing or always decreasing
The monotonic stack
For “next greater / next smaller element” questions, keep a stack of indices still waiting for an answer, with values in decreasing order. When a bigger value arrives, it is the answer for every smaller value on top: pop them and record. Each index is pushed and popped once, so the whole thing is O(n) instead of O(n²).
Classic uses: Daily Temperatures, Next Greater Element, Stock Span, Largest Rectangle in Histogram, Trapping Rain Water, Sum of Subarray Minimums.
Code template
# Next greater element for each index (-1 if none)
def next_greater(a):
res = [-1] * len(a)
stack = [] # indices, values decreasing
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
res[stack.pop()] = x
stack.append(i)
return res
from collections import deque
q = deque([1, 2]); q.append(3); q.popleft() # O(1) queue// Next greater element for each index (-1 if none)
int[] nextGreater(int[] a) {
int[] res = new int[a.length];
Arrays.fill(res, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indices, values decreasing
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && a[stack.peek()] < a[i]) res[stack.pop()] = a[i];
stack.push(i);
}
return res;
}
Deque<Integer> q = new ArrayDeque<>(); q.offer(1); q.poll(); // O(1) queue// Next greater element for each index (-1 if none)
vector<int> nextGreater(const vector<int>& a) {
vector<int> res(a.size(), -1), st; // st: indices, values decreasing
for (int i = 0; i < (int)a.size(); i++) {
while (!st.empty() && a[st.back()] < a[i]) { res[st.back()] = a[i]; st.pop_back(); }
st.push_back(i);
}
return res;
}
queue<int> q; q.push(1); q.pop(); // O(1) queue// Next greater element for each index (-1 if none)
function nextGreater(a) {
const res = new Array(a.length).fill(-1), stack = []; // indices, values decreasing
for (let i = 0; i < a.length; i++) {
while (stack.length && a[stack[stack.length - 1]] < a[i]) res[stack.pop()] = a[i];
stack.push(i);
}
return res;
}
// O(1) queue: array + head pointer (avoid shift())
const q = [1, 2, 3]; let head = 0; const front = q[head++];Practise this pattern (4 problems)
Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.
| # | Problem | Difficulty | |
|---|---|---|---|
| 31 | Valid Parentheses | Easy | |
| 32 | Daily Temperatures | Medium | |
| 33 | Evaluate Reverse Polish Notation | Medium | |
| 34 | Largest Rectangle in Histogram | Hard |
Common mistakes
- Popping from an empty stack: check first.
- Storing values when you need distances: store indices in a monotonic stack.
- Forgetting a final flush: add a sentinel (for example height 0) so everything left gets processed.