Skip to main content
Logo image

Java, Java, Java: Object-Oriented Problem Solving, 2024E

Ralph Morelli, Ralph Walde, Beryl Hoffman, David G. Cooper

Section 16.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 (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.
Figure 16.5.1. A queue is a list that permits insertions at the rear and removals at the front only.

Subsection 16.5.1 The 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.
Figure 16.5.2. The Queue’s enqueue() and dequeue() methods can use the List’s insertAtRear() and removeFirst() methods, respectively.
public class Queue extends List {
     public Queue() {
         super();          // Initialize the list
     }
     public void enqueue(Object obj) {
         insertAtRear( obj );
     }
     public Object dequeue() {
         return removeFirst();
     }
}// Queue
Listing 16.5.3. The QueueADT.
public static void main(String argv[]) {
     Queue queue = new Queue();
     String string = "Hello this is a test string";
     System.out.println("String: " + string);
     for (int k = 0; k < string.length(); k++)
         queue.enqueue( new Character(string.charAt(k)));
     System.out.println("The current queue:");
     queue.print();
     Object o = null;
     System.out.println("Dequeuing:");
     while (!queue.isEmpty()) {
         o  = queue.dequeue();
         System.out.print( o.toString() );
     }
} // main()
Listing 16.5.4. A method to test the QueueADT. Letters inserted in a queue come out in the same order they went in.

Exercises Self-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.
You have attempted of activities on this page.
PrevTopNext