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

 

 processing an integer Queue
 The list is: 0

 The list is: 0 1

 The list is: 0 1 2

 0 dequeued
 The list is: 1 2

 1 dequeued
 The list is: 2

 2 dequeued
 The list is empty

 processing a double Queue
 The list is: 1.1

 The list is: 1.1 2.2

 The list is: 1.1 2.2 3.3

 1.1 dequeued
 The list is: 2.2 3.3

 2.2 dequeued
 The list is: 3.3

 3.3 dequeued
 The list is empty

 All nodes destroyed

 All nodes destroyed

 

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).