In the previous tutorial, we looked at using Sets and HashSets and in this one is about stacks, specifically Stack<T> in C#.
- Found this tutorial by accident? Start with the first C# tutorial.
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.
In the example below with a Stack
internal class Program
private static void Main(string args)
var stack = new Stack<int>() ;
while (stack.Count > 0)
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.
You'll need to add using System.Linq; to the top of the program to make that work.
- Want to Learn LINQ? Start with the first LINQ Tutorial
Let's Take a PeekAnother 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.
- For more things to do with C#, see How to Do Things in C#.