Stack & Queue Puzzles

A regular stack only supports top, push, and pop — querying the minimum requires a full scan in O(n). The MinStack achieves O(1) minimum access with an auxiliary tracking stack.

Maintain a second minStack that mirrors the main stack. On each push, compute the new minimum (min of the value and the current minStack top) and push it to minStack.

On pop, pop both stacks simultaneously so minStack always reflects the minimum of everything currently in the main stack.

All four operations (push, pop, top, getMin) are O(1) because there is no iteration.

class MinStack {
  constructor() { this.stack = []; this.minStack = []; }
  push(val) {
    this.stack.push(val);
    this.minStack.push(Math.min(val, this.getMin() ?? Infinity));
  }
  pop() { this.stack.pop(); this.minStack.pop(); }
  top() { return this.stack[this.stack.length - 1]; }
  getMin() { return this.minStack[this.minStack.length - 1]; }
}

Mirror minimum stack: Each position in minStack tells you "what is the minimum in the main stack at this depth?" — popping both keeps the invariant intact.

Space is O(n) for the auxiliary stack. An optimization stores only changed minimums with counts to reduce space for repeated values.

For each element in an array, find the first element to its right that is strictly greater than it. If none exists, the answer is -1.

Use a monotonic decreasing stack storing indices. For each new element, pop all indices from the stack whose values are less than the current element — those elements found their answer.

Elements that remain in the stack by the end of the loop never found a greater element to their right, so they keep the default -1.

This runs in O(n) time — each element is pushed and popped at most once.

function nextGreater(arr) {
  let res = Array(arr.length).fill(-1), stack = [];
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length-1]] < arr[i])
      res[stack.pop()] = arr[i];
    stack.push(i);
  }
  return res;
}

Store indices, not values: Keeping indices on the stack lets you directly set the result array at the correct position when an element is resolved.

For a circular array variant, iterate through 2n indices with modulo to allow elements near the end to "see" elements at the beginning.

A queue is FIFO (first in, first out) while a stack is LIFO (last in, first out). Two stacks can simulate a queue by reversing the order via a double reversal.

Use stack S1 for enqueue. When dequeuing, if S2 is empty, transfer all elements from S1 to S2 (reversing their order). Then pop from S2, which is now in FIFO order.

Elements are transferred lazily — only when S2 is empty — making the amortized cost of dequeue O(1) even though individual operations may take O(n).

Enqueue is always O(1) worst case; dequeue is O(n) worst case but O(1) amortized.

class QueueFromStacks {
  constructor() { this.s1 = []; this.s2 = []; }
  enqueue(val) { this.s1.push(val); }
  dequeue() {
    if (!this.s2.length) while (this.s1.length) this.s2.push(this.s1.pop());
    return this.s2.pop();
  }
}

Lazy transfer: Only move S1 to S2 when S2 is empty — this batching is what makes the amortized O(1) dequeue possible.

Peek is implemented identically to dequeue but without popping — return this.s2[this.s2.length-1] after the same lazy transfer.

A stack is LIFO while a queue is FIFO. Implementing a stack with queues requires ensuring the most recently pushed element is always at the front of the active queue.

On push: enqueue the new element into Q2, then transfer all of Q1 into Q2 (so the new element is at the back, but all old elements are behind it), then swap Q1 and Q2 references.

After each push, Q1 holds elements in stack order (newest to oldest), so pop and peek just remove/view the front of Q1.

Push is O(n); pop is O(1). An alternative makes push O(1) and pop O(n) by transferring on dequeue.

class StackFromQueues {
  constructor() { this.q1 = []; this.q2 = []; }
  push(val) {
    this.q2.push(val);
    while (this.q1.length) this.q2.push(this.q1.shift());
    [this.q1, this.q2] = [this.q2, this.q1];
  }
  pop() { return this.q1.shift(); }
}

Reverse on push: Transferring existing Q1 elements after the new element into Q2 puts the new element first in a fresh Q1 after the swap — maintaining LIFO order.

Swapping references with destructuring avoids copying and makes the operation O(1) for the swap itself, only paying O(n) for the queue transfer.

Postfix (Reverse Polish Notation) places operators after their operands: 3 4 + equals 7. It eliminates the need for parentheses and operator precedence rules.

Use a stack. Scan left to right: if the token is a number, push it. If it is an operator, pop two operands, apply the operator, and push the result.

The two operands must be popped in the correct order: the last-pushed operand is the right operand (b), and the one before it is the left operand (a).

This runs in O(n) time and O(n) space for the stack, and handles all arithmetic expressions without needing recursion.

function evalPostfix(tokens) {
  let stack = [];
  for (let t of tokens) {
    if ('+-*/'.includes(t)) {
      let b = stack.pop(), a = stack.pop();
      if (t === '+') stack.push(a + b);
      else if (t === '-') stack.push(a - b);
      else if (t === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else stack.push(Number(t));
  }
  return stack[0];
}

Pop order matters: The last pushed value is the right operand (b) and the one before it is the left operand (a) — reversing them would produce wrong results for non-commutative operators.

Use Math.trunc for division to match the expected behavior of integer truncation toward zero as specified in most RPN problems.

Without random access, sorting a stack requires O(n²) time using only another stack as auxiliary storage.

Repeatedly pick the top element from the original stack and insert it into the correct position in the temp stack by moving elements back to the original temporarily.

When inserting a value into temp: if temp's top is greater, move it back to the original stack, insert the value, then restore those moved elements.

This resembles insertion sort — O(n²) time but only O(n) extra space (one auxiliary stack).

function sortStack(stack) {
  let temp = [];
  while (stack.length) {
    let val = stack.pop();
    while (temp.length && temp[temp.length-1] > val) stack.push(temp.pop());
    temp.push(val);
  }
  return temp;
}

Insertion sort analogy: The inner while loop moves elements back to maintain sorted order in temp — each outer iteration places one element in its correct sorted position.

The resulting temp stack has the smallest element at the top (ascending from top to bottom). Reverse the logic to sort descending.

The stock span for a given day is the number of consecutive days before it (including itself) where the price was less than or equal to today's price.

Use a monotonic decreasing stack storing indices. For each day, pop all days that have lower or equal prices — they cannot block the span further.

The span is either the current index plus one (stack empty, all previous days are covered) or the difference between current and the top remaining index.

This is an O(n) solution — each index is pushed and popped at most once, so the total work across all days is O(n).

function stockSpan(prices) {
  let span = [], stack = [];
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && prices[stack[stack.length-1]] <= prices[i]) stack.pop();
    span.push(stack.length ? i - stack[stack.length-1] : i + 1);
    stack.push(i);
  }
  return span;
}

Stack stores indices that block span: Only days with strictly higher prices remain on the stack, as they are the barriers that define the span boundary.

This is equivalent to finding the "previous greater element" for each day, which is a canonical monotonic stack problem pattern.

Given a histogram (array of bar heights), find the largest rectangle that can be formed using contiguous bars.

Use a monotonic increasing stack. When a bar shorter than the top of the stack is found, the top bar can no longer extend to the right — calculate its area using the current index and the new top of the stack as width boundaries.

Append a sentinel value of 0 to force all remaining bars to be processed at the end of the array.

Each bar is pushed and popped exactly once — O(n) time and O(n) space for the stack.

function largestRectangle(heights) {
  let stack = [], max = 0;
  heights.push(0);
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[stack[stack.length-1]] > heights[i]) {
      let h = heights[stack.pop()];
      let w = stack.length ? i - stack[stack.length-1] - 1 : i;
      max = Math.max(max, h * w);
    }
    stack.push(i);
  }
  return max;
}

Width calculation: When popping index k, the width of the rectangle is i - stack.top - 1 — the space between the new stack top (first bar shorter than height[k]) and the current position.

The same technique is used in "Maximal Rectangle in a Binary Matrix" by treating each row as a histogram and applying this algorithm row by row.

An LRU (Least Recently Used) cache stores a limited number of items. When it is full and a new item is added, the least recently accessed item is evicted first.

JavaScript's Map maintains insertion order, which makes it ideal for an LRU cache: deletion and re-insertion of an accessed key moves it to the "most recent" end.

When the map exceeds capacity, evict by deleting map.keys().next().value — the oldest key at the front of the insertion order.

Both get and put operations run in O(1) time due to Map's hash-based lookups.

class LRU {
  constructor(cap) { this.cap = cap; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    let val = this.map.get(key);
    this.map.delete(key); this.map.set(key, val);
    return val;
  }
  put(key, val) {
    this.map.delete(key);
    this.map.set(key, val);
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value);
  }
}

Map insertion order: JavaScript's Map iterates keys in insertion order — re-inserting on access promotes the key to most-recent, making eviction of the oldest trivial.

In production systems, LRU caches are used for database query results, DNS lookups, and web page caches to reduce expensive recomputations.

Encoded strings like "3[a2[bc]]" represent "abcbcabcbcabcbc" — each integer before brackets is a repetition count for the enclosed string.

