Stacks and Queues

Updated Nov 16, 2026 · 4 min read
On this page

    Some problems are about order: the most recent thing you opened must be the first one you close, or the first thing you discovered must be the first one you process. Trying to track that with indexes into an array gets messy fast. Stacks and queues are arrays (or lists) with a rule about which end you use, and that rule is often the whole solution.

    How it works

    A stack adds and removes at the same end (last in, first out); a queue adds at the back and removes from the front (first in, first out).
    A stack adds and removes at the same end (last in, first out); a queue adds at the back and removes from the front (first in, first out).

    Stack: last in, first out

    A stack only touches one end, the top. push puts an item on top, pop removes the top item, peek looks at it without removing it. The item you take out is always the one you put in most recently.

    Every language gives you one for free: a Python list (append and pop), Java ArrayDeque (push, pop, peek), C++ std::stack or vector, and a Go slice (append, then s = s[:len(s)-1]).

    Queue: first in, first out

    A queue adds at the back and removes from the front, like a line at a shop. In Python use collections.deque (append, popleft); in Java ArrayDeque (offer, poll); in C++ std::queue; in Go a slice with a moving head index, or container/list.

    A deque (double-ended queue) allows both ends, and can act as either.

    Why they appear in so many problems

    • A stack remembers what is still open: brackets, function calls, unfinished tags, numbers waiting for an operator. When you meet a closer, the matching opener is always on top.
    • A queue remembers what is waiting, in discovery order. That is exactly what breadth-first search needs.
    Each opening bracket is pushed; each closing bracket must match the top, which is popped. An empty stack at the end means the string is valid.
    Each opening bracket is pushed; each closing bracket must match the top, which is popped. An empty stack at the end means the string is valid.

    Operations and costs

    OperationStackQueue (deque)
    Addpush: O(1)enqueue at back: O(1)
    Removepop top: O(1)dequeue front: O(1)
    Look at next itempeek: O(1)front: O(1)
    Search for a valueO(n)O(n)

    The one trap: a plain Python list used as a queue with pop(0) is O(n), because every element shifts. Always use deque.

    When to reach for it

    Use a stack when:

    • Things must be closed in the reverse order they were opened: bracket matching, HTML tags, undo history.
    • You need to evaluate expressions: postfix notation, or a calculator with + - * /.
    • You need the next greater or smaller element: a monotonic stack keeps elements in sorted order and pops everything the new element beats. Each element is pushed and popped once, so it's O(n) overall.
    • You want to turn recursion into a loop (iterative DFS).

    Use a queue when:

    • You explore level by level: breadth-first search on a tree, a grid or a graph, and shortest paths when every step costs the same.
    • You process tasks in arrival order, or keep a sliding window of recent items.
    After visiting the first level, the queue holds the next level in the order it was discovered, so BFS naturally moves level by level.
    After visiting the first level, the queue holds the next level in the order it was discovered, so BFS naturally moves level by level.

    Example

    Check whether a string of brackets is valid: every opener is closed by the same type, in the right order.

    def is_valid(s):
        pairs = {')': '(', ']': '[', '}': '{'}
        stack = []
        for c in s:
            if c in pairs:                      # a closer
                if not stack or stack[-1] != pairs[c]:
                    return False
                stack.pop()
            else:                               # an opener
                stack.append(c)
        return not stack                        # nothing left open
    boolean isValid(String s) {
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || !stack.peek().equals(pairs.get(c))) return false;
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
    bool isValid(const string& s) {
        unordered_map<char, char> pairs = {{')', '('}, {']', '['}, {'}', '{'}};
        stack<char> st;
        for (char c : s) {
            if (pairs.count(c)) {
                if (st.empty() || st.top() != pairs[c]) return false;
                st.pop();
            } else {
                st.push(c);
            }
        }
        return st.empty();
    }
    func isValid(s string) bool {
        pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
        stack := []rune{}
        for _, c := range s {
            if open, ok := pairs[c]; ok {
                if len(stack) == 0 || stack[len(stack)-1] != open {
                    return false
                }
                stack = stack[:len(stack)-1]
            } else {
                stack = append(stack, c)
            }
        }
        return len(stack) == 0
    }

    Time: O(n). Space: O(n) in the worst case (all openers).

    Three tests cover the logic: "([]{})" is valid, "([)]" fails at the mismatch, and "((" fails at the end because the stack isn't empty.

    Common mistakes

    • Popping an empty stack. Check for empty before pop or peek; a lone ")" should return false, not crash.
    • Forgetting the final check. A string of only openers passes the loop; the answer depends on the stack being empty at the end.
    • Using a list as a queue. list.pop(0) in Python is O(n). Use deque.popleft().
    • Java's Stack class. It works but is old and synchronized; ArrayDeque is the usual choice. Compare boxed Character values with equals if you store them in collections and compare two objects.
    • Pushing values when you need positions. For problems like Daily Temperatures you need the index on the stack, not the value, to compute distances.

    Say this in the interview

    • "The most recently opened bracket has to close first, which is last in, first out, so I'll use a stack."
    • "Each element is pushed and popped at most once, so even with the inner while loop the total is O(n)."
    • "I'll use a deque for the BFS queue so dequeuing is O(1)."

    Used in