Our study of the fundamental ADTs concludes with the Queue ADT in this chapter.
Just as the Stack ADT is natural and intuitive because stacks are ubiquitous in
our everyday, physical world, so is the Queue ADT. The Queue ADT is almost identical
to the Stack ADT except for the one key difference, and often it is treated as an
inseparable sibling of the Stack ADT.
The Queue ADT models a line of objects, such as people or vehicles, waiting
to be serviced. Students waiting in line to pay for food at the cashier in the student
union cafeteria, moviegoers waiting in line to enter the 16-screen cinnaplex, and vehicles
waiting in line at the signal-controlled freeway on-ramp are all examples of
queues. The defining feature of a queue is that the object at the front of the queue is
the next to be serviced (imagine the ensuing chaos and havoc at Disney’s Space
Mountain if you randomly picked people in line for the next ride) and a new object
is added to the end, or tail, of the queue.
As in the previous chapters, we begin with the definition of the Queue ADT
and then provide two different implementations based on the array and the linked
list. We will conclude the chapter with a special variation of a queue called a priority
queue.
