Implementations

The simplest array queue keeps a head index (next to leave) and a tail index (next free slot). Enqueue writes at tail and moves it right; dequeue reads at head and moves it right. Both are O(1).

The flaw: both indices only move right. After the array has been filled and emptied once, head == tail == data.length: the queue is empty, yet offer reports full because there is no room to the right. The slots on the left are wasted. Shifting everything left on each dequeue would fix it but makes dequeue O(n).

1class NaiveArrayQueue {
2    private final int[] data;
3    private int head, tail;                          // live values are data[head .. tail - 1]
4    NaiveArrayQueue(int capacity) { data = new int[capacity]; }
5    boolean offer(int x) {
6        if (tail == data.length) return false;       // "full", even if head > 0 left room behind
7        data[tail++] = x;
8        return true;
9    }
10    Integer poll() {
11        if (head == tail) return null;
12        return data[head++];
13    }
14}

A circular queue treats the array as a ring: when an index reaches the end it wraps to 0 with index = (index + 1) % data.length. Freed slots at the front are reused, so the queue is full only when all data.length slots hold live values.

Run the animation and watch H (head) and T (tail) in the slot captions. The slots keep their old numbers after a dequeue (shown struck out), because only head and size decide what is live. The “Wrap around” preset makes the tail jump back to index 0.

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                    // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                    // wrap around
14        size--; return x;
15    }
16}

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        size--; return x;
15    }
16}

A linked queue stores each value in a node. head points at the front node and tail at the rear node. Enqueue links a new node behind the tail; dequeue moves head forward. Both are O(1), there is no capacity limit and nothing is ever shifted.

Two details cause most bugs: when the first node is added, both head and tail must be set, and when the last node is removed, tail must be reset to null, otherwise it keeps pointing at a node that is no longer in the queue. Both cases appear in the animation.

1class LinkedQueue {
2    private static class Node { int val; Node next; Node(int v) { val = v; } }
3    private Node head, tail; private int size;
4    void enqueue(int x) {
5        Node n = new Node(x);
6        if (tail == null) head = n; else tail.next = n;        // link behind the old tail
7        tail = n; size++;
8    }
9    int dequeue() {
10        if (head == null) throw new NoSuchElementException();
11        int x = head.val; head = head.next;
12        if (head == null) tail = null;                         // the queue became empty
13        size--; return x;
14    }
15}

1class LinkedQueue {
2    private static class Node { int val; Node next; Node(int v) { val = v; } }
3    private Node head, tail; private int size;
4    void enqueue(int x) {
5        Node n = new Node(x);
6        if (tail == null) head = n; else tail.next = n;        // link behind the old tail
7        tail = n; size++;
8    }
9    int dequeue() {
10        if (head == null) throw new NoSuchElementException();
11        int x = head.val; head = head.next;
12        if (head == null) tail = null;                         // the queue became empty
13        size--; return x;
14    }
15}

ArrayDeque is Java's general-purpose queue (and stack). It is a resizable circular array: it wraps its indices exactly like the ring queue above and grows when full, so offer and poll are O(1) amortised. It is not bounded, not thread-safe, and rejects null.

Declare the variable with the interface, Queue<Integer> q = new ArrayDeque<>();, so that only queue operations are visible. Iteration goes from the front to the rear.

1static List<Integer> drain(int[] values) {
2    Queue<Integer> q = new ArrayDeque<>();
3    for (int v : values) q.offer(v);
4    List<Integer> out = new ArrayList<>();
5    while (!q.isEmpty()) out.add(q.poll());               // front first: same order as the input
6    return out;
7}

LinkedList also implements Queue and Deque. It is a doubly linked list with one node object per element, so each element costs extra memory and the nodes are scattered in the heap, which is unkind to the CPU cache. It permits null elements, which can make poll() ambiguous: after offer(null), poll() returns null although the queue was not empty.

Unless you need null elements or list operations such as get(i), use ArrayDeque for queues. It is usually faster and smaller.