C# 3.0 Cookbook, 3rd Edition

4.4. Replacing the Stack and Queue with Their Generic Counterparts

Problem

You want to enhance the performance of your application as well as make the code easier to work with by replacing all Stack and Queue objects with their generic versions. This is imperative when you find that structures or other value types are being stored in these data structures, resulting in boxing/unboxing operations.

Solution

Replace all occurrences of the System.Collections.Stack and System.Collection.Queue objects with the System.Collections.Generic.Stack and System.Collection.Generic.Queue objects.

Here is a simple example of using a System.Collections.Queue object:

	public static void UseNonGenericQueue()
	{

	    // Create a non-generic Queue object.
	    Queue numericQueue = new Queue();

	    // Populate Queue (causing a boxing operation to occur). 
	    numericQueue.Enqueue(1); 
	    numericQueue.Enqueue(2); 
	    numericQueue.Enqueue(3);

	    // De-populate Queue and display items (causing an unboxing operation to
occur)

	    Console.WriteLine(numericQueue.Dequeue());
	    Console.WriteLine(numericQueue.Dequeue());        
	    Console.WriteLine(numericQueue.Dequeue().ToString()); 
	}

Here is that same code using a System.Collections.Generic.Queue object:

	public static void UseGenericQueue()
	{ 
	    // Create a generic Queue object.        
	    Queue<int> numericQueue = new Queue<int>();

	    // Populate Queue. 
	    numericQueue.Enqueue(1);
	    numericQueue.Enqueue(2);
	    numericQueue.Enqueue(3);

	    // De-populate Queue and display items.
	    Console.WriteLine(numericQueue.Dequeue());
	    Console.WriteLine(numericQueue.Dequeue());
	    Console.WriteLine(numericQueue.Dequeue());
	}

Here is a simple example of using a System.Collections.Stack object:

	public static void UseNonGenericStack()
	{ 
	    // Create a non-generic Stack object.
	    Stack numericStack = new Stack();

	    // Populate Stack (causing a boxing operation to occur). 
	    numericStack.Push(1);
	    numericStack.Push(2);
	    numericStack.Push(3);

	    // De-populate Stack and display items (causing an unboxing operation to
occur).
	    Console.WriteLine(numericStack.Pop().ToString());
	    Console.WriteLine(numericStack.Pop().ToString());
	    Console.WriteLine(numericStack.Pop().ToString());
	}

Here is that same code using a System.Collections.Generic.Stack object:

	public static void UseGenericStack()
	{ 

	    // Create a generic Stack object.        
	    Stack<int> numericStack = new Stack<int>();

	    // Populate Stack.
	    numericStack.Push(1);
	    numericStack.Push(2);
	    numericStack.Push(3);

	    // De-populate Stack and display items.
	    Console.WriteLine(numericStack.Pop().ToString());
	    Console.WriteLine(numericStack.Pop().ToString());
	    Console.WriteLine(numericStack.Pop().ToString());
	}

Discussion

On the surface, the generic and nongeneric Queue and Stack classes seem similar enough. However, it is a very different story underneath the surface. The basic use of the generic Queue and Stack objects are the same as with their nongeneric counter-parts, except for the syntax used to instantiate the objects. The generic form requires a type argument in order to create the type. The type argument in this example is an int. This type argument indicates that this Queue or Stack object will be able to contain only integer types, as well as any type that implicitly converts to an integer, such as a short:

	short s = 300; 
	numericQueue.Enqueue(s);     // OK, because of the implicit conversion

However, a type that cannot be implicitly converted to an integer, such as a double, will cause a compile-time error:

	double d = 300; 
	numericQueue.Enqueue(d);         // Error, no implicit conversion available 
	numericQueue.Enqueue((int)d);    // OK, because of the explicit cast

The nongeneric form does not require this type argument, because the nongeneric Queue and Stack objects are allowed to contain any item as an element because all items are convertible to type Object.

When choosing between a generic and nongeneric Queue or Stack, you need to decide whether you wish to use a generic Queue or Stack object or a nongeneric Queue or Stack object. Choosing the generic Queue or Stack class over its nongeneric form gives you many benefits, including:

