.NET 1.1+

The Queue Collection

by Richard Carr, published at http://www.blackwasp.co.uk/Queue.aspx

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, a queue is a data structure that permits the storage of items for later extraction. When items are retrieved from a 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 queue 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 demand is high. When integrating disparate systems it may be essential that updates are processed in order to avoid data integrity problems. For example, it may be invalid to attempt to process sales order lines before the sales order header is generated.

The Queue Collection

The .NET framework includes the Queue collection type. This class provides 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 object, including duplicate items and null values.

Implemented Collection Interfaces

The Queue collection implements the ICollection interface. This behaviour is described in the earlier Collection Interfaces article. The rest of this article describes the additional functionality of Queue.

Declaring a Queue

Constructors

The Queue class has four constructors for instantiating new collections. The first is the most basic, having 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 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.

Queue myFifo = new Queue();

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 required capacity during instantiation. 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, pass the capacity to the constructor as an integer parameter.

Queue myFifo = new Queue(25);

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. It is possible to adjust this multiplier when instantiating a Queue by passing a second, float parameter containing a growth factor between one and ten. On exceeding capacity, the current size is multiplied by this value.

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

Queue myFifo = new Queue(10, 1.5F);

The final constructor permits the creation of a pre-populated queue. If you 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 source 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

Queue structures allow new items to be added to the end of the queue and existing 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 has a single parameter containing the object to add to the queue.

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

You can extract items from a queue with the Dequeue method. This returns the item that appears at the front of the queue as an object, which you may 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 extracted from a queue. Note that the order of extraction matches the 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

*/