1. Technology

How to use Stack<T> in C#

Using the HashSet<T> class

By

Stack of plates from Wikimedia

In the previous tutorial, we looked at using Sets and HashSets and in this one is about stacks, specifically Stack<T> in C#.

Normally when you think of a stack, it's the place where local variables are held in methods in C#. Also return address and method para,eters are stored there as well.

However a Stack is a valid data structure and there are two C# Stack Collection classes; the original Stack class in System.Collections and the Systems.Collections.Generic Stack<T> generic collection class.

Generics are generally better because they are type safe. If you create a stack to hold ints, the compiler won't allow it to hold any other type. Speed is possibly better as well as type conversion isn't needed.

As a general rule, try to use the generic collection classes in preference to the non generics. So for the rest of the tutorial when I refer to Stack class, I mean Stack<T>.

If you aren't familiar with this Stack<T> notation, it means that the Stack can handle any Type of object (i.e. it's generic) be it int, String or another class.

What is a Stack?

Here's my version of Computing 101. A stack a LIFO (Last In First Out) data structure described as being like a stack of plates in a cafeteria. The plate stack has a spring pushing up the base and the weight of the plates on the base pushes it down so the top most plate is always at the same level. When loading it with plates, the plates are pushed onto the stack and then popped off as needed.

The key to a stack is that plates are added to the top and also popped off the top. Add a red plate then a blue plate and a white plate in that order and the white plate is top. You remove them starting with the white plate first then the blue and finally the red plate.

The Stack class works in the same way. You define a stack of some type and then can push values on to it with the Push(Value) method. When you want to remove them, you use Pop() to return the values.

In the example below with a Stack, three values are pushed: 5,9 and 4. They are then popped in reverse order 4,9,5.

using System;
using System.Collections.Generic;

namespace exStack
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var stack = new Stack<int>() ;
            stack.Push(5) ;
            stack.Push(9) ;
            stack.Push(4) ;
            while (stack.Count > 0)
                {
                    Console.WriteLine(stack.Pop()) ;
                };
            Console.ReadKey() ;
        }
    }
}

Note the use of stack.Count to make sure we don't pop off too many values.

Being that Stack<int> has an enumerator, it's possible to use LINQ to process the elements in the stack. Adding this line just before the while (stack.Count) will output 18, the sum of the three elements currently in the stack.

Console.WriteLine(stack.Sum());

You'll need to add using System.Linq; to the top of the program to make that work.

Let's Take a Peek

Another method that Stack<T&hgt; provides is Peek() which let's you examine the value at the top of the stack without removing it.

Using a Stack

There aren't that many algorithms that I can think of that might use a stack. One that springs to mind is evaluating an expression, where the factors of the expression are pushed onto a stack.

Say the expression is y = ((c*d) + (a + b)) and we want to check the expression is correct, i.e the brackets are balanced and if so then evaluate it.

Push the first bracket on the stack, then the second. Then a factor c, an operator *, another factor d and a right bracket. The code is looking for a right bracket and once it finds it, it pops off everything from the right bracket back to the previous left and evaluates it.. and so on.

Another use might be in a brute force maze solving algorithm, assuming the maze has no loops in it. As you advance through the maze, push each location in the path on to the stack, including junctions, after marking which path is taken at the junction. If the path turns out to be a dead end, back track to the junction by repeatedly popping off the previous paths from the stack until you get back to the junction and then take an unused path.

That completes this tutorial.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. C# / C Sharp
  5. Learn C Sharp
  6. Using The Stack Collection Class in C#

©2014 About.com. All rights reserved.