Stacks & Queues — Complete Guide with Interactive Walkthroughs

A stack is an ordered collection where you only add and remove from the same end — LIFO (last in, first out). Think of a stack of plates, or browser history: visit A → B → C, then back removes C first.

A queue adds and removes from opposite ends — FIFO (first in, first out). Think of a line at a restaurant, or jobs on a first-come printer.

Both are abstract interfaces, not a single implementation. Arrays make great stacks; efficient queues usually need a deque or doubly linked list.

This guide continues the series after [Linked Lists](/blog/linked-list-technique) and pairs with [Sliding Window](/blog/sliding-window-technique) and [Hashing](/blog/hashing-technique).

---

Core Patterns

---

Stacks — LIFO

Push inserts, pop removes, peek looks at the top without removing. With a dynamic array: push / pop are O(1) amortized; search is O(n).

Stacks and recursion are close cousins — call frames are pushed and popped on a call stack.

When to reach for a stack: the problem has a LIFO shape — matching openers with the most recent unclosed item, undoing the latest action, or processing “most recent unresolved” indices first.

Language sketch

---

String Problems with Stacks

Iterate the string, push characters (or openers), and compare the top with the current character. The stack stores history.

Example 1 — Valid Parentheses

[LeetCode 20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/)

Open brackets must close in the reverse order they opened. That is pure LIFO.

Map each opener to its closer. On '(', '{', '[' — push. On a closer — pop and check the match. Stack must be empty at the end.

function isValid(s) {
  const pairs = { ")": "(", "}": "{", "]": "[" };
  const stack = [];

  for (const ch of s) {
    if (ch === "(" || ch === "{" || ch === "[") {
      stack.push(ch);
    } else {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }

  return stack.length === 0;
}

Complexity: O(n) time and space.

Example 2 — Remove Adjacent Duplicates

[LeetCode 1047](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/)

Keep deleting pairs of equal neighbors until none remain. Deletions unlock later pairs — order is LIFO ("abccba" deletes c → b → a).

Push each char; if it equals the top, pop instead.

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

Example 3 — Backspace String Compare

[LeetCode 844](https://leetcode.com/problems/backspace-string-compare/)

'#' deletes the most recently typed character — again LIFO. Simulate both strings with stacks (guard empty pops), then compare.

function build(s) {
  const stack = [];
  for (const ch of s) {
    if (ch === "#") stack.pop();
    else stack.push(ch);
  }
  return stack.join("");
}

function backspaceCompare(s, t) {
  return build(s) === build(t);
}

---

Queues — FIFO

Enqueue at one end, dequeue at the other. A plain array that shifts from the front is O(n) — use a deque (or doubly linked list with head/tail) for O(1) ends.

A deque (double-ended queue) supports add/remove on both ends. Queues alone are rarer in interviews than stacks; their star role is BFS (coming in trees & graphs). Still useful for streams with expiry.

Example — Number of Recent Calls

[LeetCode 933](https://leetcode.com/problems/number-of-recent-calls/)

ping(t) records a call and returns how many calls fall in [t - 3000, t]. Times only increase — drop outdated values from the front of a queue.

class RecentCounter {
  constructor() {
    this.q = [];
  }

  ping(t) {
    this.q.push(t);
    while (this.q[0] < t - 3000) this.q.shift();
    return this.q.length;
  }
}

With an efficient front removal, each call is amortized O(1).

---

Monotonic Stacks & Queues

Monotonic means the structure stays sorted (non-increasing or non-decreasing). Before pushing x, pop anything that would break the order.

stack = []
for num in nums:
    while stack not empty AND stack.top violates order with num:
        stack.pop()
    // problem-specific logic here
    stack.push(num)

Despite the nested loop, time is still O(n) — each element is pushed and popped at most once.

Use them for next greater/smaller problems, or to track max/min in a moving window.

Example 1 — Daily Temperatures

[LeetCode 739](https://leetcode.com/problems/daily-temperatures/)

For each day, how many days until a warmer temperature? Brute force is O(n²). Keep a monotonically decreasing stack of indices. When you see a warmer day, pop colder days and fill answer[j] = i - j.

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = Array(n).fill(0);
  const stack = []; // indices, decreasing temps

  for (let i = 0; i < n; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const j = stack.pop();
      answer[j] = i - j;
    }
    stack.push(i);
  }

  return answer;
}

Strictly speaking this stack is monotonically non-increasing (equals allowed). Use >= / <= if you must forbid ties.

Example 2 — Sliding Window Maximum

[LeetCode 239](https://leetcode.com/problems/sliding-window-maximum/)

Window of size k slides across nums; return the max in each window. When the max leaves, you need the next-best — a monotonic decreasing deque of indices:

• Pop from the right while the new value is larger (smaller values can never be max again)
• Pop from the left when the index falls outside the window
• Front of the deque is always the current max

function maxSlidingWindow(nums, k) {
  const deque = []; // indices, decreasing values
  const out = [];

  for (let i = 0; i < nums.length; i++) {
    while (deque.length && deque[0] <= i - k) deque.shift();
    while (deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }
    deque.push(i);
    if (i >= k - 1) out.push(nums[deque[0]]);
  }

  return out;
}

Complexity: O(n) time, O(k) space.

Example 3 — Longest Subarray with Abs Diff ≤ Limit

[LeetCode 1438](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/)

Longest subarray where max − min ≤ limit. Classic [sliding window](/blog/sliding-window-technique) plus two monotonic deques — one increasing (min at front), one decreasing (max at front). Shrink left while max − min > limit.

Window length = right − left + 1. Overall O(n).

---

Complexity Cheat Sheet

---

Common Mistakes

Using array shift as a queue in hot loops without a real deque — becomes O(n²) accidentally.

Forgetting empty-stack pops on backspace or mismatched closers.

Storing values instead of indices when you need distance or window bounds (temperatures, window max).

Thinking nested while is O(n²) — if each element enters/leaves once, it is still O(n).

Strict vs non-strict monotonic — know whether equal elements are allowed (> vs >=).

Skipping the LIFO recognition step — if “most recent unmatched X” matters, try a stack first.

---

Practice Problems (Easiest → Hardest)

---

Quick Reference — Pattern Picker

---

Key Takeaways

1. Stack = LIFO (same end). Queue = FIFO (opposite ends). Deque does both.
2. Spot LIFO in matching, undo, and “most recent unresolved” problems.
3. String stacks: push openers / chars; pop on match, duplicate, or backspace.
4. Efficient queues need O(1) front removal — use a deque, not shift in a tight loop.
5. Monotonic stack → next greater / daily temperatures.
6. Monotonic deque → sliding window max (and min+max constraints).
7. Nested pop loops stay O(n) when each element is processed once.
8. Queues shine even more in BFS — next up in trees & graphs.

Pair this with [Sliding Window](/blog/sliding-window-technique) for window problems, [Hashing](/blog/hashing-technique) for bracket maps, and [Linked Lists](/blog/linked-list-technique) for deque implementations under the hood.