Section 24.6. Queues

24.6. 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. The operating system places each application requiring processor time 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 the users in a network. Many users can send print jobs to the printer, even when the printer is busy. The operating system places these print jobs 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. 24.16 and 24.17 creates a queue class by inheriting from a list class. We want the QueueInheritance class (Fig. 24.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 24.16. QueueInheritance extends class List.

  1  ' Fig. 24.16: QueueInheritanceLibrary.vb  2  ' Implementing a queue by inheriting  from class List.  3  Imports LinkedListLibrary  4  5  Public Class QueueInheritance : Inherits List  6     ' pass name "queue" to List constructor  7     Public Sub New()  8        MyBase.New("queue")  9     End Sub ' New 10 11     ' place dataValue at end  of queue  by inserting 12     ' dataValue at end of linked list 13     Public Sub Enqueue(ByVal  dataValue As Object) 14        InsertAtBack(dataValue) 15     End Sub ' Enqueue 16 17     ' remove item from front of queue by removing 18     ' item at front of linked list 19     Public Function Dequeue() As Object 20        Return RemoveFromFront() 21     End Function ' Dequeue 22  End Class ' QueueInheritance 

Figure 24.17. Queue created by inheritance.

  1  ' Fig. 24.17: QueueTest.vb  2  ' Testing class QueueInheritance.  3  Imports QueueInheritanceLibrary  4  Imports LinkedListLibrary  5  6  ' demonstrate functionality of class QueueInheritance  7  Module QueueTest  8    Sub Main()  9       Dim queue As New QueueInheritance() 10 11       ' create objects to store in the stack 12       Dim aBoolean As Boolean = True 13       Dim aCharacter As Char = "$"c 14       Dim anInteger As Integer = 34567 15       Dim aString As String = "hello" 16 17       ' use method Enqueue to add items to queue 18       queue.Enqueue(aBoolean)                    19       queue.Print()                              20       queue.Enqueue(aCharacter)                  21       queue.Print()                              22       queue.Enqueue(anInteger)                   23       queue.Print()                              24       queue.Enqueue(aString)                     25       queue.Print()                              26 27       ' use method Dequeue to remove items from queue 28       Dim removedObject As Object = Nothing 29 30       ' remove items from queue 31       Try 32          While True 33             removedObject = queue.Dequeue() 34             Console.WriteLine(removedObject & " dequeued") 35             queue.Print() 36          End While 37       Catch exception As EmptyListException 38          ' if exception occurs, print stack trace 39          Console.Error.WriteLine(exception.StackTrace) 40       End Try 41    End Sub ' Main 42  End Module ' QueueTest 

[View full width]
 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:\examples\ch25\Fig25_17\QueueTest.cs :line 38 

The implementation of each QueueInheritance method calls the appropriate List methodmethod Enqueue calls InsertAtBack (line 14), and method Dequeue calls RemoveFromFront (line 20). 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. 24.4); thus, the class library for QueueInheritance must have a reference to the LinkedListLibrary class library.

Class QueueInheritanceTest's Main method (Fig. 24.17) creates a QueueInheritance object called queue (line 9). Lines 12-15 define four values that will be enqueued and dequeued. The program enqueues (lines 18, 20, 22 and 24) a Boolean containing true, a Char containing '$', an Integer 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 32-36) 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. 24.4) and namespace QueueInheritanceLibrary (Fig. 24.16); thus, the solution for class QueueInheritanceTest must have references to both class libraries.