Use a stack to handle nesting. When you encounter a [, push the current string and current count onto stacks and reset them. When you encounter a ], pop and repeat the current string by the saved count, then prepend the saved string.

This handles arbitrary nesting depth because the stack naturally tracks the parent context at each level.

Time complexity is O(maxRepetition × n) in the worst case; space is O(n) for the stack.

function decodeString(s) {
  let stack = [], curr = '', k = 0;
  for (let c of s) {
    if (c >= '0' && c <= '9') {
      k = k * 10 + Number(c);
    } else if (c === '[') {
      stack.push([curr, k]); curr = ''; k = 0;
    } else if (c === ']') {
      let [prev, count] = stack.pop();
      curr = prev + curr.repeat(count);
    } else curr += c;
  }
  return curr;
}

Stack for nested context: Push (current string, count) before entering a bracket, pop and multiply after closing — this handles any depth of nesting.

Multi-digit numbers like 12[a] are handled by k = k * 10 + digit before each [ is encountered.

Given a number string and k deletions, remove exactly k digits to make the resulting number as small as possible while maintaining digit order.

Use a monotonic increasing stack. For each digit, pop larger digits from the stack while k > 0 (remove them). Push the current digit and continue. After processing, remove remaining digits from the stack end if k > 0.

Strip leading zeros from the result. If the result is empty, return "0".

This runs in O(n) time and O(n) space for the stack.

function removeKdigits(num, k) {
  let stack = [];
  for (let d of num) {
    while (k > 0 && stack.length && stack[stack.length-1] > d) {
      stack.pop(); k--;
    }
    stack.push(d);
  }
  while (k-- > 0) stack.pop();
  let result = stack.join('').replace(/^0+/, '');
  return result || '0';
}

Monotonic stack greed: Always remove larger digits earlier in the number when a smaller digit appears — this greedy choice minimizes the leading value of the number.

The final while k-- > 0 handles cases where no removals were triggered during processing (e.g., sorted ascending input like "12345").

For each day, find how many days until a warmer temperature. A brute force O(n²) approach checks all future days for each day.

Use a monotonic decreasing stack. Push indices onto the stack. When a temperature is warmer than the top of the stack, the top found its answer: current index minus stack top index.

Pop the top and continue comparing — one index may resolve multiple stacked days in one pass.

This runs in O(n) time and O(n) space for the stack.

function dailyTemperatures(temps) {
  let res = Array(temps.length).fill(0), stack = [];
  for (let i = 0; i < temps.length; i++) {
    while (stack.length && temps[stack[stack.length-1]] < temps[i]) {
      let idx = stack.pop();
      res[idx] = i - idx;
    }
    stack.push(i);
  }
  return res;
}

Monotonic stack for "next greater": Storing indices (not values) on the stack lets you compute the distance directly as currentIndex - poppedIndex.

Temperatures that never find a warmer day remain as 0 in the result — they stay on the stack throughout and are never popped.

Given a push sequence and a pop sequence, determine if the pop sequence could result from some sequence of push and pop operations on a stack.

Simulate the operations: push elements in order from the push sequence, then pop from the top of the simulated stack whenever it matches the next element in the pop sequence.

After processing all pushes, if the stack is empty, the pop sequence is valid. If elements remain, it is not achievable.

This runs in O(n) time and O(n) space for the simulation stack.

function validateStackSequences(pushed, popped) {
  let stack = [], j = 0;
  for (let val of pushed) {
    stack.push(val);
    while (stack.length && stack[stack.length-1] === popped[j]) {
      stack.pop(); j++;
    }
  }
  return stack.length === 0;
}

Greedy simulation: Pop eagerly whenever the stack top matches the next pop target — any delay in popping would only block future operations.

A non-empty stack at the end means some pushed elements never matched their expected pop position, proving the sequence is invalid.

Browser history requires navigating to new pages, going back, and going forward. This maps naturally to two stacks: one for back history and one for forward history.

When visiting a new page: push the current page to the back stack, clear the forward stack, and update the current page. Pressing back: push current to forward, pop from back. Pressing forward: push current to back, pop from forward.

Clearing forward history on new navigation matches real browser behavior — you cannot go "forward" to pages you have not visited in the current path.

All operations (visit, back, forward) are O(1) amortized with stacks.

class BrowserHistory {
  constructor(homepage) { this.back = []; this.forward = []; this.curr = homepage; }
  visit(url) { this.back.push(this.curr); this.curr = url; this.forward = []; }
  goBack() {
    if (!this.back.length) return this.curr;
    this.forward.push(this.curr); this.curr = this.back.pop(); return this.curr;
  }
  goForward() {
    if (!this.forward.length) return this.curr;
    this.back.push(this.curr); this.curr = this.forward.pop(); return this.curr;
  }
}

Two-stack model: Back stack holds history; forward stack holds future pages. Visiting clears future — this is standard browser UX behavior.

An alternative doubly linked list approach also works but stacks are simpler and avoid pointer management for this use case.

A basic calculator must handle addition, subtraction, and nested parentheses. Operator precedence is not needed here since only + and - are involved.

Use a stack to save (current result, current sign) when entering parentheses. Restore them when closing. Iterate character by character, updating the running result.

Each digit may extend a multi-digit number (multiply current number by 10). Apply sign and reset the number buffer when a +/- or ) is encountered.

