A print spooler, a thread-pool work list, a request buffer in front of a slow writer — they all need the same contract: the job that arrived first is the job that runs first. If you implement that with list.remove(0), every dequeue slides the rest of the array one slot left. The queue is correct. The bill is not.

A queue is FIFO: enqueue at the tail, dequeue at the head. That is the abstract data type. The layout that delivers it cheaply is a different question — and the reason a naive array queue “rotates.” Terms like ADT vs implementation, amortized cost, and contiguous vs linked live on the Data Structures Roadmap. This post is the FIFO layout: linear queue, circular buffer, and the JDK type you actually import.

The FIFO contract

Three operations, one order. Enqueue puts an item at the back. Dequeue takes the item at the front. Peek looks at the front without removing it. After A, then B, then C go in, the only legal first removal is A.

That contract does not mention arrays. Confusing FIFO with one layout is how people ship remove(0) on an ArrayList and call it done. The order after three enqueues is always the same:

enqueue(A), enqueue(B), enqueue(C)
peek()     -> A
dequeue()  -> A
dequeue()  -> B
peek()     -> C

Empty dequeue is the other half of the contract. A bounded queue also has a full enqueue. How you signal those — exception, null, Optional — is API. The layout still has to know which it is.

Linear queue: why a naive array rotates

Store the items in a plain array (or ArrayList) and dequeue index 0. That is FIFO — and the version that rotates:

class NaiveArrayQueue<E> {
    private final ArrayList<E> items = new ArrayList<>();

    void enqueue(E item) {
        items.add(item);          // amortized O(1)
    }

    E dequeue() {
        return items.remove(0);   // O(n) — everything slides left
    }
}

After dequeue, every remaining element moves one index down. Ten thousand jobs in the buffer, and removing the one at the front copies 9,999 references. The array is contiguous, so the CPU likes the copy — and you still pay linear work on every pop. ArrayList.remove(0) is a queue with a hidden rotate.

The usual “fix” is to stop sliding and keep a head (next read) and tail (next write). Dequeue increments head and leaves the old slot behind:

class HeadTailQueue<E> {
    private final Object[] slots;
    private int head;
    private int tail; // next write; size = tail - head

    HeadTailQueue(int capacity) {
        this.slots = new Object[capacity];
    }

    void enqueue(E item) {
        if (tail == slots.length) {
            throw new IllegalStateException("no room at the end");
        }
        slots[tail++] = item;
    }

    @SuppressWarnings("unchecked")
    E dequeue() {
        if (head == tail) {
            throw new NoSuchElementException();
        }
        E item = (E) slots[head];
        slots[head++] = null; // drop the reference
        return item;
    }
}

Enqueue and dequeue are now O(1). The new problem is wasted prefix. After a few dequeues the picture looks like this:

capacity 6, head=3, tail=6
index:  0  1  2  3  4  5
value:  _  _  _  D  E  F
                 ^head  ^tail (no room)

Three live items. Three empty slots. enqueue still throws, because tail is at the physical end. Production code then rotates: copy D E F down to index 0, reset head and tail, and only then write. That compact is O(n) — the same slide you thought you escaped, now batched whenever the tail hits the wall.

A linear array queue either slides on every dequeue, or slides when the tail runs out of room. Head and tail indices are not enough if they only move right.

Note: Growing the array when tail hits the end does not fix the wasted prefix. You allocate a bigger block and still copy live items — plus the dead slots you already drained. Growth is for capacity. Wrap-around is for reuse.

Circular buffer: wrap-around, full vs empty

A circular buffer (ring) is the same array plus modular arithmetic. When head or tail walks off the last index, it wraps to 0 and reuses drained slots — no rotate, no compact:

class RingBufferQueue<E> {
    private final Object[] slots;
    private int head;
    private int tail;
    private int size;

    RingBufferQueue(int capacity) {
        this.slots = new Object[capacity];
    }

    void enqueue(E item) {
        if (size == slots.length) {
            throw new IllegalStateException("full");
        }
        slots[tail] = item;
        tail = (tail + 1) % slots.length;
        size++;
    }

    @SuppressWarnings("unchecked")
    E dequeue() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
        E item = (E) slots[head];
        slots[head] = null;
        head = (head + 1) % slots.length;
        size--;
        return item;
    }
}

Same six slots after wrapping. Live items occupy a contiguous ring, not a contiguous prefix:

capacity 6, head=4, tail=2, size=4
index:  0  1  2  3  4  5
value:  C  D  _  _  A  B
              ^tail    ^head
FIFO order: A, B, C, D  (indices 4, 5, 0, 1)

(index + 1) % capacity is the wrap. Head and tail chase each other around the ring. Enqueue and dequeue stay O(1) and the empty slots stay usable.

Head equal to tail is ambiguous without extra state. After wrapping, both “empty” and “full” can land on head == tail: empty means you just caught up by draining; full means you just caught up by filling. Three honest ways to tell them apart:

SchemeEmptyFullCost
Countsize == 0size == capacityExtra int; used above
Waste one slothead == tail(tail + 1) % n == headOne unused cell, always
Flaglast op was dequeue (or start)last op was enqueueExtra boolean; easy to get wrong

The wasted-slot rule is the one most array deques use: the ring is never allowed to hold capacity live items, so head == tail always means empty. OpenJDK’s ArrayDeque grows before the last slot would fill, for the same reason.

Note: Null out the slot you dequeue. A ring that keeps stale references pins objects the GC should free — especially in a long-lived buffer that rarely goes empty.

