4.7 Using Stacks and Queues

You want to use a data structure that orders items based on when they are added to the collection.

Technique

If you want to use a last-in-first-out structure (LIFO) in which the last item in the collection is the first item that is removed, then use a stack. To add an object to a stack, use the Push method defined in the System.Collections.Stack class. To remove an item from the stack, use the Pop method. This object is the same object that was added with the last Push method call.

A queue is similar to a stack, but it uses a first-in-first-out (FIFO) method. The first element removed from the queue was the first element initially added to the collection. To add an object to a queue, use the Enqueue method defined in the System.Collection.Queue class. Likewise, to remove an object from the queue, use the Dequeue method.

Comments

The previous recipes in this chapter looked at arrays and ArrayList s, which allowed you to randomly access any element within the array using an indexer. These data structure act as simple collections without any type of data-organizing structure to them. Stack and queues, on the other hand, don't allow indexers to randomly access the elements in the collection but rather use methods that allow you to add or remove elements from the beginning or end of the collection.

As mentioned earlier, a stack is a LIFO data structure. To use a metaphor for visualization purposes, imagine stacking blocks on top of each other. Each time you add a block to the top, you are doing the equivalent of the System.Collections.Stack 's Push method. When it's time to remove the blocks one at a time, it makes sense to remove them from the top working your way to the bottom because removal of the bottom block isn't possible without breaking the structure. Removing the top or last block that was added to the structure is the equivalent of the stack method Pop , as demonstrated in Figure 4.2.

Figure 4.2. A stack uses a last-in-first-out (LIFO) methodology.

Listing 4.8 shows a simple application that uses a stack. The Main method asks the user to enter a list of names separated by a space. These names are placed within a simple string array, and that array is then passed to the TestStack method. This method then enumerates through the string array and pushes each string onto the stack, visually displaying the progress, as shown in Figure 4.2. Finally, the user is prompted to enter an integer value specifying how many objects to pop off the stack. Again, as the items are removed, the application shows the contents of the stack.

Listing 4.1 Pushing and Popping Objects from a Stack

 using System; using System.Collections; namespace _6_StacksQueues {     class Class1     {         [STAThread]         static void Main(string[] args)         {             string input;             Console.Write( "Enter a list of names separated by a space: " );             input = Console.ReadLine();             // place names into a string array             string[] names = input.Split( ' ' );             // print out string array             PrintCollection( "Input", names );             TestStack( names );         }         static void PrintCollection( string name, ICollection coll )         {             Console.Write( name + ": " );             foreach( object elem in coll )             {                 Console.Write( elem.ToString() + ' ' );             }             Console.WriteLine("\n");         }         static void TestStack( string[] names )         {             Stack nameStack = new Stack();             // enumerate through the array             foreach( string name in names )             {                 // push name onto stack and display new stack contents                 nameStack.Push( name );                 Console.WriteLine( "Pushed value: {0}", name );                 PrintCollection( "New Stack", nameStack );             }             // let user choose how many items to remove             Console.Write( "Pop how many items? " );             int pops = Int32.Parse( Console.ReadLine() );             for( int i = 1; i <= pops; i++ )             {                 // Pop value. Note that Pop also                 // returns the value that was removed                 Console.WriteLine( "Popped value: " + nameStack.Pop());                 // display the new stack contents                 PrintCollection( "Stack after " + i.ToString() + " pops",                     nameStack );             }             Console.WriteLine();         }     } } 

A queue is quite similar to a stack, which is the reason they are both mentioned in this recipe. As with the stack, you cannot randomly access or remove items using an indexer into the queue. The equivalent of a stack's Push method is called Enqueue . However, rather than add that the object to the beginning of the list as a stack does, the queue adds the item at the end of the list. This process ensures that the first item added to the queue is at the beginning of the collection, which results in it also being the first item removed when you call the Dequeue method. To visualize a queue, you can use the classic example of a line of people waiting for an attraction. The first person who entered the line will be the first person who gets into the attraction.

Figure 4.4. Queues work on the notion of first-in-first-out (FIFO) when adding and removing objects.

Listing 4.2 expands on the application presented in Listing 4.1. It adds a new method called TestQueue , which is quite similar to the TestStack method. What is different is the output that you see in Figure 4.5. If you compare this figure with Figure 4.3, you can see how the LIFO and FIFO data structures compare.

Listing 4.2 Using Enqueue and Dequeue Instead of Push and Pop

 static void TestQueue( string[] names ) {     Queue nameQueue = new Queue();     foreach( string name in names )     {         nameQueue.Enqueue( name );         Console.WriteLine( "Enqueued value: {0}", name );         PrintCollection( "New Queue", nameQueue );     }     Console.Write( "Dequeue how many items? " );     int dequeues = Int32.Parse( Console.ReadLine() );     for( int i = 1; i <= dequeues; i++ )     {         Console.WriteLine( "Dequeued value: " + nameQueue.Dequeue());         PrintCollection( "Queue after ", nameQueue );     } } 

Figure 4.5. The objects in a queue that were added first are also the first to be removed.

Figure 4.3. The objects on a stack that were added last are the first to be removed.