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 (Figure 16.5.1).
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 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.
Subsection16.5.1The Queue Class
The Queue class is also trivial to derive from List (Figure 16.5.2). Here we just restrict operations to the insertAtRear() and removeFirst() methods (Listing 16.5.3). To test the methods of this class, we replace the push() and pop() operations of the last example to enqueue() and dequeue(), respectively (Listing 16.5.4). In this case, the letters of the test string will come out of the queue in the same order they went in—FIFO.
Principle16.5.5.EFFECTIVE DESIGN: ADTs.
ADTs encapsulate and manage the difficult tasks involved in manipulating the data structure. But because of their extensibility, they can be used in a wide range of applications.
ExercisesSelf-Study Exercise
1.Queue Test.
The complete implementation of the Queue ADT as a subclass of List is given here. To test it, add code to the main method that enqueues every character in a string, then prints the queue, then de-queues all elements of the queue. (Note: the Character(char) constructor has been deprecated. To create a Character object, you can use the static method Character.valueOf(char) instead.)
Hint.
Your algorithm should loop through the string enqueing each character onto the queue. Once all the characters have been stored, use another loop to dequeue all the characters until the queue is empty.
2.Queue Peek.
Using the code on the previous exercise, 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 queue without removing it.