Stack using C# with Linked List

What is the Stack Data Structure?

Stack Data Structure is a Last In First Out type of Data Structure. It has only one end where we do insertion and Deletion of data. So, the last data that we insert to the Stack will be coming out first. In Computer Programming we use Stack extensively, for example pushing the current context data to Stack before calling a function in program execution, etc.  Push, Pop, Top, etc are the main methods available for the stack. The push will be inserting the data to Stack whereas Pop will remove the top of the stack. In this article, we will be learning and implementing Stack using C#.

Let us visualize a sample stack data structure.

The above pictorial representation of the stack data structure shows how a stack data structure works. We can insert or remove the data from only one side (left side from the above figure). When we insert data to the stack we call it Push & when we remove data from it we call it Pop and the last element that we inserted to the stack is knows as the top of the stack or Peek element and these names could be varying across different developers and different programming languages. The meaning of ‘Stack’ is just the same as what we commonly say ‘a stack of books’, books kept on top of another.

Mainly a Stack data structure contains Push, Pop, and Top (or Peek) operations. Let’s see some of the examples. If you see the right side of the above image there are few operations. The number 4 is the first element inserted to the stack & 5 is the last element inserted to the stack. So 5 is the top of the stack here. When you do the Pop operation you will be removing the top of the stack at that point in time.

As we already discussed earlier there might be slight difference in different implementation. Some implementation return top of the stack on execution of Pop operation and some may return void & we will have to explicitly get Top element by invoking that method.

Implementation of Stack using C#

Let us discuss the basic implementation of the stack using C#. We can use an array, linked list, etc. just to demonstrate the functionality. In this example, we are going to use a linked list for Implementing this. Below is the Linked List Node using C#

public class LinkedListNode
{
    public int data;
    public LinkedListNode next;

    public LinkedListNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}

Here you can see that it is a simple singly-linked list node with two properties data & link to the next node. Data is of type Integer, In order to pass these data at during the instantiation, we have included a Constructor also here. In the Constructor method, we are setting the next link of the linked list to null on instantiation so that it can be modified later.

The Below code implements the Stack with Push ,Pop & Peek Operations.

public class Stack
{
    LinkedListNode top;
    

    public Stack()
    {
        top = null;
        
    }

    public LinkedListNode GetNode(int data)
    {
        LinkedListNode node = new LinkedListNode(data);
        return node;
    }

    public void Push(int data)
    {

        LinkedListNode newNode = GetNode(data);
        if (top == null)
        {
            top=newNode;
            return;
        }

        newNode.next = top;
        top = newNode;
       


    }

    public int Peek()
    {
        if (top != null)
        {
            return top.data;
        }
        return -1;
    }

    public int Pop()
    {
        int peek = -1;
        if (top != null)
        {
            peek = top.data;
            top = top.next;
        }

        return peek;


    }

}

Let us go through the code in detail. We have created a class named ‘Stack’ with a LinkedListNodenode as one of the properties of that class. We are initializing this property to null on instantiation of the object of this class. In order to make it simple, we have created a method named GetNode which will return us the single linked list node with the data property of the node-set to the value that we pass.

Push Method using C#

In the Push method, we are adding to the stack. We also check if the stack is empty by checking the top object. If the top is null meaning the stack is empty then we are setting the new node as top & returning from that method. If the stack is not empty, we are pointing the next link of the new Node to the top element & Changing the top element to the new Node. The Below two lines will do this,

newNode.next = top;
top = newNode;

Pop Method using C#

In the Pop method, we will be removing the top of the stack or Peek and returning the data to the calling method. Here we will have to be careful as the stack may be empty, So we are checking if the top is null or not. If the stack is empty then we are returning value as -1 to indicate the calling method that the stack is empty. If the stack is not null we returning the top of the stack and will be pointing the top node to the next node.

peek = top.data;
top = top.next;

The last method is simple the Peek method , It just returns the top of the stack or the Peek element. If the stack is empty it will return -1.

You check the GitHub reference for the code in this link.

Stack in .Net framework

We have how we can implement a stack using c# in our previous sections. In the .NET framework, we have stack already implemented. There are two different types one is generic stack in c# & the other is non-generic stack in c#. Below is a simple c# stack example using generic implementation.

namespace MyTestConsoleApp
{
    class Practice
    {

        public static void Main(string[] args)
        {
            Stack<int> stack = new Stack<int>();

            stack.Push(10);
            stack.Push(20);
            stack.Push(40);

            while(stack.Count!=0)
            {
                Console.WriteLine(stack.Pop());
            }
        }

    }
}