Stack and queue

A stack gives back the most recently added item first: last in, first out, like a pile of plates. A queue gives back the oldest item first: first in, first out, like a line at a counter. Both add and remove in constant time (the cost does not grow with the number of items). Interviewers ask about them because many problems turn simple once you pick the right one, and because they connect to things testers already know: undo history, browser back buttons, message queues and job runners.

Which structure to use in each language

In Java, use ArrayDeque for both. As a stack: push, pop, peek. As a queue: offer, poll, peek. The old Stack class still works, but its own documentation recommends the Deque interface instead.

In Python, a plain list is a good stack: append and pop() work at the end in constant time. Do not use a list as a queue: pop(0) shifts every other element, so it costs O(n). Use collections.deque with append and popleft.

Step by step: balanced brackets

The classic stack problem: are the brackets in a string balanced? Every bracket must be closed by the same kind, in the reverse order of opening. A stack fits exactly, because the bracket you must close next is always the most recent one still open. Push every opening bracket. On a closing bracket, the stack must not be empty and its top must be the matching opening bracket; pop it. At the end the stack must be empty.

For "([)]" the walk pushes ( and [, then meets ) while [ is on top, so the answer is false at once. Counting each kind of bracket separately would wrongly accept it.

Signs that a stack is the answer

• Matching pairs, where the most recent open item must close first: brackets, tags, undo.
• "Next greater" or "previous smaller" questions. Keep a stack whose values stay in order (a monotonic stack). When a new value arrives, pop everything it beats; those values can never be an answer again.
• Turning recursion into a loop: the call stack is a stack, so a deep walk can use your own.

Signs that a queue is the answer

• Level by level or step by step: breadth-first search (visit everything one step away, then everything two steps away, and so on) on trees and grids, the fewest moves to reach something, or something spreading one cell per minute, such as rot in a grid of fruit.
• Processing in arrival order: tasks, messages, requests.

A double-ended queue adds and removes at both ends. The sliding window maximum uses one: positions enter at the back, expired positions leave at the front, and weaker values are removed from the back.

The monotonic stack in code

The program below shows both structures, then finds the next greater value for every element. It walks from right to left and keeps a stack of candidate answers. For 4, 5, 2, 25: 25 has no answer; 2 gets 25; 5 pops the 2 and gets 25; 4 gets 5. Each value is pushed once and popped at most once, so the whole walk is O(n), even with a loop inside a loop.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    // For each value, the first larger value to its right, or -1.
    static int[] nextGreater(int[] nums) {
        int[] result = new int[nums.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                stack.pop();                    // can never be an answer again
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        System.out.println(queue.poll());       // first in, first out

        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");
        stack.push("second");
        System.out.println(stack.pop());        // last in, first out

        System.out.println(Arrays.toString(nextGreater(new int[] { 4, 5, 2, 25 })));
    }
}

first
second
[5, 25, 25, -1]

from collections import deque


def next_greater(nums):
    """For each value, the first larger value to its right, or -1."""
    result = [-1] * len(nums)
    stack = []
    for i in range(len(nums) - 1, -1, -1):
        while stack and stack[-1] <= nums[i]:
            stack.pop()                  # can never be an answer again
        if stack:
            result[i] = stack[-1]
        stack.append(nums[i])
    return result


queue = deque()
queue.append("first")
queue.append("second")
print(queue.popleft())                   # first in, first out

stack = []
stack.append("first")
stack.append("second")
print(stack.pop())                       # last in, first out

print(next_greater([4, 5, 2, 25]))

first
second
[5, 25, 25, -1]

Design questions

Two design classics come up often. A queue built from two stacks: push onto an inbox stack; when you need the front and the outbox stack is empty, move everything from the inbox to the outbox, which reverses the order. Each item moves once, so each operation is constant time on average (this is called amortised: the cost averaged over many operations). A stack that reports its minimum: next to every value, store the minimum at the time it was pushed, so popping brings the previous minimum back for free.

How to answer in an interview

Say which structure you chose and the property that decided it: "the bracket I must close is always the latest one opened, so a stack". Trace a short input, including one that fails, and say what happens on an empty stack. Give the cost: each item is pushed and popped once, so O(n) time and up to O(n) space.

Common mistakes

• Popping or peeking an empty stack. Check first, and decide what the answer is in that case.
• Forgetting the final check: brackets are balanced only if the stack is empty at the end.
• Using a Python list as a queue with pop(0), which is O(n) per call.
• Storing values when you need positions, for example to know when an item has left a window.

Recap

Use a stack when the latest item must be handled first, and a queue when the oldest must. A monotonic stack answers "next greater" questions in one pass, and two stacks can make a queue with amortised constant-time operations.