Stacks & Queues | Phase 2

Stack (LIFO) vs Queue (FIFO)

Stack — Last In, First Out

1 (bottom)

7 ← TOP (push/pop here)

push(7) → [1,3,7]. pop() → returns 7, leaves [1,3]

Queue — First In, First Out

1 ← FRONT (dequeue)

7 → enqueue here

enqueue(7) → [1,3,7]. dequeue() → returns 1, leaves [3,7]

C++ API & Implementation

C++
// STACK — use std::stack
#include <stack>
stack<int> st;
st.push(5);       // add to top   O(1)
st.top();          // peek top     O(1)
st.pop();          // remove top   O(1)
st.empty();        // check empty  O(1)
st.size();         // number of elements

// QUEUE — use std::queue
#include <queue>
queue<int> q;
q.push(5);        // enqueue rear  O(1)
q.front();         // peek front    O(1)
q.pop();           // dequeue front O(1)
q.empty();         // check empty   O(1)

// DEQUE (double-ended queue) — use std::deque
deque<int> dq;
dq.push_front(1); // add to front
dq.push_back(2);  // add to back
dq.pop_front();   // remove front
dq.pop_back();    // remove back
    

When to Use Which

Stack Use Cases

Parentheses matching
DFS (iterative)
Undo/redo operations
Function call simulation
Monotonic stack (Hard)
Expression evaluation

Queue Use Cases

BFS traversal
Task scheduling (FIFO)
Sliding window maximum (deque)
Level-order tree traversal
0-1 BFS (shortest path)
Stream processing

Key insight: Use a stack when you need to process things in reverse order of arrival (backtracking). Use a queue when order of arrival must be preserved (level-by-level processing).

Monotonic Stack Pattern

A stack that maintains elements in monotonically increasing or decreasing order. Whenever we push, we pop all elements that violate the ordering. This finds the "next greater/smaller element" for every position in O(n).

C++
// Next Greater Element — for each i, find first j>i where arr[j]>arr[i]
vector<int> nextGreater(vector<int>& arr) {
    int n = arr.size();
    vector<int> res(n, -1);
    stack<int> st;   // stores indices, monotonically decreasing values
    for (int i = 0; i < n; i++) {
        while (!st.empty() && arr[i] > arr[st.top()]) {
            res[st.top()] = arr[i];   // arr[i] is NGE for st.top()
            st.pop();
        }
        st.push(i);
    }
    return res;
}
// arr={2,1,2,4,3} → NGE={4,2,4,-1,-1}
// Time: O(n) — each element pushed/popped once
// Space: O(n)
    

Interactive: Valid Parentheses Trace

Watch the stack grow and shrink as we scan {[()]} then (). Openers (purple) push to stack. Closers match the top and pop (green). Mismatch or non-empty stack at the end → invalid.

Deeper Understanding

🧠 Under the Hood

Both std::stack and std::queue are container adapters wrapping a deque by default. The underlying deque uses a doubly-linked list of fixed-size chunks, giving O(1) amortized push/pop at both ends with no contiguous-memory copies.

⚖️ When to Use / When NOT to Use

✅ Use stack for nesting, undo/redo, or iterative DFS

Anything recursive can be expressed with an explicit stack — useful when recursion depth may exceed OS stack limits (~10⁵ frames).

✅ Use queue for BFS, level-by-level processing, task scheduling

BFS with a queue guarantees shortest path in unweighted graphs — a DFS stack cannot do this.

✅ Use monotonic stack for "next greater/smaller element" in O(n)

Each element is pushed and popped at most once — the nested while loop is O(n) total, not O(n) per step.

❌ Avoid stack when random access or indexed lookup is needed

Instead: Use vector. Stack hides all elements except the top.

❌ Avoid queue when priority ordering is needed

Instead: Use priority_queue (heap). FIFO order is incompatible with priority-based extraction.

🚫 Common Misconceptions

❌ "std::stack is a container"

It's a container adapter — it wraps another container (deque by default). You can template the underlying type: stack<int, vector<int>> for better cache performance.

❌ "Recursion is separate from the call stack"

Every recursive call pushes a frame onto the OS call stack (local vars, return address, etc.). Converting recursion → explicit stack eliminates stack-overflow risk and is often faster.

❌ "Monotonic stack is O(n²) because of the inner while"

Each element is pushed once and popped at most once → total operations = 2n → O(n) amortized. The inner while never runs n times per outer iteration on average.

🎤 Interview Follow-ups

Implement a queue using two stacks

In-stack for push, out-stack for pop. When out-stack is empty, pour all of in-stack into it (reverses order). Amortized O(1) per operation — each element moves at most twice total.

Design MinStack with O(1) getMin()

Parallel min-stack: push min(val, minSt.top()) alongside every element. On pop, pop both stacks. Uses O(n) extra space but all four ops are O(1).

Why does DFS use a stack and BFS use a queue?

DFS explores depth-first (commit to a path, backtrack). A stack provides LIFO order — last discovered node is explored next. BFS needs FIFO to explore nodes in wave-fronts at equal distance from the source.

Practice Problems

#20Valid ParenthesesEasy

Given string of brackets, return true if every open bracket has a matching close bracket in correct order.

Pattern: Stack. Push open brackets. On close bracket, check stack top matches. Stack must be empty at end.

