Chapter 4 · Intermediate · Prereq: Chapter 3

Stacks & Queues

LIFO vs FIFO · Bracket Matching · Monotonic Stacks · Deque Sliding Window — the patterns that eliminate O(n²) loops with elegant O(n) stack-based sweeps.

11 Sections 13 Practice Problems Intermediate ← Back to Roadmap

Section 1 — Stacks: LIFO Data Structure

A stack is a linear data structure following Last In, First Out (LIFO): the last element pushed is the first one popped. Think of a pile of dinner plates — you always add and remove from the top.

Real-World Stack Analogies

Function call stack: OS pushes a stack frame on each function call, pops on return. Stack overflow = too deep recursion.
Browser history: Back button pops the last visited URL. Forward button uses a second stack.
Undo/Redo: Text editors push changes; undo pops the last change.
Expression evaluator: Compilers evaluate infix/postfix math using stacks.

1.1 — Stack Operations in C++

#include <stack>
stack<int> st;

st.push(10);       // push — O(1)
st.push(20);
st.push(30);
st.top();          // peek top = 30 — O(1), does NOT remove
st.pop();          // remove top = 30 — O(1), returns void
st.empty();        // true if empty — O(1)
st.size();         // number of elements — O(1)

// CRITICAL: ALWAYS check empty() before top() or pop()
if (!st.empty()) { int val = st.top(); st.pop(); }

Push / Pop / TopO(1) SpaceO(n)

Section 2 — Queues: FIFO Data Structure

A queue is a linear data structure following First In, First Out (FIFO): the first element enqueued is the first dequeued. Think of a supermarket checkout line — customers are served in arrival order.

Stack vs Queue in One Sentence Stack: last in, first out (DFS). Queue: first in, first out (BFS). Mixing them is the #1 source of wrong answers on BFS/DFS problems.

#include <queue>
queue<int> q;

q.push(1);         // enqueue rear — O(1)
q.push(2);
q.push(3);
q.front();         // peek front = 1 — O(1), does NOT remove
q.back();          // peek rear = 3 — O(1)
q.pop();           // dequeue front = 1 — O(1), returns void
q.empty();         // true if empty — O(1)
q.size();          // number of elements — O(1)

// Deque (double-ended queue) — push/pop from BOTH ends O(1)
#include <deque>
deque<int> dq;
dq.push_back(1);   dq.push_front(0);
dq.pop_back();     dq.pop_front();
dq.front();        dq.back();

Push / Pop / Front / BackO(1) SpaceO(n)

Section 3 — Pattern: Bracket Matching

The classic stack application: use a stack to ensure every opening bracket has a matching closing bracket in the correct order.

Algorithm — Valid Parentheses

Opening bracket ( [ { → push onto stack
Closing bracket ) ] } → check if stack top is the matching opener; if yes pop, if no → invalid
At the end: stack must be empty (all openers matched)

Common mistake: returning true at end without checking st.empty(). Input ((( is invalid but stack is non-empty!

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;  // no matching opener
            char top = st.top(); st.pop();
            if ((c==')' && top!='(') ||
                (c==']' && top!='[') ||
                (c=='}' && top!='{')) return false;
        }
    }
    return st.empty();  // all openers must be matched
}

TimeO(n) SpaceO(n)

Section 4 — Pattern: Min Stack (O(1) getMin)

Design a stack that supports push, pop, top, and getMin() in O(1). The trick: maintain an auxiliary min-tracking stack that stores the current minimum at each depth.

Key Insight When you push a value, also push the minimum of (that value, current minStack top) onto the auxiliary stack. When you pop the main stack, pop the auxiliary stack too. The auxiliary stack top always holds the global minimum for the current state.

class MinStack {
    stack<int> st, minSt;
public:
    void push(int val) {
        st.push(val);
        int curMin = minSt.empty() ? val : min(val, minSt.top());
        minSt.push(curMin);
    }
    void pop() { st.pop(); minSt.pop(); }   // always pop both
    int top() { return st.top(); }
    int getMin() { return minSt.top(); }    // O(1)
};

All opsO(1) SpaceO(n) — two stacks

Section 5 — Pattern: Queue Using Two Stacks

Simulate FIFO queue behaviour using two LIFO stacks. Key: lazy transfer — only move elements from inbox to outbox when outbox is empty.

Two-Stack Queue — Amortised O(1)

inbox stack: receives all push() calls — O(1)
outbox stack: serves all pop()/peek() calls
When outbox is empty, transfer ALL elements from inbox to outbox (single reversal gives FIFO order)
Each element moves at most once: inbox→outbox. Total work across n operations = O(n) → amortised O(1) per operation

class MyQueue {
    stack<int> inbox, outbox;
    void transfer() {
        if (outbox.empty())
            while (!inbox.empty()) { outbox.push(inbox.top()); inbox.pop(); }
    }
public:
    void push(int x) { inbox.push(x); }  // O(1)
    int pop()  { transfer(); int v=outbox.top(); outbox.pop(); return v; }
    int peek() { transfer(); return outbox.top(); }
    bool empty() { return inbox.empty() && outbox.empty(); }
};

Section 6 — Pattern: Monotonic Stack

A monotonic stack maintains elements in strictly increasing or decreasing order. When a new element violates the order, we pop until order is restored. This solves Next Greater Element and similar problems in O(n).

Two Monotonic Stack Variants

Decreasing stack (top is smallest): pop when new element is greater. Answers: Next Greater Element, Daily Temperatures.
Increasing stack (top is largest): pop when new element is smaller. Answers: Next Smaller Element, Histogram.
Always store INDICES, not values — you need indices to compute distances and record answers at the right position.
Each element is pushed once and popped at most once → O(n) amortised total.

6.1 — Next Greater Element

// Next Greater Element — O(n) time, O(n) space
vector<int> nextGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> ans(n, -1);  // default: no greater element
    stack<int> st;            // stores INDICES, decreasing stack
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[i] > arr[st.top()]) {
            ans[st.top()] = arr[i];  // arr[i] is the next greater
            st.pop();
        }
        st.push(i);
    }
    return ans;
    // Remaining elements in stack have no next greater (ans=-1 by default)
}

// Circular array (scan 2n indices, use i%n)
for (int i = 0; i < 2*n; i++) {
    while (!st.empty() && arr[i%n] > arr[st.top()])
        { ans[st.top()] = arr[i%n]; st.pop(); }
    if (i < n) st.push(i);
}

6.2 — Daily Temperatures Trace (arr = [73,74,75,71,69,72,76,73])

i=0, temp=73: stack empty → push 0. Stack:[0]
i=1, temp=74: 74 > 73 → pop 0, ans[0]=1–0=1; push 1. Stack:[1]
i=2, temp=75: 75 > 74 → pop 1, ans[1]=2–1=1; push 2. Stack:[2]
i=3, temp=71: 71 < 75 → push 3. Stack:[2,3]
i=4, temp=69: 69 < 71 → push 4. Stack:[2,3,4]
i=5, temp=72: 72>69 pop 4 ans[4]=1; 72>71 pop 3 ans[3]=2; push 5. Stack:[2,5]
i=6, temp=76: 76>72 pop 5 ans[5]=1; 76>75 pop 2 ans[2]=4; push 6. Stack:[6]
i=7, temp=73: 73 < 76 → push 7. Stack:[6,7]
END: idx 6,7 remain → no warmer day → ans[6]=0, ans[7]=0
Final: ans = [1, 1, 4, 2, 1, 1, 0, 0] ✓

6.3 — Largest Rectangle in Histogram

// Largest Rectangle in Histogram — O(n) with sentinel
int largestRectangleArea(vector<int>& heights) {
    heights.push_back(0);  // sentinel: forces all bars to be popped
    stack<int> st;
    int maxArea = 0;
    for (int i = 0; i < heights.size(); i++) {
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, h * w);
        }
        st.push(i);
    }
    return maxArea;
}

Section 7 — Pattern: Monotonic Deque (Sliding Window Maximum)

For a fixed-size sliding window of size k, maintain a monotonic decreasing deque of indices. The front always holds the index of the maximum element in the current window.

Remove from front if the front index is out of the current window (index < i–k+1)
Remove from back while the back element is ≤ new element (smaller elements can never be the window max)
Push new index to back; front of deque = index of the window maximum

// Sliding Window Maximum — O(n) time, O(k) space
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;   // indices, front = index of max in window
    vector<int> ans;
    for (int i = 0; i < nums.size(); i++) {
        // Remove indices outside window
        while (!dq.empty() && dq.front() < i-k+1) dq.pop_front();
        // Remove smaller elements from back (they can never be max)
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k-1) ans.push_back(nums[dq.front()]); // window full
    }
    return ans;
}

TimeO(n) SpaceO(k)

Section 8 — Common Mistakes & Edge Cases

❌ top() on empty stack

Always check st.empty() before st.top() or st.pop(). Empty access = undefined behaviour / runtime crash.

❌ pop() returns void

C++ STL stack::pop() does NOT return the value. Use st.top() to read, then st.pop() to remove.

❌ Stack for BFS

Stack gives DFS. BFS requires a queue (FIFO). Mixing them gives wrong shortest-path results.

❌ Not checking empty at end

Valid Parentheses: return st.empty(), not true. Input "(((" leaves stack non-empty → invalid.

❌ Values not indices in mono-stack

Monotonic stack must store indices to compute distances and record answers at the right array position.

❌ Wrong monotonicity direction

Next Greater → decreasing stack (pop when arr[i] > arr[top]). Next Smaller → increasing stack. Swapping gives wrong answers.

Edge Cases to Test

Empty string for bracket matching → return true
Single bracket '(' → invalid
Temperatures all equal [5,5,5,5] → strictly greater condition never fires → all answers = 0
k=1 for sliding window → each element is its own window max
k=n for sliding window → single result = global maximum

Practice Problems

Stack Problems

#	Problem	Pattern	Diff
1	20. Valid Parentheses	Bracket matching	Easy
2	155. Min Stack	Auxiliary min-tracking stack	Medium
3	150. Evaluate Reverse Polish Notation	Postfix expression evaluation	Medium
4	394. Decode String	Nested encoding — two stacks	Medium
5	232. Implement Queue using Stacks	Two stacks + lazy transfer	Easy

Monotonic Stack Problems

#	Problem	Pattern	Diff
6	739. Daily Temperatures	Decreasing stack (days to wait)	Medium
7	496. Next Greater Element I	Monotonic stack + hash map	Easy
8	503. Next Greater Element II	Circular array — scan 2n	Medium
9	84. Largest Rectangle in Histogram	Increasing stack + sentinel	Hard
10	42. Trapping Rain Water	Monotonic stack or two-pointer	Hard

Queue & Deque Problems

#	Problem	Pattern	Diff
11	239. Sliding Window Maximum	Monotonic deque — O(n)	Hard
12	102. Binary Tree Level Order Traversal	BFS with queue	Medium
13	994. Rotting Oranges	Multi-source BFS with queue	Medium