Queues
A queue is similar to a supermarket checkout linethe first person in line is serviced first, and other customers enter the line at the end and wait to be serviced. Queue nodes are removed only from the head of the queue and are inserted only at the tail of the queue. For this reason, a queue is referred to as a first-in, first-out (FIFO) data structure. The insert and remove operations are known as enqueue and dequeue.
Queues have many applications in computer systems. Computers that have a single processor can service only one user at a time. Entries for the other users are placed in a queue. Each entry gradually advances to the front of the queue as users receive service. The entry at the front of the queue is the next to 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 managers 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 on the network 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.
The program of Figs. 21.1621.17 creates a Queue class template (Fig. 21.16) through private inheritance (line 9) of the List class template of Fig. 21.4. We want the Queue to have member functions enqueue (lines 1316), dequeue (lines 1922), isQueueEmpty (lines 2528) and printQueue (lines 3134). Note that these are essentially the insertAtBack, removeFromFront, isEmpty and print functions of the List class template. Of course, the List class template contains other member functions (i.e., insertAtFront and removeFromBack) that we would not want to make accessible through the public interface to the Queue class. So when we indicate that the Queue class template is to inherit the List class template, we specify private inheritance. This makes all the List class template's member functions private in the Queue class template. When we implement the Queue's member functions, we have each of these call the appropriate member function of the list classenqueue calls insertAtBack (line 15), dequeue calls removeFromFront (line 21), isQueueEmpty calls isEmpty (line 27) and printQueue calls print (line 33). Again, this is called delegation.
Figure 21.16. Queue class-template definition.
(This item is displayed on page 1022 in the print version)
|
1 // Fig. 21.16: Queue.h 2 // Template Queue class definition derived from class List. 3 #ifndef QUEUE_H 4 #define QUEUE_H 5 6 #include "List.h" // List class definition 7 8 template< typename QUEUETYPE > 9 class Queue : private List< QUEUETYPE > 10 { 11 public: 12 // enqueue calls List member function insertAtBack 13 void enqueue( const QUEUETYPE &data ) 14 { 15 insertAtBack( data ); 16 } // end function enqueue 17 18 // dequeue calls List member function removeFromFront 19 bool dequeue( QUEUETYPE &data ) 20 { 21 return removeFromFront( data ); 22 } // end function dequeue 23 24 // isQueueEmpty calls List member function isEmpty 25 bool isQueueEmpty() const 26 { 27 return isEmpty(); 28 } // end function isQueueEmpty 29 30 // printQueue calls List member function print 31 void printQueue() const 32 { 33 print(); 34 } // end function printQueue 35 }; // end class Queue 36 37 #endif |
Figure 21.17. Queue-processing program.
(This item is displayed on pages 1023 - 1024 in the print version)
|
1 // Fig. 21.17: Fig21_17.cpp 2 // Template Queue class test program. 3 #include 4 using std::cout; 5 using std::endl; 6 7 #include "Queue.h" // Queue class definition 8 9 int main() 10 { 11 Queue< int > intQueue; // create Queue of integers 12 13 cout << "processing an integer Queue" << endl; 14 15 // enqueue integers onto intQueue 16 for ( int i = 0; i < 3; i++ ) 17 { 18 intQueue.enqueue( i ); 19 intQueue.printQueue(); 20 } // end for 21 22 int dequeueInteger; // store dequeued integer 23 24 // dequeue integers from intQueue 25 while ( !intQueue.isQueueEmpty() ) 26 { 27 intQueue.dequeue( dequeueInteger ); 28 cout << dequeueInteger << " dequeued" << endl; 29 intQueue.printQueue(); 30 } // end while 31 32 Queue< double > doubleQueue; // create Queue of doubles 33 double value = 1.1; 34 35 cout << "processing a double Queue" << endl; 36 37 // enqueue floating-point values onto doubleQueue 38 for ( int j = 0; j < 3; j++ ) 39 { 40 doubleQueue.enqueue( value ); 41 doubleQueue.printQueue(); 42 value += 1.1; 43 } // end for 44 45 double dequeueDouble; // store dequeued double 46 47 // dequeue floating-point values from doubleQueue 48 while ( !doubleQueue.isQueueEmpty() ) 49 { 50 doubleQueue.dequeue( dequeueDouble ); 51 cout << dequeueDouble << " dequeued" << endl; 52 doubleQueue.printQueue(); 53 } // end while 54 55 return 0; 56 } // end main
|
Figure 21.17 uses the Queue class template to instantiate integer queue intQueue of type Queue< int > (line 11). Integers 0 through 2 are enqueued to intQueue (lines 1620), then dequeued from intQueue in first-in, first-out order (lines 2530). Next, the program instantiates queue doubleQueue of type Queue< double > (line 32). Values 1.1, 2.2 and 3.3 are enqueued to doubleQueue (lines 3843), then dequeued from doubleQueue in first-in, first-out order (lines 4853).