This runs in O(n) time and O(n) space for the stack depth proportional to nesting depth.

function calculate(s) {
  let stack = [], res = 0, num = 0, sign = 1;
  for (let c of s) {
    if (c >= '0' && c <= '9') {
      num = num * 10 + Number(c);
    } else if (c === '+') { res += sign * num; num = 0; sign = 1; }
    else if (c === '-') { res += sign * num; num = 0; sign = -1; }
    else if (c === '(') { stack.push(res, sign); res = 0; sign = 1; }
    else if (c === ')') {
      res += sign * num; num = 0;
      res *= stack.pop(); // sign before (
      res += stack.pop(); // result before (
    }
  }
  return res + sign * num;
}

Stack for parentheses context: Push the accumulated result and sign before entering (; on ), finalize the inner expression and add it to the outer context.

Multi-digit numbers require num = num * 10 + digit; flush num to res at every operator and at the final return.

Adjacent duplicate removal is a classic stack problem: repeatedly remove pairs of identical adjacent characters until no more remain.

Iterate through the string. If the top of the stack equals the current character, pop it (they cancel out). Otherwise, push the current character.

The stack naturally handles cascading removals: removing a pair may expose a new pair at the top of the stack which is immediately resolved in the next iteration.

This runs in O(n) time and O(n) space for the stack (worst case no duplicates).

function removeDuplicates(s) {
  let stack = [];
  for (let c of s) {
    if (stack.length && stack[stack.length-1] === c) stack.pop();
    else stack.push(c);
  }
  return stack.join('');
}

Stack cancellation: The stack acts as the "processed" output; each character either extends the output or cancels with its predecessor — one pass is sufficient.

For the variant "remove k adjacent duplicates", track both character and count on the stack and pop when count reaches k.

As numbers arrive one at a time, you need to find the median at any point. A sorted array would require O(n) insertion; the optimal approach uses two heaps.

Maintain a max-heap for the lower half and a min-heap for the upper half. After each insertion, balance so heaps differ in size by at most 1. The median is either the top of the larger heap or the average of both tops.

JavaScript does not have a built-in heap, so simulate with a sorted array for small inputs or implement a heap class. Conceptually the approach is O(log n) per insert.

This is the optimal solution: O(log n) insert and O(1) median query.

// Concept: two heaps maintain lower and upper halves
// maxHeap (lower half): always <= minHeap (upper half)
// Balance: |maxHeap.size - minHeap.size| <= 1
// Median: maxHeap.top if odd total, else (maxHeap.top + minHeap.top) / 2

// After each insert:
// 1. Push to maxHeap, then move maxHeap.top to minHeap
// 2. If minHeap.size > maxHeap.size, move minHeap.top to maxHeap

Two-heap invariant: The max-heap's top is always the largest element of the smaller half — maintaining this invariant gives O(1) median access at all times.

This pattern extends to "sliding window median" where expired elements must be lazily removed from heaps using a deletion map.

In prefix (Polish) notation, operators come before their operands (e.g., + 3 4 = 7). Unlike postfix, you process from right to left using a stack.

Traverse the expression right to left. If the token is a number, push it. If it is an operator, pop two operands, apply the operator, and push the result.

The key difference from postfix: in postfix you process left to right and pop for operators; in prefix you process right to left and get the same stack behavior.

Both run in O(n) time and O(n) space.

function evalPrefix(tokens) {
  let stack = [];
  for (let i = tokens.length - 1; i >= 0; i--) {
    let t = tokens[i];
    if ('+-*/'.includes(t)) {
      let a = stack.pop(), b = stack.pop();
      if (t === '+') stack.push(a + b);
      else if (t === '-') stack.push(a - b);
      else if (t === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));
    } else stack.push(Number(t));
  }
  return stack[0];
}

