Java Generics and Collections, 2nd Edition

Chapter 13. 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<E> 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 a later addition to the framework, motivated in part by the need for queues in the concurrency utilities included at the same time. A glance at the hierarchy of implementations shown in Figure 13-1 shows that, in fact, nearly all the Queue implementations in the Collections Framework are in the package java.util.concurrent.

One classic requirement for queues in concurrent systems arises 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 and wait until they reach its head, when they are assigned to the next operator who becomes ...