Chapter 3.6: Stacks, Queues & Deques

These three data structures control the order in which elements are processed. Each has a unique "personality" that makes it perfect for specific types of problems.

• Stack: Last In, First Out (like a stack of plates)
• Queue: First In, First Out (like a line at a store)
• Deque: Double-ended — insert/remove from both ends

3.6.1 Stack Deep Dive

We introduced stack in Chapter 3.1. Let's use it to solve real problems.

Visual: Stack Operations

The diagram above illustrates the LIFO (Last In, First Out) property with step-by-step push and pop operations. Note how pop() always removes the most-recently-pushed element — this is what makes stacks ideal for matching brackets, DFS, and undo operations.

The Balanced Brackets Problem

Problem: Given a string of brackets ()[]{}, determine if they're properly nested.

#include <bits/stdc++.h>
using namespace std;

bool isBalanced(const string &s) {
    stack<char> st;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);   // opening bracket: push onto stack
        } else {
            // closing bracket: must match the most recent opening
            if (st.empty()) return false;   // no matching opening bracket

            char top = st.top();
            st.pop();

            // Check if it matches
            if (ch == ')' && top != '(') return false;
            if (ch == ']' && top != '[') return false;
            if (ch == '}' && top != '{') return false;
        }
    }

    return st.empty();  // all brackets matched if stack is empty
}

int main() {
    cout << isBalanced("()[]{}") << "\n";    // 1 (true)
    cout << isBalanced("([]){}") << "\n";    // 1 (true)
    cout << isBalanced("([)]")   << "\n";    // 0 (false)
    cout << isBalanced("(()")    << "\n";    // 0 (false — unmatched '(')
    return 0;
}

The "Next Greater Element" Problem

Problem: For each element in an array, find the next element to its right that is strictly greater. If none exists, output -1.

This is a classic monotonic stack problem.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> answer(n, -1);  // default: -1 (no greater element)
    stack<int> st;              // stores indices of elements awaiting their answer

    for (int i = 0; i < n; i++) {
        // While stack is non-empty and current element > element at stack's top index
        while (!st.empty() && A[i] > A[st.top()]) {
            answer[st.top()] = A[i];  // A[i] is the next greater element for st.top()
            st.pop();
        }
        st.push(i);  // push current index (waiting for a larger element later)
    }

    for (int x : answer) cout << x << " ";
    cout << "\n";

    return 0;
}

Trace for [3, 1, 4, 1, 5, 9, 2, 6]:

• i=0: push 0. Stack: [0]
• i=1: A[1]=1 ≤ A[0]=3, push 1. Stack: [0,1]
• i=2: A[2]=4 > A[1]=1 → answer[1]=4, pop. A[2]=4 > A[0]=3 → answer[0]=4, pop. Push 2.
• i=3: push 3. Stack: [2,3]
• i=4: A[4]=5 > A[3]=1 → answer[3]=5. A[4]=5 > A[2]=4 → answer[2]=5. Push 4.
• i=5: A[5]=9 > A[4]=5 → answer[4]=9. Push 5. Stack: [5]
• i=6: push 6. Stack: [5,6]
• i=7: A[7]=6 > A[6]=2 → answer[6]=6. Push 7.
• Remaining on stack (5, 7): answer stays -1.

Output: 4 4 5 5 9 -1 6 -1

Key insight: A monotonic stack maintains elements in a strictly increasing or decreasing order. When a new element breaks that order, it "solves" all the elements it's greater than. This is O(n) because each element is pushed and popped at most once.

3.6.2 Queue and BFS Preparation

The queue's FIFO property makes it perfect for Breadth-First Search (BFS), which we cover in Chapter 5.2. Here we focus on the queue itself and related patterns.

Visual: Queue Operations

The queue processes elements in order of arrival: the front element is always dequeued next, while new elements join at the back. This FIFO property ensures BFS visits nodes level-by-level, guaranteeing shortest-path distances.

Simulation with a Queue

Problem: A theme park ride has N groups of people. Each group has size[i]. The ride holds at most M people per run. Simulate how many runs are needed to take everyone.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    queue<int> groups;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        groups.push(x);
    }

    int runs = 0;
    while (!groups.empty()) {
        int capacity = m;   // remaining capacity for this run
        runs++;

        while (!groups.empty() && groups.front() <= capacity) {
            capacity -= groups.front();  // fit this group
            groups.pop();
        }
    }

    cout << runs << "\n";
    return 0;
}

3.6.3 Deque — Double-Ended Queue