Right-to-left for prefix: Processing from the end ensures operands are on the stack when the operator is encountered, mirroring the left-to-right behavior for postfix.

For interactive evaluation (streaming input), a recursive descent parser is more natural than a stack-based right-to-left scan.

A deque allows insertions and deletions from both the front and back in O(1) time, combining the functionality of a stack and a queue.

Implement with a fixed-size array using front and rear pointers. Wrap indices with modulo arithmetic to reuse space when pointers reach the array ends.

Track the current size to distinguish between full and empty states (both conditions would otherwise have front === rear).

All operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getLast) are O(1).

class MyCircularDeque {
  constructor(k) { this.buf = Array(k); this.cap = k; this.front = 0; this.rear = 0; this.size = 0; }
  insertFront(v) {
    if (this.size === this.cap) return false;
    this.front = (this.front - 1 + this.cap) % this.cap;
    this.buf[this.front] = v; this.size++; return true;
  }
  insertLast(v) {
    if (this.size === this.cap) return false;
    this.buf[this.rear] = v; this.rear = (this.rear + 1) % this.cap; this.size++; return true;
  }
  deleteFront() {
    if (!this.size) return false;
    this.front = (this.front + 1) % this.cap; this.size--; return true;
  }
  deleteLast() {
    if (!this.size) return false;
    this.rear = (this.rear - 1 + this.cap) % this.cap; this.size--; return true;
  }
  getFront() { return this.size ? this.buf[this.front] : -1; }
  getRear() { return this.size ? this.buf[(this.rear - 1 + this.cap) % this.cap] : -1; }
  isEmpty() { return this.size === 0; }
  isFull() { return this.size === this.cap; }
}

Separate size counter: Tracking size explicitly avoids the ambiguity between empty and full states that arises when using only front/rear pointers on a circular buffer.

Deques are used in sliding window maximum problems, palindrome checking algorithms, and task scheduling systems.

A Unix file path may contain . (current directory), .. (parent directory), and multiple slashes that need to be simplified.

Split the path by /, then process each component: ignore empty strings and single dots, pop the stack for .. (if non-empty), and push valid directory names.

The resulting stack, joined with / and prefixed with /, gives the canonical simplified path.

This runs in O(n) time and O(n) space.

function simplifyPath(path) {
  let parts = path.split('/'), stack = [];
  for (let p of parts) {
    if (!p || p === '.') continue;
    if (p === '..') stack.pop();
    else stack.push(p);
  }
  return '/' + stack.join('/');
}

Stack as directory hierarchy: Each valid directory name goes onto the stack; .. pops the most recent directory — this mirrors filesystem navigation exactly.

Handle root edge case: popping an empty stack for .. at the root level is a no-op since you cannot go above the root directory.

A string of brackets is valid if every open bracket has a matching close bracket in the correct order. The goal is to find the minimum additions needed to balance the string.

Track two counters: open (unmatched open brackets) and close (unmatched close brackets). For each ( increment open; for each ) either match an open (decrement) or increment close.

At the end, the answer is open + close — each represents a bracket that must be added on the opposite side.

This runs in O(n) time and O(1) space with just two counters.

function minAddToMakeValid(s) {
  let open = 0, close = 0;
  for (let c of s) {
    if (c === '(') open++;
    else if (open > 0) open--;
    else close++;
  }
  return open + close;
}

Two-counter approach: close counts ) with no matching ( to the left; open counts ( with no matching ) to the right.

The same problem can be solved with a single stack, but two counters are both simpler and more space-efficient.

A standard stack has O(1) push and pop but O(n) minimum lookup. The min-stack augments each operation to maintain the current minimum in O(1).

Maintain a parallel minStack. On every push, compute Math.min(val, current min) and push that to minStack. On every pop, also pop minStack.

This means the top of minStack always holds the minimum of all elements currently in the main stack.

Both stacks stay in sync — they grow and shrink together, guaranteeing O(1) for all four operations.

class MinStack {
  constructor() { this.stack = []; this.minStack = []; }
  push(val) {
    this.stack.push(val);
    let minVal = this.minStack.length ? Math.min(val, this.minStack[this.minStack.length-1]) : val;
    this.minStack.push(minVal);
  }
  pop() { this.stack.pop(); this.minStack.pop(); }
  top() { return this.stack[this.stack.length-1]; }
  getMin() { return this.minStack[this.minStack.length-1]; }
}

Parallel tracking: Rather than searching the stack for the minimum on each call, pre-compute and store the running minimum at each level of the stack.

An optimization stores only when the new minimum changes (using <= comparisons) — reduces minStack size but complicates pop logic slightly.