A bounded ring is the right picture for a fixed-size I/O buffer or a telemetry window. An unbounded queue is the same ring plus growth: when full, allocate a larger array, copy in FIFO order (the wrap becomes a linear stretch), then resume. That copy is occasional. It is amortized, not a rotate on every call — see the hub if “amortized” is still fuzzy.

Java Queue and ArrayDeque

The JDK type for this ADT is java.util.Queue. The layout you want in single-threaded (or confined) code is ArrayDeque: a circular array, head and tail indices, wrap-around, growth when the ring is about to fill.

Queue<String> jobs = new ArrayDeque<>();
jobs.offer("render-page");
jobs.offer("send-email");
jobs.offer("purge-temp");

String next = jobs.poll();   // render-page
String peek = jobs.peek();   // send-email

Queue has two vocabularies for the same three operations. The exception forms throw when the buffer cannot do the work. The special-value forms return false or null. Prefer offer / poll / peek unless an empty or full queue is a programming error you want to fail fast:

JobThrowsReturns false / null
Enqueueaddoffer
Dequeueremovepoll
Lookelementpeek

ArrayDeque grows, so add and offer both succeed until memory does not. The distinction matters on bounded queues (ArrayBlockingQueue, a hand-rolled ring with a hard capacity). It also matters that ArrayDeque rejects null: poll and peek already use null to mean empty. Put null in and you cannot tell “no job” from “a job that is null.”

LinkedList implements Queue too. It is a fine queue when you already needed the list. As a default FIFO it pays a node object per item for a job ArrayDeque does with a ring of references. Reach for ArrayDeque unless you have a reason the list API is the point.

Note: PriorityQueue implements Queue and is not FIFO. It is a heap: next-out is the smallest (or highest priority) element, not the oldest. Compiling against Queue does not make the layout FIFO. If the ticket says “oldest first,” do not import PriorityQueue.

Complexity

Read the table as a shopping list. The hot path for a queue is enqueue and dequeue. If those are not cheap, you picked the wrong layout — or you are still rotating.

OperationNaive array (remove(0))Head/tail, no wrapCircular buffer / ArrayDeque
Enqueueamortized O(1)O(1) until tail hits the endamortized O(1)
DequeueO(n) slideO(1), wastes prefixO(1)
PeekO(1)O(1)O(1)
Compact / grow—O(n) when tail hits the endO(n) only on resize
Extra spaceO(1)wasted prefixone slot, or a count

Space is O(n) for the live items in every honest implementation. The circular buffer’s extra is a handful of indices, not a second copy.

When not to use a queue

A queue is the wrong layout when FIFO is not the job.

Need to insert and remove at both ends equally — undo plus redo, a sliding window you extend and shrink, a work-stealing end. That is a deque. ArrayDeque already is a deque; using only Queue methods is a FIFO view of the same ring. If callers need addFirst / removeLast as first-class operations, program to Deque, not Queue.

Need “next-best,” not “oldest” — a scheduler, a leaderboard, Dijkstra’s frontier. That is a heap (PriorityQueue). Forcing priority into a FIFO queue means scanning for the best item, which is the bill a heap exists to avoid.

Need index i, a scan, or a removal from the middle. That is a list. A queue that you search is two structures pretending to be one.

Need uniqueness. That is a set. A queue of tokens you contains-scan on every insert is the login-check example from the hub, wearing a FIFO hat.

Note: Concurrent producers and consumers are a queue, but not this post’s layout. ConcurrentLinkedQueue and the BlockingQueue family exist so you do not put a lock around an ArrayDeque and hope. The ADT is still FIFO. The memory model is not.

Cheat sheet

The contract, the two failed arrays, the ring, and the JDK type in one block:

ADT:          FIFO — enqueue tail, dequeue head, peek head
Naive array:  remove(0) slides O(n) every dequeue
Head/tail:    O(1) ops, then wasted prefix; compact = rotate later
Ring:         (i + 1) % n wrap; reuse drained slots; no slide
Full vs empty: count, or waste one slot so head==tail means empty
JDK:          Queue + ArrayDeque (circular array)
API:          offer / poll / peek  (add / remove / element throw)
Null:         ArrayDeque forbids it — poll uses null for empty
Not FIFO:     PriorityQueue implements Queue and is a heap

Do:

  • Name the contract FIFO before you name the array.
  • Use a ring (or ArrayDeque) so drained slots come back without a rotate.
  • Pick offer / poll unless empty or full should be an exception.
  • Keep a count, or waste one slot, so full and empty are not the same picture.

Don’t:

  • Build a queue on ArrayList.remove(0) and call the slide an implementation detail.
  • Treat head == tail as empty on a ring that can also be full.
  • Use PriorityQueue when the ticket said oldest-first.
  • Default to LinkedList as a queue because it implements the interface.

Wrap-up

FIFO is three operations and a promise about order. A naive array keeps the promise by rotating: either on every dequeue, or in a compact when the tail runs out of unused suffix. A circular buffer keeps head and tail moving around the same block, wrapping with modulo, and tells full from empty with a count or a wasted slot. That ring is the layout behind ArrayDeque.

Import Queue, construct ArrayDeque, and stay on offer / poll / peek unless you want throws. When the job is both ends, program to a deque. When the job is next-best, use a heap. When the job is still “oldest first,” the ring is the whole answer.

The glossary, the JDK map, and the rest of the series index are on the Data Structures Roadmap.

Next optional step in the series Stack and queue in one ring when you need both ends. Deque: Both Ends Without Two Structures