Chapter 18 of 30
Stacks, Queues & Monotonicity
Master stack and queue applications, monotonic stacks, and monotonic deques for sliding window min/max problems.
Stack ApplicationsQueue ApplicationsMonotonic StackMonotonic Deque (Sliding Window Min/Max)
Share:
Stacks, Queues & Monotonicity
Stacks and queues become powerful when combined with monotonicity constraints. A monotonic stack keeps elements in sorted order, enabling O(n) solutions to problems that seem to require O(n²).
Stack Applications
Balanced Parentheses
hljs cpp
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if (c == ')' && t != '(') return false;
if (c == ']' && t != '[') return false;
if (c == '}' && t != '{') return false;
}
}
return st.empty();
}
Next Greater Element
hljs cpp
// For each element, find the next greater element to its right
vector<int> result(n, -1);
stack<int> st; // stores indices
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
result[st.top()] = a[i];
st.pop();
}
st.push(i);
}
Evaluate Expression
hljs cpp
// Postfix evaluation
stack<int> st;
for (token : tokens) {
if (token is number) {
st.push(number);
} else {
int b = st.top(); st.pop();
int a = st.top(); st.pop();
st.push(apply(token, a, b));
}
}
Queue Applications
BFS (Breadth-First Search)
hljs cpp
queue<int> q;
vector<bool> visited(n, false);
q.push(source);
visited[source] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
Sliding Window Maximum (Queue Approach)
hljs cpp
deque<int> dq; // stores indices
for (int i = 0; i < n; i++) {
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) cout << a[dq.front()] << " ";
}
Monotonic Stack
A stack where elements are always in increasing or decreasing order.
Next Greater Element (Monotonic Stack)
hljs cpp
vector<int> nextGreater(n, -1);
stack<int> st; // decreasing stack
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] < a[i]) {
nextGreater[st.top()] = a[i];
st.pop();
}
st.push(i);
}
Previous Greater Element
hljs cpp
vector<int> prevGreater(n, -1);
stack<int> st; // decreasing stack
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()] < a[i]) {
prevGreater[st.top()] = a[i];
st.pop();
}
st.push(i);
}
Largest Rectangle in Histogram
hljs cpp
// For each bar, find the first smaller bar to the left and right
vector<int> left(n), right(n);
stack<int> st;
// Left smaller
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
// Clear stack
while (!st.empty()) st.pop();
// Right smaller
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()] >= a[i]) st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
// Compute max area
long long maxArea = 0;
for (int i = 0; i < n; i++) {
long long area = (long long)a[i] * (right[i] - left[i] - 1);
maxArea = max(maxArea, area);
}
Monotonic Deque (Sliding Window Min/Max)
A monotonic deque maintains elements in order while supporting O(1) removal from both ends:
hljs cpp
// Sliding window minimum
deque<int> dq; // increasing deque (front = minimum)
for (int i = 0; i < n; i++) {
// Remove elements outside window
while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
// Remove elements that are larger than current (they'll never be min)
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) {
cout << a[dq.front()] << " "; // minimum in window [i-k+1, i]
}
}
Summary
- Stack: LIFO — next greater/smaller element, balanced parentheses, expression evaluation
- Queue: FIFO — BFS, sliding window maximum
- Monotonic stack: keeps elements in sorted order for O(n) range queries
- Monotonic deque: O(1) amortized push/pop from both ends, maintains min/max at front
- Key insight: each element is pushed and popped at most once → O(n) total
Prefer reading offline? Download the full book as a PDF.
Download Free Book