Queues

A queue is first in, first out: add at one end, remove from the other. Simple to describe, and the obvious implementation is wrong in a way that is worth seeing.

The obvious version, and why it is O(n)

Put the elements in an array, add at the end, remove from index 0 — and shift everything down one to close the gap. That dequeue is O(n), and draining a queue of n elements becomes O(n²). It is the standard way a hand-rolled queue goes wrong.

The circular buffer

Nothing has to move. Keep the array still and let two indices chase each other around it, wrapping with a modulo.

    private Object[] items;
    private int head;  // index of the next element to come out
    private int size;

    /** O(1) amortised. */
    public void enqueue(E item) {
        if (size == items.length) {
            grow();
        }
        items[(head + size) % items.length] = item;
        size++;
    }

    /** O(1) - nothing shifts, the head simply moves on. */
    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (size == 0) {
            throw new NoSuchElementException("queue is empty");
        }
        E item = (E) items[head];
        items[head] = null;
        head = (head + 1) % items.length;
        size--;
        return item;
    }

Storing head and size rather than head and tail is deliberate. With two indices, a full queue and an empty queue both have head == tail and you need a spare slot or a flag to tell them apart. Keeping size removes the ambiguity entirely.

⚠️ The growth bug

This is the one worth the whole post. When the buffer is full and the contents have wrapped, the logical order and the physical order are different:

physical:  [ 4 ][ 5 ][ 2 ][ 3 ]
                       ^head
logical:     2, 3, 4, 5

Arrays.copyOf preserves the physical layout, so the queue comes back reordered. The fix is to copy element by element in logical order and reset the head:

    private void grow() {
        Object[] bigger = new Object[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[(head + i) % items.length];
        }
        items = bigger;
        head = 0;
    }

What makes this bug nasty is that it cannot happen until the buffer has wrapped and then filled. Every small test passes. So the test does it deliberately:

        // Now head is 1 and the next enqueue wraps to index 0.
        q.enqueue(4);
        Check.eq(q.toString(), "[2, 3, 4]", "enqueue wraps around");
        Check.eq(q.size(), 3, "size after wrap");

        // Force a grow while the contents are wrapped - the case the naive copy breaks.
        q.enqueue(5);
        Check.eq(q.toString(), "[2, 3, 4, 5]", "grow unrolls the wrap in order");

This is the concrete version of the advice from the first post: test the ugly states, not the happy path.

Queue against stack

That last row is the one to hold on to. BFS and DFS are the same algorithm; the only difference is which of these two you put the frontier in.

In Java

Queue<String> queue = new ArrayDeque<>();
queue.add("first");
queue.add("second");
queue.remove();   // "first"

ArrayDeque is a circular buffer exactly like the one above, and is the right default. Two notes: it rejects null (because poll() returns null to mean "empty", so a null element would be ambiguous), and it is not thread-safe — for a producer and consumer on different threads you want ArrayBlockingQueue or ConcurrentLinkedQueue.

Each operation comes in two flavours, and the difference is what happens when the queue is empty or full:

A Deque is a double-ended queue — add and remove at both ends — which is why one class serves as both a queue and a stack.

What to remember

• FIFO, and both ends are O(1) — if you use a circular buffer.
• Shifting on dequeue is the O(n) mistake.
• Growing a wrapped buffer must unroll it in logical order.
• Track head and size, not head and tail.
• ArrayDeque for both queues and stacks; no null elements.