Java Generics and Collections

Chapter 14. Queues

A queue is a collection designed to hold elements for processing, yielding them up in the order in which they are to be processed. The corresponding Collections Framework interface Queue (see Figure 14-1) has a number of different implementations embodying different rules about what this order should be. Many of the implementations use the rule that tasks are to be processed in the order in which they were submitted (First In First Out, or FIFO), but other rules are possible—for example, the Collections Framework includes queue classes whose processing order is based on task priority. The Queue interface was introduced in Java 5, motivated in part by the need for queues in the concurrency utilities included in that release. A glance at the hierarchy of implementations shown in Figure 14-2 shows that, in fact, nearly all of the Queue implementations in the Collections Framework are in the package java.util.concurrent.

One classic requirement for queues in concurrent systems comes when a number of tasks have to be executed by a number of threads working in parallel. An everyday example of this situation is that of a single queue of airline passengers being handled by a line of check-in operators. Each operator works on processing a single passenger (or a group of passengers) while the remaining passengers wait in the queue. As they arrive, passengers join the tail of the queue, wait until they reach its head, and are then assigned to the next operator who becomes ...