Stacks and Queues for Coding Interviews

Interviewers expect you to know that a stack is last in, first out and a queue is first in, first out, that both add and remove at their ends in O(1), and which type your language wants you to use. Choose a stack for nesting, undo and depth-first work, and a queue for arrival order and breadth-first search.

Operations and what they cost

Structure	Add	Remove	Peek	Search	Space
Stack	O(1), push	O(1), pop	O(1), top	O(n)	O(n)
Queue	O(1), enqueue	O(1), dequeue	O(1), front	O(n)	O(n)
Deque	O(1), either end	O(1), either end	O(1), either end	O(n)	O(n)
Queue from two stacks	O(1)	O(1) amortized	O(1) amortized	O(n)	O(n)
Ring buffer, fixed capacity	O(1)	O(1)	O(1)	O(n)	O(capacity)

Those are the costs of the structures. The trap is the type you implement them with, which is the next section.

Which type to use in each language

Language	Stack	Queue	What the documentation says
Python	`list`	`collections.deque`	Appending is O(1) amortized and popping at the end moves nothing, but `pop(0)` is O(n). A deque gives approximately O(1) at either end.
JavaScript	`Array`	`Array` with a head index	No Big O is stated for these. The specification defines `shift` as moving every remaining element, so a head index avoids it.
Java	`ArrayDeque`	`ArrayDeque`	Most operations are amortized constant, and it is likely to be faster than Stack as a stack and LinkedList as a queue.

When to reach for each

Reach for	When the problem has	Guide
A stack	Nesting, matching pairs, undo, or the most recent unfinished thing	Stack patterns
A monotonic stack	The next larger or smaller element for every position	Stack patterns
A queue	Processing in arrival order, or the fewest steps in a graph	Graph patterns
A deque	Adding or removing at both ends, such as a sliding maximum	Sliding window
A priority queue	The next item by importance, not by arrival	Heaps

How it looks in Python, JavaScript and Java

The same two jobs in each language: use a stack to check that brackets balance, then use a queue to list a tree level by level.

from collections import deque

CLOSES = {")": "(", "]": "[", "}": "{"}

def balanced(text):
    stack = []
    for ch in text:
        if ch in CLOSES.values():
            stack.append(ch)
        elif ch in CLOSES:
            if not stack or stack.pop() != CLOSES[ch]:
                return False
    return not stack                     # leftovers were never closed

def by_level(root):
    levels, queue = [], deque([root] if root else [])
    while queue:
        level = []
        for _ in range(len(queue)):      # exactly one level per round
            node = queue.popleft()
            level.append(node.val)
            queue.extend(c for c in (node.left, node.right) if c)
        levels.append(level)
    return levels

JavaScript

const CLOSES = new Map([[")", "("], ["]", "["], ["}", "{"]]);
const OPENS = new Set(CLOSES.values());

function balanced(text) {
  const stack = [];
  for (const ch of text) {
    if (OPENS.has(ch)) stack.push(ch);
    else if (CLOSES.has(ch) && stack.pop() !== CLOSES.get(ch)) return false;
  }
  return stack.length === 0;
}

function byLevel(root) {
  const levels = [];
  let current = root ? [root] : [];       // one array per level, so no shift()
  while (current.length > 0) {
    levels.push(current.map((n) => n.val));
    current = current.flatMap((n) => [n.left, n.right].filter(Boolean));
  }
  return levels;
}

Java

import java.util.*;

class StacksAndQueues {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static boolean balanced(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : text.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    static List<List<Integer>> byLevel(Node root) {
        List<List<Integer>> levels = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                Node node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }
}

Interviewers also like asking for a queue built from two stacks, because it tests whether you can reason about amortized cost:

class QueueFromStacks:
    def __init__(self):
        self.incoming, self.outgoing = [], []

    def enqueue(self, x):
        self.incoming.append(x)

    def dequeue(self):
        if not self.outgoing:
            while self.incoming:         # the order flips exactly once
                self.outgoing.append(self.incoming.pop())
        return self.outgoing.pop()

A single dequeue can move everything, but each element moves between the two stacks only once in its life, so n operations cost O(n) in total: amortized O(1) per operation.

How to explain the choice out loud

What a strong candidate might say

The most recent opening bracket has to close first, so this is a stack: I push each opener, and each closer must match the top. Every character is pushed and popped at most once, so it's O(n) time, and O(n) space if everything opens before anything closes. For the level listing I'd use a queue instead, because breadth-first needs arrival order. I'll use a deque for that, since popping from the front of a plain list would move every element.

Common mistakes

Using list.pop(0) or shift() for a queue inside a loop, and not saying what it costs.
Popping from an empty stack when a closer arrives first.
Declaring success without checking the stack is empty at the end.
Using Java's Stack or LinkedList out of habit when ArrayDeque is what the docs point to.
Confusing a queue with a priority queue: one serves by arrival, the other by importance.

Where to go next

Patterns: stack and monotonic stack, sliding window and graphs.
Worked problems: Validate Nesting in a Rich-Text Comment, Build a Document Outline from Headings and Deduplicate a Stream of Retried Events.
All the figures in one place: the Big O cheat sheet.
Practice saying it: a coding mock interview.