Stack & Queue

Concept

Stack is LIFO (Last In, First Out) — the most recently added element is removed first. Queue is FIFO (First In, First Out) — the earliest added element is removed first. Both support O(1) push and pop. Stack is used for DFS, expression evaluation, and monotonic stack problems. Queue is used for BFS and sliding window problems.

When to Use

  • ▸Stack — DFS (iterative), balanced parentheses, next greater element, undo operations
  • ▸Queue — BFS traversal, sliding window maximum, task scheduling
  • ▸Monotonic stack — next greater/smaller element in O(n)
  • ▸Deque — sliding window min/max in O(n)

Intuition

Stack is like a stack of plates — you can only add or remove from the top. Queue is like a line at a store — first person in line gets served first. Monotonic stack keeps elements in sorted order by popping elements that violate the order, efficiently finding 'next greater element' for every position in one pass.

Complexity

Time
O(1) per push/pop/top/front
Space
O(n)

Template Code

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

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- Stack: Balanced Parentheses ---
    string s;
    cin >> s;

    stack<char> st;
    bool valid = true;
    for(char c : s){
        if(c == '(' || c == '[' || c == '{'){
            st.push(c);
        }
        else{
            if(st.empty()){ valid = false; break; }
            char top = st.top();
            st.pop();
            if(c == ')' && top != '(') valid = false;
            if(c == ']' && top != '[') valid = false;
            if(c == '}' && top != '{') valid = false;
        }
    }
    if(!st.empty()) valid = false;
    cout << (valid ? "YES" : "NO") << "\n";

    // --- Queue: BFS Level Order ---
    // queue<int> q;
    // q.push(start);
    // while(!q.empty()){
    //     int u = q.front();
    //     q.pop();
    //     for(int x : adj[u]){
    //         q.push(x);
    //     }
    // }

    // --- Monotonic Stack: Next Greater Element ---
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    vector<int> ans(n, -1);
    stack<int> mono;  // stores indices

    for(int i = 0; i < n; i++){
        while(!mono.empty() && v[mono.top()] < v[i]){
            ans[mono.top()] = v[i];
            mono.pop();
        }
        mono.push(i);
    }

    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    cout << "\n";

    return 0;
}

// Sample Input:
// ({[]})
// 5
// 4 2 6 1 5
//
// Sample Output:
// YES
// 6 6 -1 5 -1