19.5 Queues

Recall that 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.

19.5.1 Applications of Queues

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

19.5.2 Implementing a Class Template Queue Class Based By Inheriting from List

The program of Figs. 19.16–19.17 creates a Queue class template (Fig. 19.16) through private inheritance (line 9) of the List class template from Fig. 19.5. The Queue has member functions enqueue (Fig. 19.16, lines 12–14), dequeue (lines 17–19), isQueueEmpty (lines 22–24) and printQueue (lines 27–29). These are essentially the insertAt-Back, removeFromFront, isEmpty and print functions of the List class template. Of course, the List class template contains other member functions that we do 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 class—enqueue calls insertAtBack (line 13), dequeue calls removeFromFront (line 18), isQueueEmpty calls isEmpty (line 23) and printQueue calls print (line 28). As with the Stack example in Fig. 19.13, this delegation requires explicit use of the this pointer in isQueueEmpty and printQueue to avoid compilation errors.

Fig. 19.16 Queue class-template definition.

Alternate View 

1   // Fig. 19.16: Queue.h 
2   // Queue class-template definition. 
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   public: 
11      // enqueue calls List member function insertAtBack 
12      void enqueue(const QUEUETYPE& data) {
13         insertAtBack(data);
14      }
15
16      // dequeue calls List member function removeFromFront
17      bool dequeue(QUEUETYPE& data) {
18         return removeFromFront(data);
19      }
20
21      // isQueueEmpty calls List member function isEmpty 
22      bool isQueueEmpty() const {
23         return this->isEmpty();
24      }
25
26      // printQueue calls List member function print 
27      void printQueue() const {
28         this->print();
29      }
30   };
31
32   #endif

19.5.3 Testing the Queue Class Template

Figure 19.17 uses the Queue class template to instantiate integer queue intQueue of type Queue<int> (line 8). Integers 0 through 2 are enqueued to intQueue (lines 13–16), then dequeued from intQueue in first-in, first-out order (lines 21–25). Next, the program instantiates queue doubleQueue of type Queue<double> (line 27). Values 1.1, 2.2 and 3.3 are enqueued to doubleQueue (lines 33–37), then dequeued from doubleQueue in first-in, first-out order (lines 42–46).


Fig. 19.17 Queue-processing program.

Alternate View 

 1   // Fig. 19.17: fig19_17.cpp
 2   // Queue-processing program.
 3   #include <iostream>
 4   #include "Queue.h" // Queue class definition
 5   using namespace std;
 6
 7   int main() {
 8      Queue<int> intQueue; // create Queue of integers
 9
10      cout << "processing an integer Queue" << endl;
11
12      // enqueue integers onto intQueue
13      for (int i{0}; i < 3; ++i) {
14         intQueue.enqueue(i);  
15         intQueue.printQueue();
16      } 
17
18      int dequeueInteger; // store dequeued integer
19
20      // dequeue integers from intQueue
21      while ( !intQueue.isQueueEmpty() ) {
22         intQueue.dequeue(dequeueInteger);
23         cout << dequeueInteger << " dequeued" << endl;
24         intQueue.printQueue();
25      }
26
27      Queue<double> doubleQueue; // create Queue of doubles
28      double value{1.1};
29
30      cout << "processing a double Queue" << endl;
31
32      // enqueue floating-point values onto doubleQueue
33      for (int j = 0; j < 3; ++j) {
34         doubleQueue.enqueue(value);
35         doubleQueue.printQueue();  
36         value += 1.1;
37      } 
38
39      double dequeueDouble; // store dequeued double
40
41      // dequeue floating-point values from doubleQueue
42      while (!doubleQueue.isQueueEmpty() ) {
43         doubleQueue.dequeue(dequeueDouble);
44         cout << dequeueDouble << " dequeued" << endl;
45         doubleQueue.printQueue();
46      }
47   }


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
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset