Implement a Stack Using Queues

class Stack {
    queue q1, q2;
public:
    void push(int x) {
        q1.push(x);
    }
    
    int pop() {
        if (q1.empty()) return -1;
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int top = q1.front();
        q1.pop();
        swap(q1, q2);
        return top;
    }

    int top() {
        if (q1.empty()) return -1;
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        int top = q1.front();
        q2.push(top);
        swap(q1, q2);
        return top;
    }

    bool empty() {
        return q1.empty();
    }
};
            

Implement a Queue Using Stacks

class Queue {
    stack s1, s2;
public:
    void enqueue(int x) {
        s1.push(x);
    }

    int dequeue() {
        if (s2.empty()) {
            if (s1.empty()) return -1; 
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int front = s2.top();
        s2.pop();
        return front;
    }

    bool empty() {
        return s1.empty() && s2.empty();
    }
};
            

Evaluate a Postfix Expression

int evaluatePostfix(string expression) {
    stack st;
    for (char c : expression) {
        if (isdigit(c)) {
            st.push(c - '0');
        } else {
            int val2 = st.top(); st.pop();
            int val1 = st.top(); st.pop();
            switch (c) {
                case '+': st.push(val1 + val2); break;
                case '-': st.push(val1 - val2); break;
                case '*': st.push(val1 * val2); break;
                case '/': st.push(val1 / val2); break;
            }
        }
    }
    return st.top();
}
            

Evaluate a Prefix Expression

int evaluatePrefix(string expression) {
    stack st;
    reverse(expression.begin(), expression.end());
    for (char c : expression) {
        if (isdigit(c)) {
            st.push(c - '0');
        } else {
            int val1 = st.top(); st.pop();
            int val2 = st.top(); st.pop();
            switch (c) {
                case '+': st.push(val1 + val2); break;
                case '-': st.push(val1 - val2); break;
                case '*': st.push(val1 * val2); break;
                case '/': st.push(val1 / val2); break;
            }
        }
    }
    return st.top();
}
            

Valid Parentheses (Balanced Parentheses)

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

Next Greater Element

vector nextGreaterElement(vector& nums) {
    stack st;
    vector result(nums.size(), -1);
    for (int i = 0; i < nums.size(); i++) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            result[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}
            

Sliding Window Maximum

vector maxSlidingWindow(vector& nums, int k) {
    deque dq;
    vector result;
    for (int i = 0; i < nums.size(); i++) {
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
        while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}
            

Design a Circular Queue

class CircularQueue {
    vector queue;
    int front, rear, size;
public:
    CircularQueue(int k) {
        size = k + 1;
        queue = vector(size, 0);
        front = 0;
        rear = 0;
    }
    
    bool enQueue(int value) {
        if ((rear + 1) % size == front) return false;
        queue[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }
    
    bool deQueue() {
        if (front == rear) return false;
        front = (front + 1) % size;
        return true;
    }
    
    int Front() {
        if (front == rear) return -1;
        return queue[front];
    }

    int Rear() {
        if (front == rear) return -1;
        return queue[(rear - 1 + size) % size];
    }

    bool isEmpty() {
        return front == rear;
    }

    bool isFull() {
        return (rear + 1) % size == front;
    }
};
            

Reverse a Stack Using Recursion

void reverseStack(stack& st) {
    if (st.empty()) return;
    int top = st.top();
    st.pop();
    reverseStack(st);
    insertAtBottom(st, top);
}

void insertAtBottom(stack& st, int x) {
    if (st.empty()) {
        st.push(x);
    } else {
        int top = st.top();
        st.pop();
        insertAtBottom(st, x);
        st.push(top);
    }
}
            

Design a Stack that Supports Push, Pop, and Retrieving the Minimum Element in Constant Time

class MinStack {
    stack st, minSt;
public:
    void push(int val) {
        st.push(val);
        if (minSt.empty() || val <= minSt.top()) minSt.push(val);
    }
    
    void pop() {
        if (st.top() == minSt.top()) minSt.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minSt.top();
    }
};
            

Design a Queue Using Two Stacks

class QueueUsingTwoStacks {
    stack s1, s2;
public:
    void enqueue(int x) {
        s1.push(x);
    }

    int dequeue() {
        if (s2.empty()) {
            if (s1.empty()) return -1;
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int front = s2.top();
        s2.pop();
        return front;
    }
};
            

Daily Temperature (Next Greater Temperature Problem)

vector dailyTemperatures(vector& temperatures) {
    stack st;
    vector result(temperatures.size(), 0);
    for (int i = 0; i < temperatures.size(); i++) {
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int idx = st.top();
            st.pop();
            result[idx] = i - idx;
        }
        st.push(i);
    }
    return result;
}
            

Find the Largest Rectangle in a Histogram

int largestRectangleArea(vector& heights) {
    stack st;
    int maxArea = 0, i = 0;
    while (i < heights.size()) {
        if (st.empty() || heights[i] >= heights[st.top()]) {
            st.push(i++);
        } else {
            int top = st.top();
            st.pop();
            maxArea = max(maxArea, heights[top] * (st.empty() ? i : i - st.top() - 1));
        }
    }
    while (!st.empty()) {
        int top = st.top();
        st.pop();
        maxArea = max(maxArea, heights[top] * (st.empty() ? i : i - st.top() - 1));
    }
    return maxArea;
}