Stacks
The last-in-first-out ADT, its array- and list-backed implementations, and its applications from bracket matching and expression evaluation to the monotonic stack.
What you will learn
The last-in-first-out ADT, its array- and list-backed implementations, and its applications from bracket matching and expression evaluation to the monotonic stack.
Prerequisites: Modules 5 and 7.
ADT and operations
push, pop, top/peek, empty, size. Explain LIFO, overflow/underflow, array-backed and linked-list-backed implementations.
Syntax
In C++, pop() does not return the removed value. Read it with top() first. Calling top() or pop() on an empty std::stack is undefined behaviour — always check empty().
stack<int> st;
st.push(10);
if (!st.empty()) {
int topValue = st.top();
st.pop();
}Applications
Balanced brackets, expression conversion/evaluation, undo operations, browser history, recursion simulation, DFS, monotonic stack, and histogram problems.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The >= in the shunting-yard loop makes operators of equal precedence left-associative: 8 − 3 − 2 becomes 83-2- (= 3), not 832-- (= 7).
#include <bits/stdc++.h>
using namespace std;
bool balanced(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') st.push(c);
else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) return false; // closing with nothing open
char open = st.top(); st.pop();
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
}
}
return st.empty(); // nothing left open
}
int prec(char op) { return op == '+' || op == '-' ? 1 : 2; }
// Shunting-yard: infix -> postfix, then evaluate the postfix with a value stack
string toPostfix(const string& s) {
string out; stack<char> ops;
for (char c : s) {
if (isdigit((unsigned char)c)) out += c;
else if (c == '(') ops.push(c);
else if (c == ')') { while (ops.top() != '(') { out += ops.top(); ops.pop(); } ops.pop(); }
else if (c != ' ') {
while (!ops.empty() && ops.top() != '(' && prec(ops.top()) >= prec(c)) { out += ops.top(); ops.pop(); }
ops.push(c);
}
}
whi
…{[()()]} balanced: true
([)] balanced: false
(( balanced: false
)( balanced: false
3 + 4 * (2 - 1) - 8 / 2 -> postfix 3421-*+82/- = 3Advanced patterns
Next greater/smaller element, stock span, largest rectangle in histogram, maximal rectangle, remove k digits, and stack-based parsing.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Each bar is pushed once and popped once, so the whole scan is O(n) (Module 26 generalises the monotonic stack).
#include <bits/stdc++.h>
using namespace std;
long long largestRectangle(const vector<int>& h) {
stack<int> st; // indices with increasing heights
long long best = 0;
int n = (int)h.size();
for (int i = 0; i <= n; ++i) {
int cur = (i == n) ? 0 : h[i]; // sentinel height 0 flushes the stack
while (!st.empty() && h[st.top()] >= cur) {
int height = h[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
best = max(best, 1LL * height * (i - left - 1));
}
st.push(i);
}
return best;
}
long long brute(const vector<int>& h) {
long long best = 0;
for (size_t i = 0; i < h.size(); ++i) {
int mn = INT_MAX;
for (size_t j = i; j < h.size(); ++j) { mn = min(mn, h[j]); best = max(best, 1LL * mn * int(j - i + 1)); }
}
return best;
}
int main() {
vector<int> h = {2, 1, 5, 6, 2, 3};
cout << "largest rectangle in {2,1,5,6,2,3}: " << largestRectangle(h) << '\n';
mt19937 rng(3);
for (int t = 0; t < 3000; ++t) {
vector<int> v(rng() % 10 + 1);
for (int& x : v) x = rng() % 6;
if (largestRectangle(v)
…largest rectangle in {2,1,5,6,2,3}: 10
matches the O(n^2) brute force on 3000 random histogramsstackqueuePractice
Easy: implement a stack with getMin() in O(1) (hint: a second stack of running minimums).
Medium: remove k digits from a number string to make it as small as possible.
Hard: maximal rectangle of 1s in a binary matrix (row-by-row histograms).
Quiz
? Which input makes a bracket checker that ignores the final `st.empty()` check wrong?
+ `((` :: Every closing bracket matched, but two remain open.
- `()` :: Correctly balanced.
- `)(` :: Caught by the empty-stack check on `)`.
- `([)]` :: Caught by the mismatch check.
? Why is the histogram algorithm O(n) despite the inner while loop?
+ Each index is pushed and popped at most once, so total work is linear. :: Amortized counting over the whole scan.
- The inner loop runs at most once. :: It can run many times for one i.
- Heights are small. :: Irrelevant.
- It uses a sentinel. :: The sentinel only flushes the stack.
? What does `std::stack::pop()` return?
+ Nothing (void) — read `top()` first :: A frequent surprise for people coming from other languages.
- The removed element :: That is Java's `Stack.pop()` or Python's `list.pop()`.
- A bool :: No.
- An iterator :: No.