Introduction to queues in Java 5

Java 5 adds queues to the Collections framework. A queue is in some ways a sub-construct of a list, usually implemented as a linked list, with the following characteristics:

• unlike a normal list, it is not random access: that is, you can't get or set the element at an arbitrary position in the list;
• get and set operations always take place at the ends of the queue (generally, one "takes from the head" and "puts on the tail").

In a standard queue, the next item to be taken is the one at the head of the queue, i.e. the one that has been there the longest. When items are added to the queue, they are added to the tail. The item at the tail can only be accessed once all the items placed before it have been removed in order.

Why use a queue?

So you may well be thinking: why use a queue if it has these restrictions? Can't you just use a boring old ArrayList or LinkedList¹? It turns out there are at least three main reasons:

• in some cases, a queue is "conceptually what we want";
• eliminating random access allows optimisations for concurrency;
• Java's efficient BlockingQueue implementations can take some of the work out of the most typical use of queues.

Places where we "conceptually" want a queue are where we are dealing with a so-called producer-consumer pattern. That is, one thread "produces" a list of jobs for another thread to pick up. Of course, we could use an ordinary (synchronized) LinkedList if this was purely our motivation. However, it turns out that restricting access to the head and tail of the queue allows for further optimisation for concurrent access.

Queues with thread pools

One place, then, in which queues are useful is for the work queue of a thread pool. Java provides the ThreadPoolExecutor class; when constructing this class, you can pass in the queue that you want the thread pool to use. Or, you can construct your thread pool with one of the utility methods in the Executors class, in which case a default BlockingQueue will be used.

---

1. It turns out that LinkedList has been retrofitted to implement the Queue interface in Java 5. But for many tasks, there are more efficient or suitable queue implementations than a plain LinkedList.

---