SyntaxShelf
DSA

Stacks & Queues

Interview Prep · 6 entries

Valid Parentheses

syntax
Push opening brackets onto stack.
For closing brackets, check if top of stack is the matching opener.
At end, stack must be empty.
example
// JavaScript
function isValid(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of s) {
    if ('([{'.includes(ch)) {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

# Python
def is_valid(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0
output
is_valid('({[]})') → True
is_valid('([)]') → False

Note Time O(n), Space O(n). Edge cases: empty string (valid), single character (invalid), only opening brackets (invalid). This is the quintessential stack problem — if you see matching/nesting, think stack.

valid parenthesesbalanced bracketsstack matchingbracket validation

Min Stack

syntax
Maintain a secondary stack that tracks the current minimum.
When pushing, also push to min stack if value <= current min.
When popping, also pop from min stack if value equals current min.
example
// JavaScript
class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [];
  }
  push(val) {
    this.stack.push(val);
    const curMin = this.minStack.length === 0
      ? val : Math.min(val, this.minStack[this.minStack.length - 1]);
    this.minStack.push(curMin);
  }
  pop() {
    this.stack.pop();
    this.minStack.pop();
  }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

# Python
class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        cur_min = min(val, self.min_stack[-1]) if self.min_stack else val
        self.min_stack.append(cur_min)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def get_min(self):
        return self.min_stack[-1]
output
push(5), push(3), push(7)
getMin() → 3
pop() → removes 7
getMin() → 3
pop() → removes 3
getMin() → 5

Note All operations O(1) time, O(n) extra space for the min stack. The trick: each entry in min_stack stores the minimum at that height of the main stack. Alternative: store (value, currentMin) tuples in one stack.

min stackminimum stackstack with getMinO(1) minimum

Evaluate Reverse Polish Notation

syntax
Process tokens left to right.
Numbers: push onto stack.
Operators: pop two operands, apply operator, push result.
example
// JavaScript
function evalRPN(tokens) {
  const stack = [];
  const ops = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => Math.trunc(a / b),
  };
  for (const token of tokens) {
    if (token in ops) {
      const b = stack.pop(), a = stack.pop();
      stack.push(ops[token](a, b));
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

# Python
def eval_rpn(tokens):
    stack = []
    ops = {'+', '-', '*', '/'}
    for token in tokens:
        if token in ops:
            b, a = stack.pop(), stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            else: stack.append(int(a / b))  # truncate toward zero
        else:
            stack.append(int(token))
    return stack[0]
output
evalRPN(['2','1','+','3','*']) → 9
((2+1)*3 = 9)

Note Time O(n), Space O(n). Watch out: division truncates toward zero (not floor). Order matters: first popped is right operand, second popped is left. For infix to postfix conversion, use the Shunting Yard algorithm.

reverse polish notationevaluate expressionstack calculatorpostfix evaluation

Next Greater Element (Monotonic Stack)

syntax
Traverse from right to left (or left to right).
Maintain a decreasing stack.
For each element, pop smaller elements — the top is the next greater.
example
// JavaScript
function nextGreaterElements(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = []; // stores indices
  for (let i = 0; i < arr.length; i++) {
    while (stack.length > 0 && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

# Python
def next_greater_elements(arr):
    result = [-1] * len(arr)
    stack = []  # stores indices
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result
output
next_greater_elements([4, 5, 2, 10, 8]) → [5, 10, 10, -1, -1]

Note Time O(n), Space O(n). Each element is pushed and popped at most once. Used in: stock span, daily temperatures, histogram problems. For circular arrays, iterate through the array twice (use i % n).

next greater elementmonotonic stackdaily temperaturesstock span

BFS with Queue

syntax
Use a queue (FIFO) for breadth-first traversal.
Process level by level.
Enqueue neighbors/children, dequeue to process.
example
// JavaScript — BFS level order traversal of binary tree
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

# Python
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result
output
Tree:    3
       / \
      9  20
→ [[3], [9, 20]]

Note Time O(n), Space O(n). Use deque in Python for O(1) popleft — list.pop(0) is O(n). The 'capture level size' trick (for loop with current queue length) lets you process one level at a time. BFS is the go-to for shortest path in unweighted graphs.

BFS queuelevel order traversalbreadth first searchqueue

Monotonic Stack Pattern

syntax
A stack that maintains elements in sorted order (increasing or decreasing).
Before pushing, pop all elements that violate the ordering.
Used for: next greater/smaller, largest rectangle in histogram.
example
// JavaScript — Largest rectangle in histogram
function largestRectangle(heights) {
  const stack = []; // indices of increasing heights
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i < heights.length ? heights[i] : 0;
    while (stack.length > 0 && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

# Python
def largest_rectangle(heights):
    stack = []
    max_area = 0
    for i in range(len(heights) + 1):
        h = heights[i] if i < len(heights) else 0
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area
output
largest_rectangle([2,1,5,6,2,3]) → 10 (height 5, width 2)

Note Time O(n), Space O(n). The sentinel value (appending 0 at the end) forces all remaining bars to be processed. This is a hard problem but the monotonic stack template is reusable. Variant: maximal rectangle in a binary matrix applies this per row.

monotonic stacklargest rectangle histogramincreasing stackdecreasing stack