Queues

Another commonly used data structure is the queue. A queue is similar to a checkout line in a supermarketthe cashier services the person at the beginning of the line first. Other customers enter the line only at the end and wait for service. Queue nodes are removed only from the head (or front) of the queue and are inserted only at the tail (or end). For this reason, a queue is a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.

Queues have many uses in computer systems. Most computers have only a single processor, so only one application at a time can be serviced. Each application requiring processor time is placed in a queue. The application at the front of the queue is the next to receive service. Each application gradually advances to the front as the applications before it receive service.

Queues are also used to support print spooling. For example, a single printer might be shared by all users of a network. Many users can send print jobs to the printer, even when the printer is already busy. These print jobs are placed in a queue until the printer becomes available. A program called a spooler manages the queue to ensure that, as each print job completes, the next print job is sent to the printer.

Information packets also wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node along the path to the packet's final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.

A file server in a computer network handles file-access requests from many clients throughout the network. Servers have a limited capacity to service requests from clients. When that capacity is exceeded, client requests wait in queues.

Figure 17.13 creates a queue class that contains an object of class List (Fig. 17.3). Class Queue (Fig. 17.13) provides methods enqueue, dequeue, isEmpty and print. Class List contains other methods (e.g., insertAtFront and removeFromBack) that we would rather not make accessible through the public interface of class Queue. By using composition, these methods in the public interface of class List are not accessible to clients of class Queue. Each method of class Queue calls an appropriate List methodmethod enqueue calls List method insertAtBack, method dequeue calls List method removeFromFront, method isEmpty calls List method isEmpty and method print calls List method print. For reuse purposes, class Queue is declared in package com.deitel.jhtp6.ch17.

Figure 17.13. Queue uses class List.

(This item is displayed on pages 836 - 837 in the print version)

 1 // Fig. 17.13: Queue.java
 2 // Class Queue.
 3 package com.deitel.jhtp6.ch17;
 4
 5 public class Queue
 6 {
 7 private List queueList;
 8
 9 // no-argument constructor
10 public Queue()
11 {
12 queueList = new List( "queue" );
13 } // end Queue no-argument constructor
14
15 // add object to queue
16 public void enqueue( Object object )
17 {
18 queueList.insertAtBack( object );
19 } // end method enqueue
20
21 // remove object from queue
22 public Object dequeue() throws EmptyListException
23 {
24 return queueList.removeFromFront();
25 } // end method dequeue
26
27 // determine if queue is empty
28 public boolean isEmpty()
29 {
30 return queueList.isEmpty();
31 } // end method isEmpty
32
33 // output queue contents
34 public void print()
35 {
36 queueList.print();
37 } // end method print
38 } // end class Queue

Class QueueTest (Fig. 17.14) method main creates an object of class Queue called queue. Lines 13, 15, 17 and 19 enqueue four integers, taking advantage of autoboxing to insert Integer objects into the queue. Lines 2732 use an infinite while loop to dequeue the objects in first-in, first-out order. When the queue is empty, method dequeue throws an EmptyListException, and the program displays the exception's stack trace.

Figure 17.14. Queue processing program.

(This item is displayed on pages 837 - 838 in the print version)

 1 // Fig. 17.14: QueueTest.java
 2 // Class QueueTest.
 3 import com.deitel.jhtp6.ch17.Queue;
 4 import com.deitel.jhtp6.ch17.EmptyListException;
 5
 6 public class QueueTest
 7 {
 8 public static void main( String args[] )
 9 {
10 Queue queue = new Queue();
11
12 // use enqueue method
13 queue.enqueue( -1 ); 
14 queue.print(); 
15 queue.enqueue( 0 ); 
16 queue.print(); 
17 queue.enqueue( 1 ); 
18 queue.print(); 
19 queue.enqueue( 5 ); 
20 queue.print(); 
21
22 // remove objects from queue
23 try
24 {
25 Object removedObject = null;
26
27 while ( true )
28 {
29 removedObject = queue.dequeue(); // use dequeue method
30 System.out.printf( "%s dequeued
", removedObject );
31 queue.print();
32 } // end while
33 } // end try
34 catch ( EmptyListException emptyListException )
35 {
36 emptyListException.printStackTrace();
37 } // end catch
38 } // end main
39 } // end class QueueTest

 

The queue is: -1

The queue is: -1 0

The queue is: -1 0 1

The queue is: -1 0 1 5

-1 dequeued
The queue is: 0 1 5

0 dequeued
The queue is: 1 5

1 dequeued
The queue is: 5

5 dequeued
Empty queue
com.deitel.jhtp6.ch17.EmptyListException: queue is empty
 at com.deitel.jhtp6.ch17.List.removeFromFront(List.java:81)
 at com.deitel.jhtp6.ch17.Queue.dequeue(Queue.java:24)
 at QueueTest.main(QueueTest.java:29)