Queues, Deques, and Priority Queues - Data Structures and Abstractions with Java - page 242

W aiting for your turn is a fact of life. Most people have spent much time standing in lines at stores,
banks, or movie theaters. You have probably waited on the telephone for an airline representative or a
technical support person, and you may have waited for your printed output to finally reach the printer
in the computer lab. In each of these examples, people wait with the expectation that they will be
served before everyone who has come after them. That is, first come, first served.
A queue is another name for a waiting line, and it is the name of one of the ADTs that we will
investigate in this chapter. Queues are used within operating systems and to simulate real-world
events—that is, they come into play whenever processes or events must wait.
Sometimes you need more flexibility than a queue permits. A double-ended queue, or deque,
organizes data like a queue but enables you to operate on both its oldest and newest entries. And
when the importance of an object depends on criteria other than its arrival time, you can assign it
a priority. You can organize such objects within a priority queue according to their priorities
instead of chronologically.
The queue, deque, and priority queue are three ADTs that this chapter will explore.
The ADT Queue

10.1

Like a stack, the ADT queue organizes its entries according to the order in which they were added.
But while a stack has a last-in, first-out behavior, a queue exhibits a first-in , first-out , or FIFO ,
behavior. To achieve this behavior, all additions to a queue are at its back . The item added most
recently, then, is at the back of a queue. The item that was added earliest is at the front of a queue.
Figure 10-1 provides examples of some common queues.

FIGURE 10-1

Some everyday queues

Note: Among the items in a queue, the one added first, or earliest, is at the front of the
queue, and the one added most recently is at the back of the queue.

A queue, like a stack, restricts access to its entries. Although someone might cut into a line of
people, additions to a software queue must occur at its back. A client can look at or remove only the
entry at the front of the queue. The only way to look at an entry that is not at the front of a queue is

VideoNote

The ADT queue