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.

Queue Class That Inherits from List

The program of Figs. 25.16 and 25.17 creates a queue class by inheriting from a list class. We want the QueueInheritance class (Fig. 25.16) to have methods Enqueue, Dequeue, IsEmpty and Print. Essentially, these are the methods InsertAtBack, RemoveFromFront, IsEmpty and Print 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.

Figure 25.16. QueueInheritance extends class List.

 1 // Fig. 25.16: QueueInheritanceLibrary.cs
 2 // Implementing a queue by inheriting from class List.
 3 using System;
 4 using LinkedListLibrary;
 5
 6 namespace QueueInheritanceLibrary
 7 {
 8 // class QueueInheritance inherits List's capabilities
 9 public class QueueInheritance : List
10 {
11 // pass name "queue" to List constructor
12 public QueueInheritance()
13 : base( "queue" )
14 {
15 } // end constructor
16

17 // place dataValue at end of queue by inserting 18 // dataValue at end of linked list 19 public void Enqueue( object dataValue ) 20 { 21 InsertAtBack( dataValue ); 22 } // end method Enqueue 23 24 // remove item from front of queue by removing 25 // item at front of linked list 26 public object Dequeue() 27 { 28 return RemoveFromFront(); 29 } // end method Dequeue 30 } // end class QueueInheritance 31 } // end namespace QueueInheritanceLibrary

Figure 25.17. Queue created by inheritance.

(This item is displayed on pages 1343 - 1344 in the print version)

 1 // Fig. 25.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( string[] args )
11 {
12 QueueInheritance queue = new QueueInheritance();
13
14 // create objects to store in the stack
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.Print(); 23 queue.Enqueue( aCharacter ); 24 queue.Print(); 25 queue.Enqueue( anInteger ); 26 queue.Print(); 27 queue.Enqueue( aString ); 28 queue.Print(); 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.Print(); 41 } // end while 42 } // end try 43 catch ( EmptyListException emptyListException ) 44 { 45 // if exception occurs, print stack trace 46 Console.Error.WriteLine( emptyListException.StackTrace ); 47 } // end catch 48 } // end method Main 49 } // end class QueueTest

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()
 at QueueInheritanceLibrary.QueueInheritance.Dequeue()
 at QueueTest.QueueTest.Main(String[] args)
 in C:examplesch25Fig25_17QueueTest.cs:line 38

The implementation of each QueueInheritance method calls the appropriate List methodmethod Enqueue calls InsertAtBack and method Dequeue calls RemoveFromFront. Calls to IsEmpty and Print invoke the base-class versions that were inherited from class List into QueueInheritance's public interface. Note that class QueueInheritance uses namespace LinkedListLibrary (Fig. 25.4); thus, the class library for QueueInheritance must have a reference to the LinkedListLibrary class library.

Class QueueInheritanceTest's Main method (Fig. 25.17) creates a QueueInheritance object called queue. Lines 1518 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". Note that class QueueInheritanceTest uses namespace LinkedListLibrary and namespace QueueInheritanceLibrary; thus, the solution for class StackInheritanceTest must have references to both class libraries.

An infinite while loop (lines 3641) dequeues the elements from the queue in FIFO order. When there are no objects left to dequeue, method Dequeue throws an EmptyListException, 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 Print (inherited from class List) to output the contents of the queue after each operation. Note that class QueueInheritanceTest uses namespace LinkedListLibrary (Fig. 25.4) and namespace QueueInheritanceLibrary (Fig. 25.16); thus, the solution for class QueueInheritanceTest must have references to both class libraries.

Trees