Overview of Stack in C#

Stack

A stack is a data structure in which items are added or removed in a Last In First Out (LIFO) manner. That means that items that are added last will be removed first. We can use an example of stack of plates in which the last added plate will be removed first. In computer science this data structure is very important because many applications are implemented using a stack. A stack is somewhat of a restrictive data structure since it allows addition and removal of nodes at the same point/direction only. A stack basically has two methods, Push and Pop.



In this article I am explaining how to create a custom stack collection class. We can create a stack using a linked list and array. For implementing a stack we must understand the basic operations that can be performed on a stack.

1. Push: Push in a stack means adding elements to the stack. Elements are added in the stack from one direction only. I am calling that position as the top of the stack. A stack is somewhat of a restrictive data structure because it only allows insertion of elements from the top of the stack.
2. Pop: Pop in a stack means removing an element from the stack. Items are removed from the stack from one direction, in other words from the top. In other words, if items are added in the order 1, 2, 3 then on calling pop then item 3 will be removed first then 2 and then 1.
3. Peek: A Peek operation returns the last added element in the stack or the top element of the stack.
4. Clear: It will clear all the items of the stack.
5. Enumerating among elements of the stack.

Stack Implementation using Linked List

A stack is implemented using a linked list and is very easy and ideal also. A linked list will only expand based upon the number of items in the stack. If you want to get an overview of a Linked List then you can read my previous article at Overview of Linked List.

So for creating a stack we will first create a class named stack and will create a Linked List object in that.

public class Stack<T> : IEnumerable<T>
{
    LinkedList<T> list = new LinkedList<T>();
}

For enumerating among items of the stack we have used the IEnumerable interface. I am also using generics so that we can use any type of data. If you want to read about the IEnumerable interface then please read my article Difference Between IEnumerable, ICollection and IList Interface.

1. Push Method

As we know items in a stack are stored one after the other so will use the AddLast method of Linked List so items will be stored one after the other.

public void Push(T value)
{
    list.AddFirst(value);
}

2. Pop Method

The Pop method removes the top element from the stack, or we can say that the last added item in the stack will be removed first. For implementing the Pop method we first check the count in the list because if the list is empty then an element cannot not be popped from the stack. Then we can get the top element of the stack using the First property of the list and we will call the RemoveFirst method to remove the element from the collection.

public T Pop()
{
    if (list.Count == 0)
    {
        throw new InvalidOperationException("The Stack is empty");
     }
    T value = list.First.Value;
    list.RemoveFirst();
    return value;
}

3. Peek Method

The Peek method returns the top element from the stack. We must check the count property of the list before returning the top element because we cannot not call the peek method if the stack is empty. Then we will use the first property of the list to return the top element of the stack.

public T Peek()
{
    if (list.Count == 0)
    {
        throw new InvalidOperationException("The Stack is empty");
    }
    return list.First.Value;
}

4. Clear Method

It clears the entire stack and sets the count of elements to 0.

public void Clear()
{
    list.Clear();
}

5. Enumerator

For enumerating among the stack items, we will call the GetEnumerator method that will internally allow us to iterate among items in the stack.

public IEnumerator<T> GetEnumerator()
{
    return list.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return list.GetEnumerator();
}

Stack Implementation using Array

We can also implement a stack by an array. The only problem with an array is that we need to maintain its size on every addition and deletion of an item. I am explaining the functionality of each method. We will create a class naming Stack that is implemented using the IEnumerable interface since we need to enumerate among nodes of the stack. I have created a generic array and a size variable.

public class StackArray<T> : IEnumerable<T>
{
    T[] items = new T[0];
    int size;
}

Initially the size of an array is 0 and we will grow that depending on our requirements. The Size variable will be a manual way to manage the size of the array.

1. Push Method
   
   In the Push method we will store an element into the array and increment the size variable only if the size variable does not equal the number items in the array. In this sample code the size variable will always be smaller than the length of the array. If the size is equal to the number of items in the array then we need to increase the size of the array. In that case we will create the new array and copy all the elements of the old array into a new one. Then we assign a new array to an old one and we will get our resized array.
   

   public void Push(T value)
   {
       if (size == items.Count())
       {
           int newlength = size == 0 ? 4 : size * 2;
           T[] newarray = new T[newlength]; // array with new size
           items.CopyTo(newarray, 0);
           items = newarray;
        }
        items[size] = value;
        size++;
   }

2. Pop Method
   
   It will remove the top element of the stack. In this method we will check the size of the array and then will decrement the size variable and return the popped element back.
   

   public T Pop()
   {
       if (size == 0)
       {
           throw new InvalidOperationException("Empty");
       }
       size--;
       return items[size];
   }

3. Peek Method
   
   This method gives the top element from the stack. Implementation of this method is almost similar to the Pop method.
   

   public T Peek()
   {
       if (size == 0)
       {
           throw new InvalidOperationException("Empty");
       }
       return items[size - 1];
   }

4. Clear Method
   
   Clearing a stack is very easy since we just need to set the size varaible to 0.
   

   public void Clear()
   {
       size = 0;
   }

5. Enumerator Method
   
   We use these methods to enumerate among the list of items in the stack. We need to implement two versions of this method because we are implementing generic an IEnumerable interface.
   

   public IEnumerator<T> GetEnumerator()
   {
       for (int i = size-1; i >= 0; i--)
       {
          yield return items[i];
        }
   }
   System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
   {
       return this.GetEnumerator();
   }

Applications of Stack

A stack is useful in many applications. Its behavior supports many various types of applications. I have mentioned a few of them below:

1. Undo mechanism: To perform undo operations in editors we use a stack. The stack will store all the operations performed in an editor and undo them in reverse order.
2. Reversing a String/List: It is a simple operation in which we can reverse a string or list using a stack.
3. For any language, local variables are created in the stack only.