Queues & Deques

Offer and poll: the queue interface

A queue has two ends. You add at the back and remove from the front, so elements exit in exactly the order they entered. In Java the Queue interface names these operations offer (add to the back) and poll (remove from the front), with peek to inspect the front without removing it. All three are O(1). Constant time however long the line gets.

Java also has add and remove methods that do the same jobs, but they throw exceptions when things go wrong, while offer and poll return false or null instead. For everyday code, offer and poll are the idiomatic pair. The standard implementation is once again ArrayDeque; you declare the variable as a Queue to signal that you only intend FIFO behavior.

Queue<String> queue = new ArrayDeque<>();
queue.offer("first");
queue.offer("second");
queue.offer("third");

System.out.println(queue.peek()); // first
System.out.println(queue.poll()); // first
System.out.println(queue.poll()); // second

The deque: both ends open

A deque (pronounced deck, short for double-ended queue) allows insertion and removal at both the front and the back, all in O(1). Java's Deque interface spells the operations out literally: offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast.

This is why ArrayDeque keeps appearing in these lessons. It plays every role. Restrict yourself to one end (push and pop, which map to the front) and it is a stack. Add at the back and remove from the front (offer and poll) and it is a queue. Use all four ends and it powers advanced patterns like the monotonic deque behind Sliding Window Maximum. One class, three data structures, which is why ArrayDeque should be your default answer whenever an interview needs a stack, queue, or deque in Java.

Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(1);   // back:  [1]
deque.offerLast(2);   // back:  [1, 2]
deque.offerFirst(0);  // front: [0, 1, 2]

System.out.println(deque.pollFirst()); // 0
System.out.println(deque.pollLast());  // 2

Why BFS needs a queue

Breadth-first search, or BFS, explores a graph or tree outward in rings: first everything one step from the start, then everything two steps away, and so on. This works only if you process discoveries in the order you made them, and that is FIFO, so the queue is not an implementation detail of BFS, it is the algorithm's beating heart.

The pattern: put the starting point in a queue. Loop while the queue is not empty: poll the front item, do whatever work the problem asks, and offer each unvisited neighbor to the back. Because near things enter the queue before far things, they are also polled first, guaranteeing you visit in order of distance. Swap the queue for a stack and the identical loop becomes depth-first search, diving down one path before backing up, a beautiful illustration that the container's ordering rule is the strategy.

void bfs(int start, List<List<Integer>> graph) {
    Queue<Integer> queue = new ArrayDeque<>();
    boolean[] visited = new boolean[graph.size()];
    queue.offer(start);
    visited[start] = true;
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.println(node);
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.offer(next);
            }
        }
    }
}

Where queues show up

Once you know the shape, you see queues everywhere. Operating system schedulers keep ready-to-run tasks in queues so every program gets a fair turn. Message systems like Kafka and RabbitMQ are giant durable queues between services. Printers, keyboard input buffers, and customer support tickets are all FIFO lines. In interview problems, the giveaways are the words level, layer, nearest, or shortest path in an unweighted graph, each signals BFS, and BFS means a queue.

Two relatives are worth knowing by name. A priority queue serves the most urgent item rather than the oldest, and Java's PriorityQueue implements it with a heap. And the deque's two open ends enable sliding-window tricks you will meet later. Before any of that, though, it is time for a different kind of order (not arrival order, but sorted order) which brings us to sorting.

Frequently asked