Principle 16.5.4. 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.
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.
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 ([cross-reference to target(s) "listing-queueadttest" missing or not unique]). In this case, the letters of the test string will come out of the queue in the same order they went in—FIFO.
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
QueueADT.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.
