You have elements that you need to process in a first-in, first-out order. This means you act on the events that you received longest ago first. Here we look at several examples of using Queue(T), and also think about some of the logic used for processing help requests in an application, using the C# programming language.
First-In-First-Out
The queue data structure implements this algorithm.
Queue is a generic type with one type parameter.Here we see how you can add four integral types to an instance of the Queue type in the C# language. 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.
--- 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.
}
}Here we look at how you can loop through the elements in your Queue. Very 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 of the program ===
5
6Description of code snippet. 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.
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);
}
}Overview of the example code. 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.
Notes. This system ensures that no one is left hanging infinitely, unless the entire system stops to work, which in real life happens a lot. You will need safeguards when designing a more complex and useful system.
Here we look at how you can copy Queue elements. You might have a Queue collections in your C# program but need to look at the elements in the reverse order. You can loop through the elements from the last to the first by using CopyTo and looping.
--- Program that copies Queue (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);
q.Enqueue(10);
q.Enqueue(15);
q.Enqueue(20);
// Create new array with Length equal to Queue's element count.
int[] arr = new int[q.Count];
// Copy the Queue to the int array.
q.CopyTo(arr, 0);
// Loop through and display int[] in order
for (int i = 0; i < arr.Length; i++)
{
Console.WriteLine(arr[i]);
}
// Loop through int array in reverse order
for (int i = arr.Length - 1; i >= 0; i--)
{
Console.WriteLine(arr[i]);
}
}
}
--- Output of the program ---
(The two loops output the data twice.)
5
10
15
20
5
10
15
20Description of the code. The example shows CopyTo and its usage 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 you the most power over iterating over the arrays. First, the array is written to the Console in front to back order, and then it is written in the opposite direction.
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.
Clear Use Clear to remove all elements from your generic Queue collection. 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 performs a linear search; therefore, this method is an O(n) operation, where n is Count." [MSDN source] CopyTo MSDN states this "copies the Queue(T) elements to an existing one-dimensional Array." This also iterates through each element. Dequeue Removes the object at the BEGINNING of your Queue. The algorithmic complexity of this is O(1), meaning it doesn't loop over the elements. Enqueue Adds the parameter object to the END of the Queue. This will be the most distant object from the one you can access with Peek. Peek MSDN: "Returns the object at the beginning of the Queue(T) without removing it." This means you only LOOK at the object. Use Dequeue to remove that object. [See above] 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 contains internal logic to avoid doing anything if the Queue is > 90% full. Count Count is a useful property that returns the number of elements in your Queue in an O(1) operation, meaning it requires constant time and doesn't enumerate the elements. This is not the Count() extension method.
Here we look at some final characteristics of the Queue collection. The author has not found the collection useful in very many programs. He has usually chosen the List collection or array for optimal performance. Queue can be used for more elegant code than makeshift solutions.
Efficiency. The performance characteristics 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.
Here 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, but for when performance is critical, using List and appending to the end will have a simpler allocation and insertion strategy.