C++ In Practice - Stack Based Problems

Stack-Based Problems (C++11 Deep Dive)

In C++, std::stack is a Container Adaptor, not a standalone container. It provides a restricted interface (push/pop/top) over an underlying sequence container.

C++11 Architecture: std::stack vs. std::vector

1. std::stack<T> (The Default)

• Under the Hood: By default, it wraps std::deque<T> (Double-Ended Queue).
• Why Deque? Deques allocate memory in disconnected chunks (pages). This prevents the massive "reallocate-and-copy" cost that std::vector incurs when it exceeds capacity. It offers consistent O(1) push performance.
• Usage: Use when you strictly need LIFO semantics and no iteration.

2. std::vector<T> as a Stack

• Under the Hood: Contiguous memory. Excellent cache locality.
• Operations: push_back(), pop_back(), back().
• Usage: Preferred in high-performance scenarios (competitive programming, embedded) or when you need to reserve memory upfront (v.reserve(N)) to prevent allocations entirely.

---

1. Valid Parentheses

Problem: Balanced brackets ()[]{}.

Complexity: Time O(N) | Space O(N).

C++11 Optimization: Avoid std::map or std::unordered_map for looking up matching brackets. The overhead of hashing or tree traversal is unnecessary for 3 pairs. Use a simple switch or ASCII math.

#include <stack>
#include <string>

bool isValid(std::string s) {
    // Optimization: Odd length can never be balanced
    if (s.size() % 2 != 0) return false;

    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char open = st.top();
            if ((c == ')' && open != '(') ||
                (c == '}' && open != '{') ||
                (c == ']' && open != '[')) {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}

---

2. Min Stack

Problem: Stack with O(1) getMin.

Approach: Store pairs {value, current_min}.

C++11 Implementation: We use std::pair within the stack.

#include <stack>
#include <utility> // for std::pair
#include <algorithm> // for std::min

class MinStack {
    // Pair: <Value, Minimum at this depth>
    std::stack<std::pair<int, int>> st;

public:
    void push(int val) {
        int newMin;
        if (st.empty()) {
            newMin = val;
        } else {
            newMin = std::min(val, st.top().second);
        }
        st.push({val, newMin});
    }

    void pop() {
        if (!st.empty()) st.pop();
    }

    int top() {
        return st.top().first;
    }

    int getMin() {
        return st.top().second;
    }
};

---

3. Evaluate Reverse Polish Notation (RPN)

Problem: Postfix evaluation "2 1 + 3 *" -> (2+1)*3 -> 9.

Complexity: Time O(N) | Space O(N).

C++11 Detail: Input is usually vector<string>. We need std::stoi to parse numbers.

#include <vector>
#include <string>
#include <stack>

int evalRPN(std::vector<std::string>& tokens) {
    std::stack<int> st;

    for (const std::string& token : tokens) {
        // Check if token is an operator
        // Note: Check length > 1 to distinguish negative numbers ("-5") from operator ("-")
        if (token.size() == 1 && std::string("+-*/").find(token) != std::string::npos) {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            
            if (token == "+") st.push(a + b);
            else if (token == "-") st.push(a - b);
            else if (token == "*") st.push(a * b);
            else if (token == "/") st.push(a / b); // C++ integer division truncates toward zero
        } else {
            st.push(std::stoi(token));
        }
    }
    return st.top();
}

---

4. Monotonic Stack: Daily Temperatures

Problem: Days until warmer temperature.

Pattern: Monotonic Decreasing Stack (stores indices).

Complexity: Time O(N) | Space O(N).

Logic: We store indices of days that haven't found a warmer day yet. If we see a warmer day, we "resolve" the waiting days.

#include <vector>
#include <stack>

std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {
    int n = temperatures.size();
    std::vector<int> result(n, 0);
    std::stack<int> st; // Stores indices

    for (int i = 0; i < n; ++i) {
        // While current temp is warmer than the temp at stack top index
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int prevIndex = st.top();
            st.pop();
            result[prevIndex] = i - prevIndex;
        }
        st.push(i);
    }
    return result;
}

---

5. Largest Rectangle in Histogram

Problem: Max area in histogram.

Pattern: Monotonic Increasing Stack.

Complexity: Time O(N) | Space O(N).

Key Insight: For a bar at index i with height h, if we know the first index to the left with height < h (L) and the first index to the right with height < h (R), the area using bar i as the full height is h * (R - L - 1).

C++11 Implementation Trick: Append a 0 height bar to the end of the vector. This forces the stack to empty completely, processing all remaining bars without a separate loop after the main loop.

#include <vector>
#include <stack>
#include <algorithm>

int largestRectangleArea(std::vector<int>& heights) {
    // Add sentinel to force pop all elements at the end
    heights.push_back(0); 
    int n = heights.size();
    int maxArea = 0;
    std::stack<int> st; // Stores indices

    for (int i = 0; i < n; ++i) {
        // Maintain monotonic increasing order
        // If current height < top height, we found the Right Boundary for 'top'
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()];
            st.pop();
            
            // Width calculation:
            // Right Boundary: i
            // Left Boundary: st.top() (after pop). If empty, left boundary is -1.
            int w = st.empty() ? i : (i - st.top() - 1);
            
            maxArea = std::max(maxArea, h * w);
        }
        st.push(i);
    }
    
    return maxArea;
}

---

6. Next Greater Element

Problem: Find next larger value in linear time. Pattern: Monotonic Decreasing Stack. Complexity: Time O(N) | Space O(N).

#include <vector>
#include <stack>
#include <unordered_map>

std::vector<int> nextGreaterElement(std::vector<int>& findNums, std::vector<int>& nums) {
    std::unordered_map<int, int> nextMap; // Value -> Next Greater Value
    std::stack<int> st;

    for (int num : nums) {
        while (!st.empty() && num > st.top()) {
            nextMap[st.top()] = num;
            st.pop();
        }
        st.push(num);
    }

    // Map result back to findingNums
    std::vector<int> result;
    for (int num : findNums) {
        if (nextMap.count(num)) {
            result.push_back(nextMap[num]);
        } else {
            result.push_back(-1);
        }
    }
    return result;
}

Summary of Stack Patterns

Problem Type	Stack Type	Content	Trigger Condition
Parsing	Standard	Values/Operators	Operator precedence or matching bracket.
History/Min	Standard (Pairs)	{val, min}	push / pop always.
Next Greater	Monotonic Decreasing	Indices/Values	current > top (Violation of decrease).
Next Smaller	Monotonic Increasing	Indices/Values	current < top (Violation of increase).
Histogram Area	Monotonic Increasing	Indices	current < top (Calculates area for top).