Queues: First In, First Out

A line at the ticket counter

The first person to join the line is the first to be served: First In, First Out (FIFO). People join at the back and leave from the front.

Why not just an ArrayList?

Removing from the front of an ArrayList shifts everyone: O(n) per person. A queue avoids that with two indexes that move forward and wrap around the array like a clock – a circular queue:

class CircularQueue {
    private int[] items;
    private int front = 0, size = 0;

    CircularQueue(int capacity) { items = new int[capacity]; }

    void offer(int x) {                               // join at the back
        items[(front + size) % items.length] = x;
        size++;
    }

    int poll() {                                      // leave from the front
        int x = items[front];
        front = (front + 1) % items.length;           // wrap around
        size--;
        return x;
    }

    boolean isEmpty() { return size == 0; }
}

public class Main {
    public static void main(String[] args) {
        CircularQueue q = new CircularQueue(3);
        q.offer(1); q.offer(2); q.offer(3);
        System.out.println("served " + q.poll());
        q.offer(4);                                   // reuses the freed slot 0
        while (!q.isEmpty()) System.out.println("served " + q.poll());
    }
}

Output

served 1
served 2
served 3
served 4

Java's version

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> line = new ArrayDeque<String>();
        line.offer("Asha");          // join at the back
        line.offer("Bo");
        line.offer("Chen");
        System.out.println("next: " + line.peek());
        System.out.println("served: " + line.poll());   // leave from the front
        System.out.println("still waiting: " + line);
    }
}

Output

next: Asha
served: Asha
still waiting: [Bo, Chen]

Remember: ArrayDeque is both: use push/pop/peek for a stack, and offer/poll/peek for a queue. Don't mix the two styles on the same deque.