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 LinkedList1?
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
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.
On the next pages and in related sections, we look at:
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.