C# Queue

Queue collection

Queue is a FIFO collection. It processes elements in a first-in, first-out order. To restate, it handles the elements that it received longest ago first. We look at several examples of the Queue(T) generic class.

Generic Class

Enqueue

Add

First we add four ints to an instance of the Queue type. These integers could correspond to help requests from visitors to your website. We add the new requests to the end of the Queue, because they will be dealt with last.

Int

First-In-First-Out:The queue data structure implements this algorithm. Queue is a generic type with one type parameter.

Program that uses Enqueue: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// New Queue of integers
	Queue<int> q = new Queue<int>();

	q.Enqueue(5);   // Add 5 to the end of the Queue.
	q.Enqueue(10);  // Then add 10. 5 is at the start.
	q.Enqueue(15);  // Then add 15.
	q.Enqueue(20);  // Then add 20.
    }
}

Loop

Foreach loop construct

Next we loop through the elements in the Queue. Frequently you will need to loop through the elements. Fortunately, the foreach loop calls the Queue's enumerator, and you can use the standard foreach syntax.

Program that loops with Queue: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Add integers to queue.
	Queue<int> collection = new Queue<int>();
	collection.Enqueue(5);
	collection.Enqueue(6);

	// Loop through queue.
	foreach (int value in collection)
	{
	    Console.WriteLine(value);
	}
    }
}

Output

5
6
Programming tip

Behind the scenes, the foreach statement is invoking the Queue's enumerator, and lots of other stuff may be going on. The foreach syntax hides this from you, allowing you to focus on more important aspects of your code.

Foreach

Help system

Here we see some simple code that could be adapted into an advanced help request processing system. You don't want your company's visitors to end up waiting forever, and the Queue ensures this won't happen.

Queue example program: C#

using System;
using System.Collections.Generic;

class Program
{
    enum RequestType
    {
	MouseProblem,
	TextProblem,
	ScreenProblem,
	ModemProblem
    };

    static void Main()
    {
	// 1
	// Initialize help requeust Queue
	Queue<RequestType> help = new Queue<RequestType>();

	// 2
	// ASP.NET website records a Text Problem help request.
	help.Enqueue(RequestType.TextProblem);

	// 3
	// ASP.NET website records a Screen Problem help request.
	help.Enqueue(RequestType.ScreenProblem);

	// 4
	// You become available to take a new request.
	// You can't help with Mouse problems.
	if (help.Count > 0 &&
	    help.Peek() != RequestType.MouseProblem)
	{
	    // 5
	    // You solve the request. It was a TextProblem
	    help.Dequeue();
	}

	// 5
	// Other parts of your code can access the Queue, testing the elements
	// to see if they can process them.

	// 6
	// ASP.NET website records a Modem Problem help request.
	help.Enqueue(RequestType.ModemProblem);
    }
}

This example simulates a help request system where new help RequestTypes are added to the Queue. The Queue is first-in, first-out (FIFO). The newest requests are the last to be processed.

At the same time, the oldest requests, those that have been waiting the longest, are the closest to being acted on. This system ensures that no one is left hanging infinitely, unless the entire system stops to work.

Tip:Systems often stop working. You will need safeguards when designing a more complex and useful system.

Copy

Array type

Next, we look at how you can copy Queue elements. You might have a Queue collection in your C# program but need to loop over the elements in the reverse order. We call CopyTo, and then loop over the array in reverse.

For
Program that copies Queue: C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// New Queue of integers.
	Queue<int> queue = new Queue<int>();
	queue.Enqueue(5);
	queue.Enqueue(10);
	queue.Enqueue(15);
	queue.Enqueue(20);

	// Create new array with Length equal to Queue's element count.
	int[] array = new int[queue.Count];

	// Copy the Queue to the int array.
	queue.CopyTo(array, 0);

	// Loop through and display int[] in order.
	Console.WriteLine("Array:");
	for (int i = 0; i < array.Length; i++)
	{
	    Console.WriteLine(array[i]);
	}

	// Loop through int array in reverse order.
	Console.WriteLine("Array reverse order:");
	for (int i = array.Length - 1; i >= 0; i--)
	{
	    Console.WriteLine(array[i]);
	}
    }
}

Output

Array:
5
10
15
20
Array reverse order:
20
15
10
5
Int keyword

In this example, we use CopyTo with an int array. Note how we allocate the number of elements to the int[] with the same integer as the Queue's Count. We use the for loop-syntax, which gives more power when iterating over the arrays.

Int Array

Results:The array is written to the Console in front to back order, and then it is written in the opposite direction.

Console.WriteLine

Methods

Method call

Here we see an overview of the methods and properties on the Queue collection from MSDN. For every class you use in the C# programming language, you should reference MSDN and other high-quality sites.

Squares

Clear:Use Clear to remove all elements from the Queue. This can be used instead of assigning the reference to a new Queue.

Contains:You can use Contains to search through the Queue for a matching element. This method does a linear search.

Dequeue:Removes the object at the beginning of your Queue.
The algorithmic complexity of this is O(1).
It doesn't loop over elements.

Peek:MSDN: "Returns the object at the beginning of the Queue(T) without removing it." This means you only look at the object.

ToArray:Converts your Queue(T) to an array. This is similar to CopyTo, but it provides the new array reference.

TrimExcess:This is supposed to minimize the Queue(T) collection's memory usage. It avoids doing anything if the Queue is > 90% full.

Count:Returns the number of elements. It is in an O(1) operation, meaning it requires constant time and doesn't enumerate the elements.

Uses

This section provides information

Here we look at some final characteristics of the Queue collection. I have not found the collection useful in many programs. I have usually chosen the List collection or array for optimal performance.

Tip:Queue can be used for more elegant code (even self-documenting code) than makeshift solutions.

The performance of Queue, and the parallel List.Insert method, need testing before using in a critical application. My work with List Insert shows that adding elements to the wrong end of a collection can devastate performance.

Insert

Research

Note

Queues are everywhere in computer systems. Usually, the task that should be first done is the one that was first requested. Otherwise, the tasks that were started first might become angry.

FIFO queues are frequently used within computer systems to hold tasks that are yet to be accomplished when we want to provide services on a first-come, first-served basis. Sedgewick, p. 167

Summary

C# programming language

We saw ways to Enqueue and Dequeue elements and some theory code about how you could process requests on your ASP.NET website with Queue(T). This collection could be useful for certain situations.

However:For when performance is critical, using List and appending to the end will have a simpler allocation and insertion strategy.

List

C#: Collections