A deque (pronounced "deck") supports O(1) insertion and removal at both the front and back.

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(1);    // [1]
    dq.push_back(2);    // [1, 2]
    dq.push_front(0);   // [0, 1, 2]
    dq.push_front(-1);  // [-1, 0, 1, 2]

    cout << dq.front() << "\n";  // -1
    cout << dq.back() << "\n";   // 2

    dq.pop_front();  // [-1 removed] → [0, 1, 2]
    dq.pop_back();   // [2 removed]  → [0, 1]

    cout << dq.front() << "\n";  // 0
    cout << dq.size() << "\n";   // 2

    // Random access (like a vector)
    cout << dq[0] << "\n";  // 0
    cout << dq[1] << "\n";  // 1

    return 0;
}

3.6.4 Monotonic Deque — Sliding Window Maximum

Problem: Given an array A of N integers and a window of size K, find the maximum value in each window as it slides from left to right.

Naive approach: for each window, scan all K elements → O(N×K). Too slow for large K.

Monotonic deque approach: O(N).

The deque stores indices of elements in decreasing order of their values. The front is always the maximum.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    deque<int> dq;  // stores indices; values A[dq[i]] are decreasing
    vector<int> maxInWindow;

    for (int i = 0; i < n; i++) {
        // Remove elements outside the window (front is too old)
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Remove elements from back that are smaller than A[i]
        // (they can never be the maximum for future windows)
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();
        }

        dq.push_back(i);  // add current index

        // Window is full starting at i = k-1
        if (i >= k - 1) {
            maxInWindow.push_back(A[dq.front()]);  // front is always the max
        }
    }

    for (int x : maxInWindow) cout << x << " ";
    cout << "\n";

    return 0;
}

Sample Input:

8 3
1 3 -1 -3 5 3 6 7

Sample Output:

3 3 5 5 6 7

Windows: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7.

3.6.5 Stack-Based: Largest Rectangle in Histogram

A classic competitive programming problem: given N bars of heights h[0..N-1], find the largest rectangle that fits within the histogram.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> h(n);
    for (int &x : h) cin >> x;

    stack<int> st;   // stores indices of bars in increasing height order
    long long maxArea = 0;

    for (int i = 0; i <= n; i++) {
        int currentH = (i == n) ? 0 : h[i];  // sentinel 0 at the end

        while (!st.empty() && h[st.top()] > currentH) {
            int height = h[st.top()];   // height of the rectangle
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;  // width
            maxArea = max(maxArea, (long long)height * width);
        }

        st.push(i);
    }

    cout << maxArea << "\n";
    return 0;
}

⚠️ Common Mistakes in Chapter 3.6

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Why is the monotonic stack O(N) and not O(N²)? It looks like there's a nested loop.

A: Key observation — each element is pushed at most once and popped at most once. Although the inner while loop may pop multiple elements at once, the total number of pops globally is ≤ N. So total operations ≤ 2N = O(N). This analysis method is called amortized analysis.

Q2: When to use stack vs deque?

A: If you only need LIFO (one-end access), use stack; if you need two-end operations (e.g., sliding window needs front removal + back addition), use deque. stack is actually backed by deque internally, but restricts the interface to only expose the top.

Q3: Must BFS use queue? Can I use vector?

A: Technically you can simulate with vector + index, but queue is clearer and less error-prone. In contests, use queue directly. The only exception is 0-1 BFS (shortest path with only 0 and 1 weights), which requires deque.

Q4: Why can the "largest rectangle" problem be solved with a stack?

A: The stack maintains an increasing sequence of bars. When a shorter bar is encountered, it means the top bar's "rightward extension" ends here. At that point, we can compute the rectangle area with the top bar's height. Each bar is pushed/popped once, total complexity O(N).

🔗 Connections to Later Chapters

• Chapter 5.2 (Graph BFS/DFS): queue is the core container for BFS, stack can be used for iterative DFS
• Chapter 3.4 (Two Pointers): the sliding window technique combines well with the monotonic deque from this chapter
• Chapters 6.1–6.3 (DP): certain optimization techniques (e.g., DP-optimized sliding window extremes) directly use the monotonic deque from this chapter
• The monotonic stack also appears as an alternative to Chapter 3.9 (Segment Trees) — many problems solvable by segment trees can also be solved in O(N) with a monotonic stack

Practice Problems

Problem 3.6.1 — Stock Span Read N daily stock prices. For each day, find the number of consecutive days up to that day where the price was ≤ today's price (including today). (Classic monotonic stack problem)

Problem 3.6.2 — Circular Queue Implement a circular queue of size K. Process operations: PUSH x (add x to back), POP (remove from front). Print "OVERFLOW" if push on full queue, "UNDERFLOW" if pop on empty.

Problem 3.6.3 — Sliding Window Minimum Same as the sliding window maximum example, but find the minimum.

Problem 3.6.4 — Expression Evaluation Read a simple expression with integers and +, - operators (no parentheses). Evaluate it using a stack.

Problem 3.6.5 — USACO 2020 January Bronze: Loan Repayment (Simplified) You have N stacks of hay. Each day, you can take one bale from any non-empty stack. Model this with a priority_queue: always take from the tallest stack. Simulate for D days and print the remaining bales.