Introduction
In this lesson, we will see how to implement a stack in C#
Stacks are usually used when data reversal is needed or is a solution to our problems as we will see in the example at the end of
Defining a stack
we can define a stack in the same way we define any collection
here we will define a stack that takes integer numbers
1 2 3 4 5 6 7 8 9 10 |
namespace Stacks_and_queues { class Program { static void Main(string[] args) { //defining a new stack Stack<int> stack = new Stack<int>(); } } } |
Adding and viewing data in a Stack
We can add elements to our stack using the method Push()
1 2 3 |
//add elements to the stack using Push() stack.Push(1); |
and we can print the element on the top of the stack using Peek() which will return the element on the top without removing it
1 2 3 |
//Peek() will return the element at the top of the stack without removing it Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); |
Now lets add elements to our stack and every time we will print the value on top
1 2 3 4 5 6 7 8 9 |
//adding elements to the stack and printing the value on top of the stack using peek //adding elements using Push() stack.Push(1); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); stack.Push(2); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); stack.Push(3); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); |
Now let’s run the application
as we run the application we will see that every time we use the Peek() method we will get the last value we Pushed into our stack
Removing Elements from a Stack
To remove elements from our stack we will use the method Pop()
which will remove the element on top of the stack and will return it at the same time
of course, we don’t want to use Pop() on an empty stack since this will throw an error so first we need to check the Count property of the stack which will return how many elements are in our stack
1 2 3 4 5 6 7 8 |
//as long as the count is > 0, as long as the stack is not empty while (stack.Count > 0) { //Pop() will return the element that was removed from the stack Console.WriteLine("The Top value {0} was removed from the stack", stack.Pop()); //print the stack count Console.WriteLine("Current stack count is : {0}", stack.Count); } |
As we can see the elements we Popped out of the stack in the opposite way we pushed them (in reverse), this is why we consider the stack to be a LIFO last in first out, the last element that entered a stack will be the first element to exit a stack
Example Reversing an array
one of the many applications of stacks is data reversal in the following example we will use a stack to reverse an array
The solution is simple
- we will go through the elements of the array from start to end and we will push each element into a stack
2.After that we will pop and print every element in the stack until it’s empty
consider the following array of integers
1 2 3 |
//defining a new array of int with some numbers int[] numbers = new int[] { 8, 2, 3, 4, 7, 6, 2 }; |
Now let’s define a new stack that takes integer values
1 2 3 |
//defining a new stack of int Stack<int> myStack = new Stack<int>(); |
let’s print each element in the array after that we will push it into our stack using Push()
1 2 3 4 5 6 7 8 9 |
Console.WriteLine("the numbers in the array are :"); //foreach number in our array foreach (int number in numbers) { //print it Console.Write(number + " "); //push it into our stack(add) myStack.Push(number); } |
Now let’s using the Pop() method in the stack to remove each element in the stack until it’s empty and whenever we remove an element we will print it as well
1 2 3 4 5 6 7 8 9 10 11 |
//new line Console.WriteLine(""); Console.WriteLine("the numbers in reverse :"); //as long as our stack is not empty while (myStack.Count > 0) { //Pop it and store it in a variable int number = myStack.Pop(); //print the value we popped Console.Write(number +" "); } |
Complete Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
namespace Stacks_and_queues { class Program { static void Main(string[] args) { Stack<int> stack = new Stack<int>(); //1 adding and viewing data from a stack //adding elements to the top of the stack and printing the element on top without removing it using Peek() stack.Push(1); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); stack.Push(2); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); stack.Push(3); Console.WriteLine("Top value in the stack is : {0}", stack.Peek()); //2. removing data from a stack //as long as the count is > 0, as long as the stack is not empty while (stack.Count > 0) { //Pop() will return the element that was removed from the stack Console.WriteLine("The Top value {0} was removed from the stack", stack.Pop()); //print the stack count Console.WriteLine("Current stack count is : {0}", stack.Count); } //3. example reversing an array using a stack //defining an array of ints with some numbers int[] numbers = new int[] { 8, 2, 3, 4, 7, 6, 2 }; Console.WriteLine("the numbers in the array are :"); //foreach number in our array foreach (int number in numbers) { //print it Console.Write(number + " "); //push it into our stack(add) myStack.Push(number); } //new line Console.WriteLine(""); Console.WriteLine("the numbers in reverse :"); //as long as our stack is not empty while (myStack.Count > 0) { //Pop it and store it in a variable int number = myStack.Pop(); //print the value we popped Console.Write(number +" "); } } } } |
Challenge: Check if a Number is a Palindromic Number Using a Stack
Take a number from the user and check if the number is a palindromic number or not then print the result
A palindromic number is a number that is the same if you read it from left to right or from right to left, In other words, the number will be the same in reverse
Example on palindromic numbers: 11, 101, 545, 123321, 9889
Solution
Without using a stack we would need a mathematical way to extract each digit in our number from the right store it in a list and compare each digit in our list with the digits of the number we have
or we can count how many digits we have to make a loop that has 2 variables i & j and run each of them from a different side of the number and compare the indexes of j & i which represents digits of the number, We also will have to make sure that we don’t touch the middle digit in case the number was composed of an odd number of digits since we won’t have a digit to compare it with
so it’s going to be a lengthy process.
But a stack can be used to solve this issue like magic we simply need to reverse the number using a stack and if the reversed number is the same as the original number then it’s a palindromic number !.
as easy as it sounds the implementation goes something like this
Solution 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
using System; using System.Collections.Generic; namespace Stacks_and_queues { class Program { static void Main(string[] args) { Console.WriteLine("Please enter a number"); //read a number and store it string input = Console.ReadLine(); //here we took advantage of the try parse method to check if the input is an int but we don't actually need the number in a parsed from we need it in string form if (int.TryParse(input, out int number)) { //since the input string is a valid number //pass it as a parameter to our IsPalindrom method which will return true if it's a palindromic number if (IsPalindrom(input)) { //if yes print it Console.WriteLine("{0} is palindrom number", number); } else { //if not print it is not Console.WriteLine("{0} is not palindrom number", number); } } else { //if the input is not a valid number, it wasn't parsed Console.WriteLine("please enter a number next time"); } //pause Console.ReadKey(); } static bool IsPalindrom(string number) { //define a new stack Stack<char> digits = new Stack<char>(); // go through each character in our input (string) for(int i = 0; i < number.Length; i++) { //push each character in the string into our stack digits.Push(number[i]); } //go through each character in our input //since we already pushed each character in our string into our stack we know that they are of the same size //that's why we didn't check for the count of the string before we popped each element for(int i = 0; i < number.Length; i++) { //pop each digit from our stack in the form of a character and store it in a variable //since a stack is LIFO the last character we stored is going to be the first character to be popped //so we compare it against the first element in our string char topDigit = digits.Pop(); if (topDigit != number[i]) { //if the digit from the top of the stack does't equals the digit from the string then the number is not a palindromic number and no need to continue in the loop //so we just return false return false; } } //if we reached this point it means all digits in the string were equal to the digits from the stack(same number but reversed) //this means the number is a palindromic number and we return true return true; } } } |
Solution 2 concatenation
More simplified solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
static bool IsPalindrom2(string number) { //define our stack of characters Stack<char> digits = new Stack<char>(); //push every digit in our number(string) into our stack foreach(char digit in number) { digits.Push(digit); } //an empty string to store the characters from the stack in reverse string numberReversed = ""; //as long as our stack is not empty while (digits.Count > 0) { //remove the top digit and store it char digit = digits.Pop(); //add it to our string (concatenation) numberReversed += digit.ToString(); } //return the result of the expression number == numberReversed: which will equal to true if the number (original) equals to the reversed number return number == numberReversed; /*this is the same as the following if(number == numberReversed){ return true; }else{ return false; } } |