Queue and Deque

Process work in order with Queue, use ArrayDeque as a queue or stack, pick PriorityQueue for urgency and BlockingQueue between threads.

Syntax

Queue<Job> jobs = new ArrayDeque<>();
jobs.offer(job);            // add at the tail
Job next = jobs.poll();     // take the head, null if empty
Deque<String> stack = new ArrayDeque<>();
stack.push("a");  stack.pop();

A Queue holds elements waiting to be processed. Most queues are first in, first out: you add at the tail and take from the head. A Deque (double-ended queue, said "deck") lets you add and remove at both ends, so the same class works as a queue or a stack.

Two families of methods

Operation	Throws on failure	Returns a special value
Insert	`add(e)`	`offer(e)` returns `false`
Remove head	`remove()`	`poll()` returns `null`
Look at head	`element()`	`peek()` returns `null`

Use offer, poll and peek in loops that drain a queue, because an empty queue is normal there, not an error. On a Deque, push, pop and peek treat the head as the top of a stack.

Which class

ArrayDeque is the default for both queues and stacks. It is faster than LinkedList and replaces the old Stack class, which is synchronised and extends Vector. It does not accept null, which is what lets poll use null to mean empty.
PriorityQueue hands out the smallest element first by natural order or a comparator. Only poll and peek follow that order; printing it or iterating over it shows the internal heap layout, not a sorted list. Elements with equal priority come out in no guaranteed order.
BlockingQueue implementations such as ArrayBlockingQueue and LinkedBlockingQueue are for passing work between threads. put waits when a bounded queue is full and take waits when it is empty.

Back-end angle

In-process queues suit small jobs inside one service: sending a confirmation email after a response, a sliding window of request timestamps for rate limiting, or a breadth-first walk over a category tree. A bounded BlockingQueue applies back-pressure, so a burst of traffic makes producers wait instead of filling the heap. An unbounded queue in front of slow work is how services run out of memory.

These queues live in memory and disappear on restart or redeploy. Work that must survive a crash belongs in a database table or a message broker, not an ArrayDeque.

Example

Loading editor…

Press Run to execute the code.

When to use it

Queue follow-up work such as welcome emails behind a bounded BlockingQueue so the HTTP response is not delayed.
Keep a deque of recent request timestamps per API key to answer 429 Too Many Requests.
Walk a category tree breadth first with an ArrayDeque to build breadcrumb data.

More examples

Most urgent first with PriorityQueue

The comparator decides urgency, with the lowest number polled first. Add a tie-breaker such as a sequence number when tasks of equal priority must keep their arrival order.

record Task(String name, int priority) {}

void main() {
    PriorityQueue<Task> queue = new PriorityQueue<>(Comparator.comparingInt(Task::priority));
    queue.add(new Task("rebuild-search-index", 5));
    queue.add(new Task("charge-card", 1));
    queue.add(new Task("send-receipt", 2));
    queue.add(new Task("cleanup-temp-files", 9));

    while (!queue.isEmpty()) {
        Task task = queue.poll();
        IO.println(task.priority() + " " + task.name());
    }
}
// Output:
// 1 charge-card
// 2 send-receipt
// 5 rebuild-search-index
// 9 cleanup-temp-files

A sliding-window rate limiter

Old timestamps leave from the head and new ones join at the tail, which is exactly what a deque is for. Passing the time in, instead of reading the clock inside, makes the limiter easy to test.

class RateLimiter {
    private final Deque<Long> window = new ArrayDeque<>();
    private final int limit;
    private final long windowMs;

    RateLimiter(int limit, long windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
    }

    boolean allow(long nowMs) {
        while (!window.isEmpty() && window.peekFirst() <= nowMs - windowMs) {
            window.pollFirst();               // drop timestamps outside the window
        }
        if (window.size() >= limit) {
            return false;
        }
        window.addLast(nowMs);
        return true;
    }
}

void main() {
    var limiter = new RateLimiter(3, 1000);
    long[] requestTimes = {0, 100, 200, 300, 1050, 1150};
    for (long t : requestTimes) {
        IO.println("t=" + t + " " + (limiter.allow(t) ? "allowed" : "429"));
    }
}
// Output:
// t=0 allowed
// t=100 allowed
// t=200 allowed
// t=300 429
// t=1050 allowed
// t=1150 allowed

Producer and consumer with a bounded BlockingQueue

With a capacity of 2 the producer can never get more than two orders ahead of the consumer. The DONE marker tells the consumer to stop without polling or sleeping.

void main() throws InterruptedException {
    BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);

    Thread producer = Thread.ofVirtual().start(() -> {
        try {
            for (String order : List.of("order-1", "order-2", "order-3", "order-4")) {
                queue.put(order);             // waits while the queue is full
            }
            queue.put("DONE");
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    });

    String item;
    while (!(item = queue.take()).equals("DONE")) {
        IO.println("processed " + item);
    }
    producer.join();
    IO.println("remaining capacity: " + queue.remainingCapacity());
}
// Output:
// processed order-1
// processed order-2
// processed order-3
// processed order-4
// remaining capacity: 2

Discussion

Be the first to comment on this lesson.

Two families of methods

Which class

Back-end angle

Example

When to use it

More examples

Most urgent first with PriorityQueue

A sliding-window rate limiter

Producer and consumer with a bounded BlockingQueue

Related

Discussion