Queue model

A queue is a collection with two working ends. New values join at the **rear**; values are served from the **front**. The value that has waited longest always leaves first: first in, first out (FIFO). This is the mirror image of a stack, where the newest value leaves first.

FIFO matches problems where fairness or arrival order matters: print jobs, network packets, tasks waiting for a worker, and the frontier of a breadth-first search. Run the animation and compare the output order with the order of the enqueues.

1class BoundedQueue {
2    private final ArrayDeque<Integer> q = new ArrayDeque<>(); private final int capacity;
3    boolean offer(int x) {
4        if (q.size() == capacity) return false;          // overflow: reject
5        q.addLast(x); return true;                       // join at the rear
6    }
7    Integer poll() {
8        return q.pollFirst();                            // front leaves first; null when empty
9    }
10    Integer peek() { return q.peekFirst(); }            // front, not removed
11}

Enqueue adds a value at the rear. It touches only the rear end, so a good implementation does it in O(1) and never moves the values already waiting. In Java the Queue interface offers two methods: offer(x) returns false if the queue cannot accept the value, and add(x) throws IllegalStateException in that case.

For an unbounded queue such as ArrayDeque both methods always succeed, so the difference only matters for bounded queues such as ArrayBlockingQueue.

1static void enqueueAll(Queue<Integer> queue, int[] values) {
2    for (int v : values) {
3        if (!queue.offer(v)) {                       // bounded queue: reject without throwing
4            System.out.println("rejected " + v);
5        }
6    }
7}

Dequeue removes and returns the front value. Java again gives a pair of methods: poll() returns null when the queue is empty, remove() throws NoSuchElementException. Because ArrayDeque does not allow null elements, a null from poll() can only mean empty.

Prefer poll() in loops that drain a queue and remove() when an empty queue would be a bug you want to see immediately.

The **front** (also called the head) is the value that will leave next; the **rear** (the tail) is the value that joined last. peek() reads the front without removing it. The Queue interface has no method to read the rear: use a Deque (peekLast()) or keep your own reference when you need it.

An implementation therefore tracks two positions. An array queue keeps two indices, a linked queue keeps two node references. The next lessons show both.

• front = oldest value = next to be dequeued
• rear = newest value = last one enqueued
• With one value, front and rear are the same element
• peek() looks at the front only; it never changes the queue

**Underflow** is dequeuing or peeking at an empty queue. **Overflow** is enqueuing into a queue that is full. Only bounded queues can overflow; an ArrayDeque or LinkedList simply grows.

ArrayBlockingQueue is a bounded queue: offer returns false when it is full and add throws IllegalStateException with the message Queue full. Choose the Bounded option in the animation, give it a capacity of 2 and enqueue three values to watch the overflow; the “Underflow” preset shows poll and peek on an empty queue.

1class BoundedQueue {
2    private final ArrayDeque<Integer> q = new ArrayDeque<>(); private final int capacity;
3    boolean offer(int x) {
4        if (q.size() == capacity) return false;          // overflow: reject
5        q.addLast(x); return true;                       // join at the rear
6    }
7    Integer poll() {
8        return q.pollFirst();                            // front leaves first; null when empty
9    }
10    Integer peek() { return q.peekFirst(); }            // front, not removed
11}

An invariant is a fact that must hold after every operation. If any of these breaks, the structure is corrupt, and checking them is the fastest way to debug a hand-written queue.