19. Data Structures: Lists, Stacks, and Queues

19.5. The Queue ADT

A queue is a special type of list that limits insertions to the end of the list and removals to the front of the list. Therefore, it enforces first-in–first-out (FIFO) behavior on the list. Think of the waiting line at the salad bar. You enter the line at the rear and you leave the line at the front (Fig. 16.24).

The queue operations are conventionally called enqueue, for insert, and

dequeue, for remove, respectively. Thus, the queue ADT stores a list of data and supports the following operations:

Enqueue—insert an object onto the rear of the list. Dequeue—remove the object at the front of the list. Empty—return true if the queue is empty.

Queues are useful for a number of computing tasks. For example, the

ready, waiting, and blocked queues used by the CPU scheduler all use a

 

,,

 

 

 

 

 

 

 

 

 

 

 

J

Figure 16.23: A method to test the Stack ADT, which is used here to reverse a String of letters.

 

 

 

 

 

FIFO protocol. Queues are also useful in implementing certain kinds of simulations. For example, the waiting line at a bank or a bakery can be modeled using a queue.

 

 

 

 

queue is a list that

 

ns at the rear and


Head

 

front only.

 

The Queue Class

The Queue class is also trivial to derive from List (Fig. 16.25). Here we just restrict operations to the insertAtRear() and removeFirst() methods (Fig. 16.26). To test the methods of this class, we replace the push() and pop() operations of the last example to enqueue() and dequeue(), respectively (Fig. 16.27). In this case, the letters of the test string will come out of the queue in the same order they went in—FIFO.

,,

 

 

 

 

 

 

Figure 16.25: The Queue’s enqueue() and dequeue() methods can use the List’s insertAtRear() and

removeFirst() methods, respectively.


 

J

Figure 16.26: The Queue ADT.

 

,,

 

 

 

 

 

 

 

 

 

 

 

J

Figure 16.27: A method to test the Queue ADT. Letters inserted in a queue come out in the same order they went in.

 

 

SELF-STUDY EXERCISE

EXERCISE 16.10 Define a peekLast() method for the Queue class. It should take no parameters and return an Object. It should return a reference to the Object stored in the last Node of the list without removing it.