Queue
A queue is a collection where elements are processed first in, first out (FIFO). The item that is put first in the queue is read first. Examples of queues are standing in the queue at the airport, a human resources queue to process employee applicants, print jobs waiting to be processed in a print queue, and a thread waiting for the CPU in a round-robin fashion. Often, there are queues where the elements processed differ in there priority. For example, in the queue at the airport business passengers are processed before economy passengers. Here, multiple queues can be used, one queue for every priority. At the airport this can easily be found out, as there are separate check-in queues for business and economy passengers. The same is true for print queues and threads. You can have an array of a list of queues where one item in the array stands for a priority. Within every array item there’s a queue, where processing happens with the FIFO principle.
| Tip | Later in this chapter, a different implementation with a linked list is used to define a list of priorities. |
With .NET you have the nongeneric class Queue in the System.Collections namespace and the generic class Queue<T> in the System.Collections.Generic namespace. Both classes are very similar in their functionality with the exception that the generic class is strongly typed, defining type T, and the nongeneric class is based on the object type.
Internally, the Queue<T> class is using an array of type T similar to the List<T> type. What’s also similar is that the interfaces ICollection and IEnumerable are implemented. The Queue class implements the interfaces ICollection, IEnumerable and ICloneable. The Queue<T> class implements the interfaces IEnumerable<T> and ICollection. The generic class Queue<T> does not implement the generic interface ICollection<T> because this interface defines methods to add and remove items to the collection with Add() and Remove() methods.
The big difference of the queue is that the interface IList is not implemented. You cannot access the queue using an indexer. The queue just allows you to add an item to the queue, where the item is put at the end of the queue (with the Enqueue() method), and to get items from the head of the queue (with the Dequeue() method).
Figure 10-1 shows the items of the queue. The Enqueue() method adds items to one end of the queue; the items are read and removed at the other end of the queue with the Dequeue() method. Reading items with the Dequeue() method also removes the items from the queue. Invoking the Dequeue() method once more removes the next item from the queue.
Figure 10-1
Methods of the Queue and Queue<T> classes are described in the following table.
| Queue and Queue<T> Members | Description |
|---|---|
| Enqueue() | The Enqueue() method adds an item to the end of the queue. |
| Dequeue() | The Dequeue() method reads and removes an item from the head of the queue. If there are no more items in the queue when the Dequeue() method is invoked, an exception of type InvalidOperationException is thrown. |
| Peek() | The Peek() method reads an item from the head of the queue but does not remove the item. |
| Count | The property Count returns the number of items in the queue. |
| TrimExcess() | TrimExcess() resizes the capacity of the queue. The Dequeue() method removes items from the queue, but it doesn’t resize the capacity of the queue. To get rid of the empty items at the begin of the queue use the TrimExcess() method. |
| Contains() | The Contains() method checks whether an item is in the queue and returns true if it is. |
| CopyTo() ToArray() | With the CopyTo() method, you can copy the items from the queue to an existing array. The method ToArray() returns a new array containing the elements of the queue. |
Open table as spreadsheet When creating queues, you can use constructors similar to those used with the List<T> type. The default constructor creates an empty queue, but you can also use a constructor to specify the capacity. As items are added to the queue, the capacity is increased to hold 4, 8, 16, and 32 items. Similarly to the List<T> class, the capacity is always doubled as required. The default constructor of the nongeneric Queue class is different, as it creates an initial array of 32 empty items. With an overload of the constructor you can also pass any other collection that implements the IEnumerable<T> interface that is copied to the queue.
The sample application that demonstrates the use of the Queue<T> class is a document management application. One thread is used to add documents to the queue, and another thread reads documents from the queue and processes them.
The items stored in the queue are of type Document. The Document class defines a title and content:
public class Document { private string title; public string Title { get { return title; } } private string content; public string Content { get { return content; } } public Document(string title, string content) { this.title = title; this.content = content; } } The DocumentManager class is a thin layer around the Queue<T> class. The class DocumentManager defines how to handle documents: adding documents to the queue with the AddDocument() method, and getting documents from the queue with the GetDocument() method.
Inside the AddDocument() method, the document is added to the end of the queue by using the Enqueue() method. The first document from the queue is read with the Dequeue() method inside GetDocument(). Because multiple threads can access the DocumentManager concurrently, access to the queue is locked with the lock statement.
| Tip | Threading and the lock statement are discussed in Chapter 18, “Threading and Synchronization.” |
IsDocumentAvailable is a read-only Boolean property that returns true if there are documents in the queue, and false if not:
public class DocumentManager { private readonly Queue<Document> documentQueue = new Queue<Document>(); public void AddDocument(Document doc) { lock (this) { documentQueue.Enqueue(doc); } } public Document GetDocument() { Document doc = null; lock (this) { doc = documentQueue.Dequeue(); } return doc; } public bool IsDocumentAvailable { get { return documentQueue.Count > 0; } } } The class ProcessDocuments processes documents from the queue in a separate thread. The only method that can be accessed from the outside is Start(). In the Start() method a new thread is instantiated. A ProcessDocuments object is created for starting the thread, and the Run() method is defined as the start method of the thread. ThreadStart is a delegate that references the method to be started by the thread. After creating the Thread object, the thread is started by calling the method Thread.Start().
With the Run() method of the ProcessDocuments class an endless loop is defined. Within this loop, the property IsDocumentAvailable is used to see if there is a document in the queue. If there is a document in the queue, the document is taken from the DocumentManager and processed. Processing here is only writing information to the console. In a real application, the document could be written to a file, written to the database, or sent across the network.
public class ProcessDocuments { public static void Start(DocumentManager dm) { new Thread(new ProcessDocuments(dm).Run).Start(); } protected ProcessDocuments(DocumentManager dm) { documentManager = dm; } private DocumentManager documentManager; protected void Run() { while (true) { if (documentManager.IsDocumentAvailable) { Document doc = documentManager.GetDocument(); Console.WriteLine("Processing document {0}", doc.Title); } Thread.Sleep(new Random().Next(20)); } } } In the Main() method of the application, a DocumentManager object is instantiated, and the document processing thread is started. Then 1000 documents are created and added to the DocumentManager.
class Program { static void Main() { DocumentManager dm = new DocumentManager(); ProcessDocuments.Start(dm); // Create documents and add them to the DocumentManager for (int i = 0; i < 1000; i++) { Document doc = new Document("Doc " + i.ToString(), "content"); dm.AddDocument(doc); Console.WriteLine("Added document {0}", doc.Title); Thread.Sleep(new Random().Next(20)); } } } When you start the application, the documents are added to and removed from the queue, and you get output similar to the following:
Added document Doc 279 Processing document Doc 236 Added document Doc 280 Processing document Doc 237 Added document Doc 281 Processing document Doc 238 Processing document Doc 239 Processing document Doc 240 Processing document Doc 241 Added document Doc 282 Processing document Doc 242 Added document Doc 283 Processing document Doc 243
A real-life scenario doing the task described with the sample application can be an application that processes documents received with a Web service.
