Week 7: Stacks, Queues & Monotonic Stacks

1. Stack Fundamentals & Balanced Parentheses

A stack is a Last-In-First-Out (LIFO) structure: you can only push onto the top and pop from the top, in O(1) time each. std::stack in <stack> is an adaptor — by default it wraps a std::deque and exposes only the operations a stack needs: push, pop, top and empty.

#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

// Returns true if every bracket in s is closed in the right order.
// O(n) time, O(n) space in the worst case (all opening brackets).
bool isBalanced(const string& s) {
    stack<char> open;
    unordered_map<char, char> match = {{')', '('}, {']', '['}, {'}', '{'}};

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            open.push(c);
        } else if (match.count(c)) {
            if (open.empty() || open.top() != match[c]) return false;
            open.pop();
        }
    }
    return open.empty();   // nothing left unclosed
}

The LIFO order is exactly what makes a stack the right tool here: the most recently opened bracket must be the next one closed, which is precisely what top() gives you access to. Any problem with a "most recently seen, still unresolved" item is a strong signal that a stack belongs in your solution.

2. The Monotonic Stack Pattern

A monotonic stack keeps its elements in strictly increasing or decreasing order at all times, by popping off elements that would violate that order before pushing a new one. The classic use is the next greater element problem: for each element, find the first element to its right that's strictly larger.

#include <vector>
#include <stack>
using namespace std;

// For each index i, result[i] is the next element to the right that's greater
// than nums[i], or -1 if none exists. O(n) time, O(n) space.
vector<int> nextGreaterElement(const vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> indices;   // stores INDICES whose next-greater is still unknown,
                           // with nums[indices] kept in decreasing order top-to-bottom

    for (int i = 0; i < n; i++) {
        // nums[i] is bigger than everything smaller still waiting on the stack --
        // pop and resolve each of those
        while (!indices.empty() && nums[indices.top()] < nums[i]) {
            result[indices.top()] = nums[i];
            indices.pop();
        }
        indices.push(i);
    }
    return result;   // whatever's left on the stack has no next greater element
}

The complexity argument is worth stating precisely: the inner while loop looks like it could make this O(n²), but every index is pushed exactly once and popped at most once across the entire run, so total work across all iterations is O(n), not O(n) per iteration — this is called amortized analysis, and it's the reasoning behind why the monotonic stack pattern is O(n) despite the nested loop shape.

3. Queue Fundamentals

A queue is First-In-First-Out (FIFO): elements are added at the back and removed from the front, both in O(1). std::queue in <queue> is another adaptor over std::deque by default, exposing push, pop, front and back.

#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);           // back: [1]
    q.push(2);           // back: [1, 2]
    q.push(3);           // back: [1, 2, 3]

    int f = q.front();   // f == 1 -- the first element pushed
    q.pop();              // removes 1, queue is now [2, 3]

    while (!q.empty()) {
        // process q.front(), then q.pop()
        q.pop();
    }
}

FIFO order is exactly what you want when processing elements in the order they were discovered rather than the order you most recently touched them — which is precisely why breadth-first search on a graph or tree, covered starting Week 9's level-order traversal and continuing into Week 12's graph BFS, always uses a queue rather than a stack: it guarantees you finish exploring everything at the current "distance" before moving farther out.

4. std::deque & Sliding Window Maximum

std::deque ("double-ended queue," <deque>) supports O(1) push and pop at both ends — push_front, push_back, pop_front, pop_back — which is more flexibility than either stack or queue exposes on their own. That flexibility is exactly what the sliding window maximum problem needs: find the maximum of every size-k contiguous window as it slides across an array.

#include <vector>
#include <deque>
using namespace std;

// Returns the maximum of every contiguous window of size k.
// O(n) time, O(k) space -- each index is pushed and popped from the
// deque at most once, the same amortized argument as the monotonic stack.
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    deque<int> dq;   // stores INDICES, nums[dq] kept in decreasing order front-to-back
    vector<int> result;

    for (int i = 0; i < (int)nums.size(); i++) {
        // drop indices that fell out of the window on the left
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // maintain decreasing order -- anything smaller than nums[i] can
        // never be the max again while nums[i] is still in the window
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);   // front is always the current max
        }
    }
    return result;
}

This is the monotonic stack idea applied at both ends at once: the front of the deque always holds the index of the current window's maximum, and it gets evicted from the front only once it slides outside the window, and from the back whenever a larger value arrives to make it irrelevant. Compare this to the brute-force approach of scanning all k elements for every window position, which costs O(n × k) — the deque version does the same job in O(n) total.

5. Hands-on Exercise

6. Knowledge Check

Four quick questions. Expand each to check your answer.