stack_queue.cpp

/*
Stack & Queue Standard Operations
Mathematical Foundation: LIFO (stack) vs FIFO (queue)
Stack: push/pop O(1), queue: enqueue/dequeue O(1)
Applications: Expression parsing, BFS/DFS, monotonic stack/queue
*/

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

// Min Stack
// LeetCode: 155. Min Stack
// https://leetcode.com/problems/min-stack/
class MinStack {
    stack<int> st, mn;
public:
    void push(int x) { st.push(x); mn.push(mn.empty() ? x : min(x, mn.top())); }
    void pop() { st.pop(); mn.pop(); }
    int top() { return st.top(); }
    int getMin() { return mn.top(); }
};

// Valid Parentheses
// LeetCode: 20. Valid Parentheses
// https://leetcode.com/problems/valid-parentheses/
bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (st.empty() || (c == ')' && st.top() != '(') || 
                 (c == ']' && st.top() != '[') || (c == '}' && st.top() != '{')) return false;
        else st.pop();
    }
    return st.empty();
}

// Largest Rectangle in Histogram
// LeetCode: 84. Largest Rectangle in Histogram
// https://leetcode.com/problems/largest-rectangle-in-histogram/
int largestRectangleArea(vector<int>& h) {
    h.push_back(0);
    stack<int> st;
    int mx = 0;
    for (int i = 0; i < h.size(); i++) {
        while (!st.empty() && h[st.top()] > h[i]) {
            int ht = h[st.top()]; st.pop();
            int w = st.empty() ? i : i - st.top() - 1;
            mx = max(mx, ht * w);
        }
        st.push(i);
    }
    return mx;
}

// Daily Temperatures (Monotonic Stack)
// LeetCode: 739. Daily Temperatures
// https://leetcode.com/problems/daily-temperatures/
vector<int> dailyTemperatures(vector<int>& t) {
    vector<int> res(t.size());
    stack<int> st;
    for (int i = 0; i < t.size(); i++) {
        while (!st.empty() && t[st.top()] < t[i]) {
            res[st.top()] = i - st.top();
            st.pop();
        }
        st.push(i);
    }
    return res;
}

// Next Greater Element
// LeetCode: 496. Next Greater Element I
// https://leetcode.com/problems/next-greater-element-i/
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int,int> mp;
    stack<int> st;
    for (int x : nums2) {
        while (!st.empty() && st.top() < x) {
            mp[st.top()] = x;
            st.pop();
        }
        st.push(x);
    }
    vector<int> res;
    for (int x : nums1) res.push_back(mp.count(x) ? mp[x] : -1);
    return res;
}

// Implement Queue using Stacks
// LeetCode: 232. Implement Queue using Stacks
// https://leetcode.com/problems/implement-queue-using-stacks/
class MyQueue {
    stack<int> in, out;
public:
    void push(int x) { in.push(x); }
    int pop() { peek(); int x = out.top(); out.pop(); return x; }
    int peek() { if (out.empty()) while (!in.empty()) { out.push(in.top()); in.pop(); } return out.top(); }
    bool empty() { return in.empty() && out.empty(); }
};

// Implement Stack using Queues
// LeetCode: 225. Implement Stack using Queues
// https://leetcode.com/problems/implement-stack-using-queues/
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 x = q.front(); q.pop(); return x; }
    int top() { return q.front(); }
    bool empty() { return q.empty(); }
};

// Sliding Window Maximum (Deque)
// LeetCode: 239. Sliding Window Maximum
// https://leetcode.com/problems/sliding-window-maximum/
vector<int> maxSlidingWindow(vector<int>& a, int k) {
    deque<int> dq;
    vector<int> res;
    for (int i = 0; i < a.size(); i++) {
        while (!dq.empty() && dq.front() <= i - k) dq.pop_front();
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}