Data Structures & Algorithms•22 min read•Intermediate

Stacks, Queues & Monotonic Stacks

LIFO, FIFO, and a clever variant that solves the "next greater element" family of problems.

Stacks (LIFO)

A stack is a Last-In, First-Out collection. The two operations are push (add to top) and pop (remove from top). Both are O(1). Real-world examples: the call stack of a running program, browser back history, undo buffers.

🍽️

Real-life analogy — A stack of plates in the cafeteria

Workers add washed plates to the TOP. Customers grab from the TOP. The plate at the bottom from this morning may not be touched until tomorrow. Last in, first out.

Stack (LIFO)

Like a stack of plates — you only add to or take from the top.

empty

Empty stack

In Python, just use a list and treat `append` and `pop` as push/pop. In JS, same with `push` and `pop` on an Array.

Classic problem: balanced parentheses

python

Try in Playground →

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            # close: top of stack must match
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(is_balanced("()[]{}"))   # True
print(is_balanced("([)]"))     # False

Stacks naturally model nesting. If your problem involves matching pairs, undoing the most recent action, or tracking depth — try a stack first.

Queues (FIFO)

A queue is First-In, First-Out: enqueue at the back, dequeue from the front. Both should be O(1). In Python, DON'T use a list as a queue — `pop(0)` is O(n). Use `collections.deque` instead.

☕

Real-life analogy — The line at a coffee shop

First person in line is the first one served. New customers join at the back. Nobody (politely) cuts to the front. That's it — that's a queue.

Queue (FIFO)

Like a line at a coffee shop — first person in is the first served.

front →

empty

← back

Empty queue

python

Try in Playground →

from collections import deque

q = deque()
q.append("a")        # enqueue
q.append("b")
q.append("c")
print(q.popleft())    # \"a\" — dequeue, O(1)

Queues are the natural data structure for breadth-first search (BFS), level-order tree traversal, and producer/consumer pipelines.

Monotonic stack

A monotonic stack is a stack whose elements are kept in sorted order (e.g. always increasing). Whenever you push something that would break the invariant, you pop the offenders first. This solves an entire family of problems where you need the "next greater" or "previous smaller" element for every position.

javascript

Try in Playground →

// For each element, find the index of the next greater element to the right.
// Returns -1 if none.
function nextGreater(nums) {
  const result = new Array(nums.length).fill(-1);
  const stack = [];   // holds INDICES, with values that are decreasing

  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const j = stack.pop();
      result[j] = i;
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreater([2, 1, 5, 3, 6, 4]));
// [2, 2, 4, 4, -1, -1]

Each element is pushed and popped at most once, so the entire algorithm is O(n) — a huge win over the naive O(n²) for-each-pair approach.

← Previous

Linked Lists

Trees & Binary Search Trees