The Stack data structure has many applications in programming. In this post, you will see three examples of using the Stack data structure in C# to solve real-life problems.
Stacks in the real world
Programming is about modelling real-life situations. The use of stacks is not the exception.
The Tower of Hanoi is a game “consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:
- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
- No disk may be placed on top of a disk that is smaller than it.
“. Source Wikipedia.
The rules of the game state that you can only move one disk at a time, and it must be the disc on top of any of the three rods.
That behaviour, of removing only the element at the top each time, and adding a new element only to the top, is known as a stack in Computer Science. Also known as the Last In, First Out (LIFO) principle.
Notice that if you remove more than one disc at a time (something you can do) while playing the game, you will be breaking the rules.
Let’s now see the basic operations of the Stack Abstract Data Type (ADT).
The Stack Abstract Data Type
Find below the basic operations of the Stack ADT and an explanation.
- Push: adds an element to the top of the stack
- Pop: retrieve and removes the element at the top
- Top: retrieve the element at the top without removing it
- isEmpty: return true if the stack is empty, otherwise it returns false.
In different programming languages, you can find extra operations and different names for the operations above. But you will always find an operation that will do the action of each of the four operations mentioned above.
Here is one implementation of the stack ADT in C# that you can use to practice.
Stack data structure examples
One example is to find the solution to the Tower of Hanoi problem given the number of disks. However, this solution is difficult to understand at a beginner level. So, I’ll show you examples that are easier to understand, so later you can solve the Tower of Hanoi problem on your own.
Example 1: Invert an array of integers
Let’s create a method that takes an array as input and return the inverted array.
We can use a stack to solve the previous problem. Notice that in a stack, the last in is the first out (LIFO principle). So, if we add all the array elements to a stack, when we take them out, they will be in reverse order.
Let’s see the implementation.
public static int[] InvertArrray(int[] arr)
{
Stack<int> stack = new Stack<int>();
for (int i = 0; i < arr.Length; i++)
{
stack.push(arr[i]);
}
int index = 0;
while (!stack.isEmpty())
{
arr[index] = stack.pop();
index++;
}
return arr;
}
All we did in the previous code was to add the elements of the array to the stack and remove the elements from the stack and add them to the array. That’s it! now the array is inverted.
Notice that the way we go through the elements of a stack is by using a while loop. The loop will be executed while the stack is not empty. So, inside the loop we need to remove (stack.pop()) the elements of the stack otherwise we will have an infinite loop. Not a good thing to have, at least in this example.
To avoid repeating code, we can implement a method to print an array. This is how we are going to visually test if the code inverted the array.
public static void PrintArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + ", ");
}
Console.WriteLine();
}
The main method of the console application can look like this:
static void Main(string[] args)
{
int[] array = new int[] { 1, 2, 3, 4, 5 };
PrintArray(array);
InvertArrray(array);
PrintArray(array);
}
Remember that if you are using .NET 6 or higher, the console application does not need to have a class definition or the “static void Main…” method definition. You can just write the code and the compiler will take care of creating the class and method Main.
Example 2: Implement a method that returns how many times a given integer value appears in a stack of integers.
We don’t have access to the internal structure of the stack. This is one of the principles of OOP.
So, we can only use the 4 methods of the ADT: push, pop, top and isEmpty.
We need to use an auxiliary stack to store the elements as we remove them from the original stack. We do that to put the stack in its initial state. We can do modifications to the stack while we are calculating what we need (how many times an element is in the stack in this case), but when we calculate the results and return a value, we must ensure that the stack is in its original state.
So, let’s see the code.
public static int HowManyTimes(int x, Stack<int> stack)
{
int c = 0;
Stack<int> aux = new Stack<int>();
while (!stack.isEmpty())
{
if (stack.top() == x) {
c++;
}
aux.push(stack.pop());
}
//Put back all the elements to the original stack
while (!aux.isEmpty())
{
stack.push(aux.pop());
}
return c;
}
This pattern of using an auxiliary stack to store the values of the original stack, so later we can return the original stack to its initial state, is applicable in most cases.
Apart from that pattern, it also follows the basic algorithm for counting pattern.
A console app to try out the code above can be as follows:
Stack<int> stack = new Stack<int>();
stack.push(1);
stack.push(5);
stack.push(3);
stack.push(5);
int c = HowManyTimes(5, stack);
Console.WriteLine("The number 5 appear {0} times in the stack", c);
If you execute the previous code, you will get the following output.
Example 3: Implement a method that returns the average of the integer elements in a certain stack.
The solution to this problem will have the same structure as the previous one. Here, instead of counting how many times a specific element is in the stack, we must add all the elements together. We also need to count the total of elements on the stack, so that later we can calculate the average.
See the code below.
public static float Average(Stack<int> stack)
{
float total = 0;
int c = 0;
Stack<int> aux = new Stack<int>();
while (!stack.isEmpty())
{
total += stack.top();
c++;
aux.push(stack.pop());
}
//Put back all the elements to the original stack
while (!aux.isEmpty())
{
stack.push(aux.pop());
}
return total/c;
}
Did you see the pattern I mentioned in the previous example? Using an auxiliary stack so you can have the original stack in its initial state.
Also, this algorithm follows the pattern of the basic algorithm for summing. Because we must add all the elements, we don’t need a condition to sum. And in the end, we need to divide by the total so we can return the average.
See the importance of the basic algorithms? They are the basis of many different algorithms.
You can try the code with the following C# console application.
Stack<int> stack = new Stack<int>();
stack.push(1);
stack.push(5);
stack.push(3);
stack.push(5);
Console.WriteLine("The average is: {0}", Average(stack));
Summary
The Stack data structure follows the LIFO principle. It means that the last element to go into the stack is the first one to go out.
Many problems can be solved using stacks. However, in all cases, you won’t see the word stack as part of the problem description. As you saw in the previous example of inverting an array.
The key to knowing when to use stacks is to think about the process you can follow to give the solution to the problem. If it follows the LIFO principle, then you can use stacks.
Some programming languages implement extra operations in the Stack data structure. As a word of caution, if you have to use more operations than the basic ones, you should evaluate if stacks are the right data structure to use in the solution to that particular problem.
H@ppy coding!
Related posts:
