Stack – Data Structures and Algorithms using C#

In our previous article Data Structures and Algorithms using C# – Array , we learnt arrays data structure and the operations performed on them. The various elements can be accessed from any position stored in an array. Some practical applications require that the additions or deletions be done only at one end.

For example : Browser back button feature, the web pages visited are put on top of another in the order of their visit. Now, if user clicks back button, he can go only the web page currently lying on the top, i.e., the last visited web page. So, the last visited web page is the first one to get back and so on.

The structure that allows deletions and additions from one end (top) is called a stack. It is also called LIFO (Last In First Out) data structure.

Stack can be visualize as shown in the below picture.

Stack Representation

 

Stack Operations

There are two main operations associated with a stack.

  1. Push – The push operation adds an item on the top of the stack.
  2. Pop – The pop operation removes an item from the top of the stack.
Stack Implementation

Stack operations can be implemented using array in C#. Look at the below codes :

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
64
65
66
67
68
69
70
71
72
73
74
75
public class Stack
{
        private T[] arr = null;
        // Define Capacity of the Stack 
        public int Capacity { get; set; }
        public int Size { get; set; }
        public int Top { get; set; }
        public Stack(int Capacity)
        {
            this.Capacity = Capacity;
            this.Top = -1;
            this.Size = 0;
            this.arr = new T[Capacity];
        }
 
        public bool isEmpty()
        {
            if (Top == -1)
                return true;
            else
                return false;
        }
 
        public T getTop()
        {
            if (Top == -1)
                return default(T);
            else
                return arr[Top];
        }
 
        public bool isFull()
        {
            if (Capacity == (Top+1))
                return true;
            else
                return false;
        }
 
        public bool Push(T value)
        {
            if (isFull())
                return false;
 
 
            //this.Size++;
            this.arr[++Top] = value;
            return true;
        }
 
        public T Pop()
        {
            if ((Top+1) == 0)
                return default(T);
            //this.Size--;
            T result = this.arr[Top];
            this.arr[Top] = default(T);
            Top--;
            return result;
        }
 
        public string PrintStack()
        {
            if ((Top + 1) == 0)
                return String.Empty;
 
            string res = String.Empty;
            for (int i = 0; i < (Top + 1); i++)
            {
                res = res + this.arr[i].ToString() + "-->";
            }
            return res;
 
        }
}

Let’s use the above Stack program to push and pop some website visited from it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Program
{
        static void Main(string[] args)
        {
            Stack stack = new Stack(5);
 
            stack.Push("www.google.com");
            stack.Push("www.codemog.com");
            stack.Push("www.w3school.com");
            stack.Push("www.facebook.com");
            stack.Push("www.linkedin.com");
 
            Console.WriteLine("Website Visited are : ");
            Console.WriteLine(stack.Display());
 
            stack.Pop();
            stack.Pop();
            stack.Pop();
            Console.WriteLine("Website Visited are : ");
            Console.WriteLine(stack.Display());
        }
}

Output :

Stack Output

 

Applications Of Stack

The stacks are used in various applications such as :

  • Arithmetic expression evaluation (A / B + C)
  • Backtracking
  • Implementation of recursive functions
  • web page-visited history (Browser Back button feature)
Performance Consideration

The performance of the stack data structure for ‘n’ elements is:

  • The space complexity is O(n).
  • The time complexity of each operation is O(1).
Most Popular Interview Questions on Stack:
  • Check for balanced parentheses in an expression
  • Implement stack using a queue.
  • Implement Stack using Linked List
  • Min Stack Problem

So, it was all about Stack Data Structure, if you have any query then please comment below and let us know. If you liked this article, then please follow us on Facebook to get notification for new posts.

Happy Learning 🙂

Rahul is a Data Geek, technology enthusiast, a passionate writer, thinker with passion for computer programming.  He loves to explore technology and finds ultimate joy when writing about trending technology, geek stuff and web development.