19.6 Queues

Another commonly used data structure is the queue. A queue is similar to a checkout line in a supermarket—the 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. Computers with only a single processor can service only one app at a time. Each app requiring processor time is placed in a queue. The app at the front of the queue is the next to receive service. Each app gradually advances to the front as the apps 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 one 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.

Queue Class That Inherits from List

The code in Fig. 19.16 creates a queue class by inheriting from a list class. We want the QueueInheritance class (Fig. 19.16) to have methods Enqueue, Dequeue, IsEmpty and Display. Essentially, these are the methods InsertAtBack, RemoveFromFront, IsEmpty and Display of class List. Of course, the list class contains other methods (such as InsertAtFront and RemoveFromBack) that we would rather not make accessible through the public interface to the queue class. Remember that all methods in the public interface of the List class are also public methods of the derived class QueueInheritance.

The implementation of each QueueInheritance method calls the appropriate List method—method Enqueue calls InsertAtBack and method Dequeue calls RemoveFrom-Front. Calls to IsEmpty and Display invoke the base-class versions that were inherited from class List into QueueInheritance’s public interface. Class QueueInheritance uses namespace LinkedListLibrary (Fig. 19.4); thus, the class library for QueueInheritance must have a reference to the LinkedListLibrary class library. Just as we demonstrated with stacks, we could use composition to implement a queue class that does not expose the unwanted methods of class List.

Fig. 19.16 Implementing a queue by inheriting from class List.

Alternate View 

  1   // Fig. 19.16: QueueInheritanceLibrary.cs
  2   // Implementing a queue by inheriting from class List.
  3   using LinkedListLibrary;
  4
  5   namespace QueueInheritanceLibrary
  6   {
  7      // class QueueInheritance inherits List's capabilities
  8      public class QueueInheritance : List
  9      {
 10         // pass name "queue" to List constructor
 11         public QueueInheritance() : base("queue") { }
 12
 13         // place dataValue at end of queue by inserting
 14         // dataValue at end of linked list
 15         public void Enqueue(object dataValue)
 16         {
 17            InsertAtBack(dataValue);
 18         }
 19
 20         // remove item from front of queue by removing
 21         // item at front of linked list
 22         public object Dequeue()
 23         {
 24            return RemoveFromFront();
 25         }
 26      }
 27   }

Class QueueTest’s Main method (Fig. 19.17) creates a QueueInheritance object called queue. Lines 15–18 define four values that will be enqueued and dequeued. The program enqueues (lines 21, 23, 25 and 27) a bool containing true, a char containing '$', an int containing 34567 and a string containing "hello". Class QueueTest uses namespace LinkedListLibrary and namespace QueueInheritanceLibrary; thus, the solution for class QueueTest must have references to both class libraries.

Fig. 19.17 Testing class QueueInheritance.

Alternate View 

  1   // Fig. 19.17: QueueTest.cs
  2   // Testing class QueueInheritance.
  3   using System;
  4   using QueueInheritanceLibrary;
  5   using LinkedListLibrary;
  6
  7   // demonstrate functionality of class QueueInheritance
  8   class QueueTest
  9   {
 10        static void Main()
 11      {
 12         QueueInheritance queue = new QueueInheritance();
 13
 14         // create objects to store in the queue
 15         bool aBoolean = true;
 16         char aCharacter = '$';
 17         int anInteger = 34567;
 18         string aString = "hello";
 19
 20         // use method Enqueue to add items to queue
 21         queue.Enqueue(aBoolean);
 22         queue.Display();
 23         queue.Enqueue(aCharacter);
 24         queue.Display();
 25         queue.Enqueue(anInteger);
 26         queue.Display();
 27         queue.Enqueue(aString);
 28         queue.Display();
 29
 30         // use method Dequeue to remove items from queue
 31         object removedObject = null;
 32
 33         // remove items from queue
 34         try
 35         {
 36            while (true)
 37            {
 38               removedObject = queue.Dequeue();
 39               Console.WriteLine($"{removedObject} dequeued");
 40               queue.Display();
 41            }
 42         }
 43         catch (EmptyListException emptyListException)
 44         {
 45            // if exception occurs, write stack trace
 46            Console.Error.WriteLine(emptyListException.StackTrace);
 47         }
 48      }
 49   }


The queue is: True

The queue is: True $

The queue is: True $ 34567

The queue is: True $ 34567 hello

True dequeued
The queue is: $ 34567 hello

$ dequeued
The queue is: 34567 hello

34567 dequeued
The queue is: hello

hello dequeued
Empty queue
   at LinkedListLibrary.List.RemoveFromFront() in C:UsersPaulDeitel
      Documentsexamplesch19Fig19_04LinkedListLibrary
      LinkedListLibraryLinkedListLibrary.cs:line 81
   at QueueInheritanceLibrary.QueueInheritance.Dequeue() in C:Users
      PaulDeitelDocumentsexamplesch19Fig19_16QueueInheritanceLibrary
      QueueInheritanceLibraryQueueInheritance.cs:line 24
   at QueueTest.Main(String[] args) in C:UsersPaulDeitelDocuments
      examplesch19Fig19_17QueueTestQueueTestQueueTest.cs:line 38

An infinite while loop (lines 36–41) dequeues the elements from the queue in FIFO order. When there are no objects left to dequeue, method Dequeue throws an Empty-ListException, and the program displays the exception’s stack trace, which shows the program-execution stack at the time the exception occurred. The program uses method Display (inherited from class List) to output the contents of the queue after each operation.

..................Content has been hidden....................

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