C++
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 top = st.top(); st.pop();
            if (c==')' && top!='(') return false;
            if (c=='}' && top!='{') return false;
            if (c==']' && top!='[') return false;
        }
    }
    return st.empty();
}
// Time: O(n)  Space: O(n)

#155Min StackMedium

Design stack that supports push, pop, top, and getMin — all in O(1).

Pattern: Two stacks. Main stack + auxiliary min stack. Min stack stores current minimum at each level.

C++
class MinStack {
    stack<int> st, minSt;
public:
    void push(int val) {
        st.push(val);
        int m = minSt.empty() ? val : min(val, minSt.top());
        minSt.push(m);
    }
    void pop()    { st.pop(); minSt.pop(); }
    int  top()    { return st.top(); }
    int  getMin() { return minSt.top(); }
};

#739Daily TemperaturesMedium

For each day i, how many days until a warmer temperature? Return as array.

Pattern: Monotonic stack of indices (decreasing temperatures). When we find a warmer day, resolve all waiting indices.

C++
vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> res(n, 0);
    stack<int> st;  // indices
    for (int i = 0; i < n; i++) {
        while (!st.empty() && T[i] > T[st.top()]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return res;
}
// Time: O(n)  Space: O(n)

#150Evaluate Reverse Polish NotationMedium

Evaluate ["2","1","+","3","*"] = (2+1)*3 = 9. Operands go to stack, operators pop two operands.

Pattern: Stack. Push numbers. On operator, pop two, apply operator, push result.

C++
int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (auto& t : tokens) {
        if (t=="+"||t=="-"||t=="*"||t=="/") {
            int b=st.top(); st.pop();
            int a=st.top(); st.pop();
            if      (t=="+") st.push(a+b);
            else if (t=="-") st.push(a-b);
            else if (t=="*") st.push(a*b);
            else             st.push(a/b);
        } else st.push(stoi(t));
    }
    return st.top();
}

#225Implement Stack using QueuesEasy

Implement a stack using only queue operations.

Pattern: One queue. On push, enqueue then rotate all n-1 elements to back, making new element the front.

C++
class MyStack {
    queue<int> q;
public:
    void push(int x) {
        q.push(x);
        for (int i = 0; i < q.size()-1; i++) {
            q.push(q.front()); q.pop();
        }
    }
    int  pop()  { int v=q.front(); q.pop(); return v; }
    int  top()  { return q.front(); }
    bool empty() { return q.empty(); }
};

#239Sliding Window MaximumHard

Given array and window size k, return max of each sliding window. Must be O(n).

Pattern: Monotonic deque. Maintain decreasing deque of indices. Front is always the window max. Remove indices outside window from front, smaller elements from back.

C++
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> dq;    // stores indices, front = max
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        // remove out-of-window from front
        while (!dq.empty() && dq.front() < i-k+1)
            dq.pop_front();
        // remove smaller elements from back
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();
        dq.push_back(i);
        if (i >= k-1) res.push_back(nums[dq.front()]);
    }
    return res;
}
// Time: O(n)  Space: O(k)

#232Implement Queue using StacksEasy

Implement a queue using only stack operations. Must be amortized O(1) per operation.

Pattern: Two stacks (in-stack and out-stack). Push to in. Pop: if out is empty, move all from in to out (reverses order), then pop from out.

C++
class MyQueue {
    stack<int> in, out;
    void transfer() {
        if (out.empty())
            while (!in.empty()) { out.push(in.top()); in.pop(); }
    }
public:
    void push(int x) { in.push(x); }
    int  pop()  { transfer(); int v=out.top(); out.pop(); return v; }
    int  peek() { transfer(); return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};

#84Largest Rectangle in HistogramHard

Given histogram bar heights, find largest rectangle area. Classic monotonic stack problem.

Pattern: Monotonic increasing stack. When a bar shorter than stack top appears, pop and calculate area with popped bar as height. Width = distance between current left boundary and i.

C++
int largestRectangleArea(vector<int>& heights) {
    stack<int> st;   // monotonically increasing
    heights.push_back(0);  // sentinel to flush stack
    int maxA = 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;
            maxA = max(maxA, h * w);
        }
        st.push(i);
    }
    return maxA;
}
// Time: O(n)  Space: O(n)

#394Decode StringMedium

Given encoded string like 3[a2[bc]], decode to abcbcabcbc. Brackets can nest arbitrarily deep.

Pattern: Stack of (count, built-string). On [: push current k and cur, reset both. On ]: pop, repeat cur k times, prepend prev string.

C++
string decodeString(string s) {
    stack<pair<int,string>> st;
    string cur = "";
    int k = 0;
    for (char c : s) {
        if      (isdigit(c)) k = k * 10 + (c - '0');
        else if (c == '[') { st.push({k, cur}); cur = ""; k = 0; }
        else if (c == ']') {
            auto [n, prev] = st.top(); st.pop();
            string rep; for (int i=0; i<n; i++) rep += cur;
            cur = prev + rep;
        } else cur += c;
    }
    return cur;
}
// "3[a2[bc]]" → "abcbcabcbc"   Time: O(n·k_max)  Space: O(n)

Interview tip: Monotonic stack is one of the hardest patterns to spot. Clue words: "next greater/smaller", "nearest", "previous larger", "skyline", "histogram area".