Type-safety

Each element contained in the data structure is typed to one specific type. This means no more casting of objects when they are added to or removed from the data structure. You cannot store multiple disparate types within a single data structure; you always know what type is stored within the data structure. Type checking is done at compile time rather than runtime. This boils down to writing less code, achieving better performance, and making fewer errors.

Shortened development time

To make a type-safe data structure without using generics means having to sub-class the System.Collections.Queue or System.Collections.Stack class in order to create your own. This is time-consuming and error-prone.

Performance

The generic Queue or Stack does not require a cast that could fail to occur when adding and removing elements from it. In addition, no boxing operation occurs when adding a value type to the Queue or Stack. Likewise, in almost all cases, no unboxing operation occurs when removing a value type from the Queue or Stack.

Easier-to-read code

Your code base will be much smaller because you will not have to subclass the nongeneric Queue or Stack class to create your own strongly typed class. In addition, the type-safety features of generic code will allow you to better understand what the purpose of the Queue or Stack class is in your code.

The following class members are implemented in the nongeneric Queue and Stack classes but not in their generic counterparts:

	Clone method
	IsSynchronized property
	SyncRoot property
	Synchronized method

The addition of the Clone method on the nongeneric Queue and Stack classes is due to the ICloneable interface being implemented only on the nongeneric Queue and Stack classes. However, all other interfaces implemented by the generic and nongeneric Queue and Stack classes are identical.

One way around the missing Clone method in the generic Queue and Stack classes is to use the constructor that accepts an IEnumerable<T> type. Since this is one of the interfaces that the Queue and Stack classes implement, it is easy to write. For the Queue object, the code is as follows:

	public static void CloneQueue()
	{
	    // Create a generic Queue object.
	    Queue<int> numericQueue = new Queue<int>();

	    // Populate Queue. 
	    numericQueue.Enqueue(1); 
	    numericQueue.Enqueue(2); 
	    numericQueue.Enqueue(3);

	    // Create a clone of the numericQueue. 
	    Queue<int> clonedNumericQueue = new Queue<int>(numericQueue);

	    // This does a simple peek at the values, not a dequeue. 
	    foreach (int i in clonedNumericQueue) 
	    {
	        Console.WriteLine("foreach: " + i.ToString());
	    }

	    // De-populate Queue and display items.       
	    Console.WriteLine(clonedNumericQueue.Dequeue().ToString());
	    Console.WriteLine(clonedNumericQueue.Dequeue().ToString());
	    Console.WriteLine(clonedNumericQueue.Dequeue().ToString());
	}

The output for this method is shown here:

	foreach: 1 
	foreach: 2 
	foreach: 3 
	1
	2
	3

For the Stack object, the code is as follows:

	public static void CloneStack()
	{

	    // Create a generic Stack object.
	    Stack<int> numericStack = new Stack<int>();

	    // Populate Stack. 
	    numericStack.Push(1); 
	    numericStack.Push(2); 
	    numericStack.Push(3);

	    // Clone the numericStack object. 
	    Stack<int> clonedNumericStack = new Stack<int>(numericStack);

	    // This does a simple peek at the values, not a pop. 
	    foreach (int i in clonedNumericStack) 
	    {
	        Console.WriteLine("foreach: " + i.ToString()); 
	    }

	    // De-populate Stack and display items.        
	    Console.WriteLine(clonedNumericStack.Pop().ToString());
	    Console.WriteLine(clonedNumericStack.Pop().ToString());
	    Console.WriteLine(clonedNumericStack.Pop().ToString());
	}

The output for this method is shown here:

	foreach: 1 
	foreach: 2 
	foreach: 3 
	1 
	2 
	3

This constructor creates a new instance of the Queue or Stack class containing the elements copied from the IEnumerable<T> type.

See Also

The "System.Collections.Stack Class," "System.Collections.Generic.Stack Class," "System.Collections.Queue Class," and "System.Collections.Generic.Queue Class" topics in the MSDN documentation.