Stacks, Queues & Monotonic Structures

Stack: last in, first out

A stack supports push, pop and peek at one end, all O(1). Think of a pile of plates.

stack = []
stack.append(1)        # push
top = stack[-1]        # peek
stack.pop()            # pop
if not stack: ...      # empty check

stack<int> st;         // or just use vector<int> with push_back/pop_back/back
st.push(1);
int top = st.top();
st.pop();
if (st.empty()) { }

Queue: first in, first out

from collections import deque
q = deque()
q.append(1)            # enqueue at the back
front = q[0]
q.popleft()            # dequeue from the front, O(1)
q.appendleft(0)        # deque = double-ended: works at both ends

queue<int> q;  q.push(1);  q.front();  q.pop();
deque<int> dq; dq.push_back(1); dq.push_front(0); dq.pop_back(); dq.pop_front();

Queues power BFS (see Graphs) and any simulation where things are processed in arrival order.

Classic stack problems

Bracket matching

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

bool isValid(string s) {
    unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
    vector<char> st;
    for (char c : s) {
        if (pairs.count(c)) {
            if (st.empty() || st.back() != pairs[c]) return false;
            st.pop_back();
        } else st.push_back(c);
    }
    return st.empty();
}

Variants: Minimum Remove to Make Valid Parentheses (push indices of unmatched (), Longest Valid Parentheses (stack of indices seeded with −1).

Min stack

Store the running minimum alongside each value so getMin is O(1).

class MinStack:
    def __init__(self):
        self.st = []                       # (value, min_so_far)
    def push(self, x):
        m = min(x, self.st[-1][1]) if self.st else x
        self.st.append((x, m))
    def pop(self):
        self.st.pop()
    def top(self):
        return self.st[-1][0]
    def getMin(self):
        return self.st[-1][1]

Nested structures: save context on the stack

When you enter a nested level, push the current context; when you leave, pop and merge.

def decode_string(s):
    stack, cur, num = [], "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            stack.append((cur, num))
            cur, num = "", 0
        elif ch == "]":
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

Expression evaluation

• Reverse Polish notation: push numbers, operators pop two operands.
• Infix with + − and parentheses: keep result and sign; on ( push them and reset.
• Infix with + − × ÷: push signed terms; apply × and ÷ immediately to the top; sum the stack at the end.

def calculate(s):             # handles + - * / (no parentheses)
    stack, num, op = [], 0, "+"
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if ch in "+-*/" or i == len(s) - 1:
            if op == "+": stack.append(num)
            elif op == "-": stack.append(-num)
            elif op == "*": stack.append(stack.pop() * num)
            else: stack.append(int(stack.pop() / num))   # truncate toward 0
            op, num = ch, 0
    return sum(stack)

Monotonic stack

A stack whose contents are kept sorted (increasing or decreasing). Before pushing a new element, pop everything that violates the order. The popped elements have just found their answer: the new element is their next greater (or smaller) element.

Template: next greater element to the right

def next_greater(nums):
    n = len(nums)
    ans = [-1] * n
    stack = []                                 # indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:   # x is the answer for these
            ans[stack.pop()] = x
        stack.append(i)
    return ans

vector<int> nextGreater(const vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1), st;              // st holds indices
    for (int i = 0; i < n; i++) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            ans[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}

Which variant do I need?

Use < vs <= deliberately to decide how ties are handled — it matters when counting subarrays to avoid double counting.

Largest rectangle in a histogram

For each bar, the widest rectangle using its full height extends left and right until a shorter bar. An increasing stack finds both boundaries: when bar j is popped by i, its right boundary is i and its left boundary is the new top.

def largest_rectangle(heights):
    stack, best = [], 0               # increasing heights (indices)
    for i, h in enumerate(heights + [0]):      # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

int largestRectangleArea(vector<int> h) {
    h.push_back(0);
    vector<int> st;
    int best = 0;
    for (int i = 0; i < (int)h.size(); i++) {
        while (!st.empty() && h[st.back()] > h[i]) {
            int height = h[st.back()]; st.pop_back();
            int left = st.empty() ? -1 : st.back();
            best = max(best, height * (i - left - 1));
        }
        st.push_back(i);
    }
    return best;
}

Contribution technique: sum of subarray minimums

Instead of enumerating subarrays, ask for how many subarrays is a[i] the minimum? If L = distance to previous strictly smaller and R = distance to next smaller-or-equal, then a[i] is the min of L × R subarrays.

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    left, right = [0] * n, [0] * n
    st = []
    for i in range(n):                         # previous strictly smaller
        while st and arr[st[-1]] >= arr[i]:
            st.pop()
        left[i] = i - (st[-1] if st else -1)
        st.append(i)
    st = []
    for i in range(n - 1, -1, -1):             # next smaller or equal
        while st and arr[st[-1]] > arr[i]:
            st.pop()
        right[i] = (st[-1] if st else n) - i
        st.append(i)
    return sum(a * l * r for a, l, r in zip(arr, left, right)) % MOD

The asymmetric >= / > ensures equal values are counted exactly once.

Monotonic deque: sliding window max/min

Keep indices in a deque with decreasing values. The front is the current window's maximum. Pop from the back anything smaller than the new element (it can never be a max again), and pop from the front when it slides out of the window.

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:           # front left the window
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

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

O(n) total. The monotonic deque also optimizes DP transitions of the form dp[i] = max(dp[j]) + cost over a sliding range of j (e.g. Jump Game VI, Constrained Subsequence Sum).

Building one structure from another

• Queue from two stacks: push to inbox; to pop, if outbox is empty pour all of inbox into it, then pop outbox. Each element moves at most twice → amortized O(1).
• Stack from queues: after pushing x, rotate the queue n−1 times so x is at the front.

Common mistakes

• Popping from an empty stack — always check stack / !st.empty() first.
• Storing values when you need indices (for widths or distances). Store indices; you can always look up the value.
• Forgetting to flush the stack at the end (use a sentinel like the 0 bar).
• Tie handling (< vs <=) causing double counting in contribution problems.
• Python integer division: -7 // 2 == -4. For truncation toward zero use int(a / b).