Queues

Written Explanation

The operations

Trace:

offer(A)        front -> A <- back
offer(B)        front -> A B <- back
offer(C)        front -> A B C <- back
poll() -> A     front -> B C <- back

The first in (A) was the first out. That is FIFO.

Java: Queue and ArrayDeque

Queue<E> is the interface for this behavior, and ArrayDeque is a common implementation. The JDK documentation for ArrayDeque says it is likely to be faster than LinkedList when used as a queue, and that it prohibits null items.

Queue<String> q = new ArrayDeque<>();
q.offer("Ana");
q.offer("Omar");
String next = q.poll();   // "Ana"

The Queue interface has two versions of some operations. offer, poll, and peek signal problems with a special value (false or null). The older-style add, remove, and element throw exceptions instead. For a general queue, prefer offer and poll, and remember that poll returns null when the queue is empty. Since ArrayDeque does not allow null items, a null from poll always means "empty".

Why an array queue is tricky

Suppose you store the queue in a plain array where the front is always index 0. offer writes at size (cheap). But poll removes index 0, and to keep the front at index 0 you must shift every other item left: O(n) each time. That is the problem from Lesson 1. A queue built on this idea is correct but slow, and the slowness grows with the queue's length.

Two standard fixes make both ends O(1):

1. A linked list with head and tail. offer attaches at the tail; poll detaches the head. Nothing shifts.
2. A circular array (ring buffer). Keep an index head for the front and let positions wrap around the end of the array using the remainder operator. poll just moves head forward by one; no shifting.

capacity 3:  [ _ , 2 , 3 ]    head = 1, size = 2
offer(4) goes to (head + size) % 3 = 0 -> [ 4 , 2 , 3 ]

The back of the queue wrapped around to the start of the array. ArrayDeque works on a related idea: an array with indexes that move at both ends, growing by copying when full, as in Lesson 2.

A linked queue

void offer(T v) {
    Node<T> n = new Node<>(v);
    if (tail == null) { head = n; tail = n; }
    else { tail.next = n; tail = n; }
    size++;
}

T poll() {
    if (head == null) return null;
    T v = head.value;
    head = head.next;
    if (head == null) tail = null;   // queue became empty
    size--;
    return v;
}

This is Lesson 3's addLast and removeFirst. The line if (head == null) tail = null is the same trap as before: when the last node leaves, the tail must not keep pointing at it.

Choosing: stack or queue?

Ask in which order items should come back out.

Queues also drive breadth-first search (you will meet this when graphs appear) and round-robin scheduling, where each task takes a turn and then rejoins the back.

Other kinds of queue

Real systems have variations that you will meet later: a priority queue serves the most important item first rather than the oldest, a bounded queue has a maximum length, and a deque (double-ended queue) lets you add and remove at both ends. ArrayDeque is a deque, which is why it works as both a stack and a queue.