.NET 1.1

The Queue Collection

The fortieth part of the C# Fundamentals tutorial describes the use of the Queue class. This collection includes the functionality required in a 'First In, First Out' (FIFO) queuing structure. Queues allow items to be held in order for later processing.

What is a Queue?

In computer science terms, a queue is a data structure that permits the storage of items for later extraction. When items are retrieved from the queue, they are accessed in the order in which they were originally added. This leads to the term First In, First Out or FIFO.

Queues have many uses in software development. The nature of the data structure allows it to be utilised for situations where messages or information must be processed in the order in which they were received whilst allowing the processing to be delayed when the demand is high. When creating integrations between disparate systems it can be essential that data updates are processed in the correct order to avoid data integrity problems. For example, it may be invalid to attempt to process a number of sales order lines before the sales order header is dealt with.

The Queue Collection

The .NET framework includes the Queue collection type. This class provides all of the functionality required to operate FIFO queues with no additional programming. The Queue class provides a very simple type of collection that can contain any type of object, including duplicate items and null values.

Implemented Collection Interfaces

The Queue collection implements the properties and methods of the ICollection interface. This behaviour is described in the earlier Collection Interfaces article. The rest of this article describes only the additional functionality provided by Queue.

Declaring a Queue

Constructors

The Queue class provides four constructors for instantiating a new collection. The first constructor is the most basic, requiring no parameters. The new, empty queue is generated with the capacity to store up to thirty-two items. Should a thirty-third item be added, the capacity of the queue is doubled automatically. It doubles again each time the capacity of the Queue is exceeded.

The Queue class is found in the System.Collections namespace so to execute the examples, add using System.Collections; to the source code.

If the maximum number of items that will be stored in a Queue is known before the collection is created, it is more efficient to declare the capacity required when the object is created. If the size is underestimated and the stated capacity is exceeded, the capacity will still be doubled to accommodate extra items. To declare the initial capacity of a Queue, the capacity is passed to the constructor as an integer parameter.

By default, each time the capacity of a Queue is exceeded, the queue capacity doubles. This doubling occurs because the standard queue growth factor is 2. However, it is possible to adjust the growth factor when instantiating the queue. This is achieved by passing a second, float parameter containing a growth factor between one and ten. On exceeding capacity, the current size is then multiplied by the growth factor.

The following example creates a new queue with an initial capacity of ten items and a growth factor of 1.5.

The final constructor permits the creation of a pre-populated queue. If you already have a collection of items in a class that implements the ICollection interface, this can be used as the source data for the new queue. Each item in the collection is added to the queue in the order that the collection would normally be enumerated.

ArrayList myList = new ArrayList();
myList.Add("String 1");
myList.Add("String 2");

Queue myFifo = new Queue(myList);               // Copies myList into the queue

Using Queue Functions

Enqueue Method

The purpose of a queue structure is to allow new items to be added to the end of the queue and for existing queue items to be extracted from the front. To add a new item to the end of the queue, the Enqueue method is called. The method requires only a single parameter containing the object to be added to the queue. The object may be of any data type. For simplicity in the following examples, strings will be used.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

Console.WriteLine("Count: {0}", waiting.Count);     // Outputs "Count: 3"

Dequeue Method

To extract items from a queue, the Dequeue method is used. Dequeue returns the item that appears at the front of the queue, boxed within an object. To extract the item into a variable, the object should be cast to the correct type. In the following example, the ToString method is used to perform the conversion as three items are added to and then removed from a queue. Not that the order of extraction matches the original order in which the items were added.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

while (waiting.Count != 0)
{
    string next = waiting.Dequeue().ToString();
    Console.WriteLine(next);
}

/* OUTPUT

Mrs Brown
Mr Green
Miss Black

*/

Peek Method

Often it is useful to know the contents of the item at the front of the queue without modifying the collection's contents. The Peek method is used in the same manner as Dequeue but when the next item is retrieved, it is also left at the front of the queue.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

string next = waiting.Peek().ToString();
Console.WriteLine(next);                            // Outputs "Mrs Brown"
Console.WriteLine("Count: {0}", waiting.Count);     // Outputs "Count: 3"

Other Queue Processing Methods

In addition to the FIFO queue processing methods, the Queue class provides some other functionality for modifying and reading the collection. These enhance the data structure with behaviours similar to those found in some other collection and list types.

Clear

The Clear method is used to empty the contents of a queue. The method requires no parameters.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

Console.WriteLine("Count: {0}", waiting.Count);     // Outputs "Count: 3"
waiting.Clear();
Console.WriteLine("Count: {0}", waiting.Count);     // Outputs "Count: 0"

TrimToSize

As the number of items in a queue collection increases, the size of the queue can also increase. Using standard settings, each time the collection capacity is exceeded it is doubled. However, as the queue empties, its capacity is not automatically lowered. This can lead to a large amount of wasted memory for larger queues. To reduce this, the queue can be trimmed in order to free up the system memory wasted by empty space. The TrimToSize method is called to set the size of the queue to match its current contents.

As the Queue class does not include a property that returns the current capacity, it is difficult to show the effect of executing the TrimToSize method. However, the method can be used as shown in the following example:

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

waiting.TrimToSize();                               // Resize the queue

Contains

Sometimes you will need to determine if a specified item exists within a queue but you will not want to dequeue every item in order to find it. The Contains method can solve this problem by returning a Boolean value indicating if the provided object is already in the queue. The method is similar to the Contains method provided by the IList interface.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

Console.WriteLine(waiting.Contains("Mrs Brown"));   // Outputs "True"
Console.WriteLine(waiting.Contains("Mrs White"));   // Outputs "False"

ToArray

A further method exists that permits a queue's contents to be read without disturbing the order of the items. In a similar manner to with an ArrayList, the objects in the queue can be extracted into an array. The resultant array has each item boxed in an object that can be cast back to the original type. The queue is unaffected.

Queue waiting = new Queue();

waiting.Enqueue("Mrs Brown");
waiting.Enqueue("Mr Green");
waiting.Enqueue("Miss Black");

// Copy items
object[] array = waiting.ToArray();

// List array items
foreach (object o in array)
    Console.WriteLine(o.ToString());

/* OUTPUT

Mrs Brown
Mr Green
Miss Black

*/

Creating a Thread-Safe Queue Wrapper

In the earlier article discussing collection interfaces, the concept of a thread-safe synchronised collection was described. In order to create a thread-safe Queue, a synchronised wrapper collection is generated using the static Synchronized method.

Queue myCollection = new Queue();

Queue myThreadSafe = Queue.Synchronized(myCollection);

Console.WriteLine(myThreadSafe.IsSynchronized);	        // Outputs "True"