Stacks and queues, LIFO and FIFO

A stack and a queue hold the same thing, a sequence of values, and differ in exactly one rule: which end you are allowed to remove from. That one rule is what makes them useful. By taking away your freedom to reach into the middle, they give you an order you can rely on.

The problem they solve

Plenty of problems come with a built-in order that you did not choose:

• The function that was called last must finish first. Undo must reverse the most recent change. A closing bracket must match the latest unclosed opener. That is "most recent first".
• A print job that arrived first must print first. A request must be served in arrival order. A message is delivered in the order it was sent. That is "oldest first".

An array can do both, but nothing stops a bug from touching the wrong end or the middle. A stack and a queue make the rule part of the type, so the ordering guarantee cannot be broken by accident, and the reader knows the intent from the name alone.

Structure

class Stack {
  #items = [];
  push(x) { this.#items.push(x); }
  pop()   { return this.#items.pop(); }
  peek()  { return this.#items[this.#items.length - 1]; }
  get size() { return this.#items.length; }
}

A stack is the easy one, because an array's end already behaves like one. A queue is where naive code goes wrong, as the last section of this page shows.

Where a stack hides in plain sight

Every function call pushes a frame holding its arguments and local variables. When the function returns, the frame is popped and execution resumes in the caller. That is why:

• Recursion needs a base case. With none, frames pile up until the runtime throws RangeError: Maximum call stack size exceeded, a stack overflow.
• Recursion and an explicit stack are interchangeable. Any recursive depth-first walk can be rewritten as a loop over your own stack, which avoids the depth limit on huge inputs.
• A stack trace is the stack. Read it from top to bottom and you are reading the calls from newest to oldest.

Other stacks you use without naming them: the browser's back button, undo in an editor, and the expression evaluator behind every calculator.

The classic use: matching pairs

Balanced brackets is the canonical stack question, because nesting is exactly last-in, first-out: the most recent opener must be the first one closed.

function isBalanced(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const stack = [];
  for (const ch of s) {
    if (ch === '(' || ch === '[' || ch === '{') stack.push(ch);
    else if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

Three failure modes, all handled above: a closer with nothing to match (pop returns undefined), a closer of the wrong kind, and leftover openers at the end.

The monotonic stack: "next greater element"

Some problems ask, for every item, "where is the next item that is bigger?" The brute force scans forward from each item: O(n²). A monotonic stack answers all of them in one pass by keeping only the items still waiting for an answer, ordered so the stack stays sorted.

Daily temperatures is the standard example: for each day, how many days until a warmer one?

function dailyTemperatures(temps) {
  const answer = new Array(temps.length).fill(0);
  const waiting = []; // indices still waiting for a warmer day
  for (let i = 0; i < temps.length; i++) {
    while (waiting.length && temps[i] > temps[waiting[waiting.length - 1]]) {
      const j = waiting.pop();
      answer[j] = i - j;       // today is the warmer day day j was waiting for
    }
    waiting.push(i);
  }
  return answer;
}

Trace [73, 74, 75, 71]:

It looks like O(n²) because of the while inside the for, but every index is pushed exactly once and popped at most once, so the total work is O(n). The same pattern solves next greater element, stock span, largest rectangle in a histogram and trapping rain water.

Building a queue out of two stacks

A classic constraint: you only have stacks, and you need FIFO behaviour.

The trick is that reversing a stack twice restores the original order. Pushing onto the inbox keeps arrivals in order. Moving them all onto the outbox flips them, so the oldest item ends up on top.

class Queue {
  #inbox = [];
  #outbox = [];

  enqueue(x) { this.#inbox.push(x); }

  dequeue() {
    if (this.#outbox.length === 0) {
      while (this.#inbox.length) this.#outbox.push(this.#inbox.pop());
    }
    return this.#outbox.pop();
  }
}

A single dequeue can cost O(n) when it triggers a transfer, but each element is moved at most once in its lifetime, so the amortised cost is O(1). Only transferring when the outbox is empty is what preserves order: transfer while it still holds items and newer elements would jump the line.

The queue's biggest job: breadth-first search

Whenever you need to process things in the order they were discovered, you want a queue. Breadth-first search visits a node, enqueues its neighbours, and dequeues the next one, so everything at distance 1 is handled before anything at distance 2. That is why BFS finds shortest paths in unweighted graphs, and why it is the tool for level-order tree traversal. The graphs page uses it heavily.

The array method trap

Array.prototype.shift() looks like a queue's dequeue, and it is the most common accidental performance bug with queues in JavaScript.

const queue: number[] = [];
queue.push(1);   // enqueue: O(1)
queue.shift();   // dequeue: O(n) in the worst case, every remaining element is re-indexed

Modern engines optimise small arrays, so it can look fine in a test and then crawl on a queue of a few hundred thousand items. Better options:

• A head index: keep a moving head integer and read items[head++]. Compact the array occasionally.
• A linked list with head and tail pointers: O(1) at both ends.
• A circular buffer for a fixed capacity.

Python has the same trap: list.pop(0) is O(n). Use collections.deque and popleft(), which is O(1).

Where they are used in real systems

Stacks and queues you already use

• `Array.prototype.push` and `pop` turn an array into a stack.
• The JavaScript event loop has a macrotask queue and a microtask queue. Promise callbacks are microtasks, which is why they run before setTimeout callbacks.
• `history.back()` and `history.forward()` walk a stack of pages.
• Node.js streams buffer chunks in a queue and apply backpressure when it fills.
• Redux DevTools time travel and most editor undo systems are stacks of past states.
• Python `collections.deque` is the standard queue, and queue.Queue is the thread-safe one.

When not to use them

• You need to reach an arbitrary element. A stack and a queue deliberately forbid it. Use an array or a hash map.
• Priority matters more than arrival. "Most urgent first" is a priority queue, which is a heap, not a queue.
• You are using an array as a queue on large inputs. shift in a hot loop is a bug waiting for data. Switch structures.
• You need both ends. That is a deque (double-ended queue), which supports push and pop at both ends and covers the stack and the queue as special cases.

What interviewers ask

• "Stack or queue?" Ask whether the most recent item or the oldest item should be handled next.
• "Check for balanced brackets." A stack, with three failure modes to name out loud.
• "Implement a queue with two stacks." Amortised O(1), and transfer only when the outbox is empty.
• "Implement a stack with two queues." The mirror image, and it makes one operation O(n).
• "Next greater element or daily temperatures." A monotonic stack, and why it is O(n) despite the nested loop.
• "Design a min stack." Push the running minimum alongside each value so getMin is O(1).
• "How does recursion use the stack, and how do you avoid overflow?" Frames, base cases, and converting to an explicit stack.

The mistake to avoid

Using shift() or splice(0, 1) on a large array as a queue, and calling pop() on an empty stack without checking. The first is silent quadratic slowdown, and the second returns undefined into the rest of your program and fails somewhere far from the cause. Check emptiness at the point of removal, and pick a real queue when the data can grow.

Stacks and queues look trivial until you notice how much of computing is one of them: the call stack, the event loop, undo, BFS, every job system. If you can say "this is a stack problem" or "this needs a queue" on sight, a large share of interview questions collapse into a short loop.