Previously we have seen how we can implement Stack and Queues in JavaScript: it was , in my opinion, a nice exercise to illustrate how the different JavaScript functions to add an remove items of an array work, and how arrays can be used as such common data structures like Queues and Stacks.

But if you are interested in knowing the ins and outs of implementing a Stack, that post won’t be, I fear, too useful, because almost all of the interesting work is already being done under the hood.

So I though I would provide an example of how to do implement Stacks using C# so that we can talk about some of the basic concepts behind the implementation of Stacks.

Also notice that if you are simply searching for a Stack/Queue implementation to use in your projects you don’t need to implement it yourself, C# provides them already for you:

So if you feel curious about how you could implement a Stack in C#, had not Microsoft already done it for you, keep reading. At the end of our simplified version, you can go an read the source code of the Microsoft’s stack  implementation to get a taste of the real thing.

Some key concepts

Before we jump into the implementation let’s have a look at some points we need to take into account.

For starters we need some kind of structure where we are going to store our values. As we did in JavaScript let’s use an array.

In the JavaScript example we simply defined an empty array, and happily pushed items at the end. Now in C# we need to specify the size of an array. Which means we need to take into account this:

  • Choose a too small size and your stack will be quickly full.
  • Choose a too big size and you will be unnecessarily wasting space.
  • When the array is full, you can add more space by creating a bigger array, and copying the original elements in the new array. Of course that operation has its cost, so you would rather to keep this operations of expanding the array to the minimum.
  • Given that your array has a fixed N length, you need to keep track of the last position occupied in the array, so that you know where to insert the next element, know how many elements are stored in the stack, knowing if the stack is empty, etc.
  • Decide on a policy on Exceptions: for example, what would happen if you where to pop an element of an empty stack? You may choose to simple return a null element, but also you could throw an Exception to tell the user that an unusual situation has arised.
  • What kind of objects is going to hold your stack? Usually we do not want a int Stack, or a string Stack, but a stack that can hold any kind of data.
  • And last, but not least let’s think about the cost associated to the operations of the stack. As with any other kind of data structure we like low costs, when possible we like O(1) – constant – cost, at least for our more commons operations that in this case would be pop and push.

Implementation

Let ´s start by addressing the first points in the list above:

  • We will create a BasicStack class with an array to store our data and an index pointing to the next free position.
  • We will provide two constructors: one that creates a BasicStack with a default capacity of 30 items. Another one that allows the user to specify the desired size of the stack. Since the Stack is created empty, the variable index – pointer to the first free position in the stack – is 0.
 public class BasicStack
    {
        private T[] arrayData;
        private const int defaultSize = 30;
        private int index;

        public BasicStack()
        {
            arrayData = new T[defaultSize];
            index = 0;
        }

        public BasicStack(int size)
        {
            if (size < 0)
                throw new ArgumentOutOfRangeException("size", "Size must be a positive number");

            arrayData = new T[size];
            index = 0;
        }
}
  • Notice also we are using generics to not tie the Stack implementation to a specific type.

Now lets move to the functions to add and remove elements and to peek (check top element of the stack without actually remove it).

        public T Pop()
        {
            if (index == 0)
                throw new InvalidOperationException("Exception: Empty stack");

            return arrayData[--index];

        }

        public T Peek()
        {
            if (index == 0)
                throw new InvalidOperationException("Exception: Empty stack");

            return arrayData[index-1];

        }

        public  void Push(T obj)
        {
            if (index == arrayData.Length)
            {
                T[] newArray = new T[2 * arrayData.Length];
                Array.Copy(arrayData, 0, newArray, 0, index);
                arrayData = newArray;
            }
            arrayData[index] = obj;
            index++;
        }
  • To add an item to the stack we must simple store the item to the array, and update the index pointer accordingly to point to the next free position. The special case is when we try to add an item to an already full stack. In that case we have to create a new array bigger – in this particular implementation we are doubling the capacity – and we have to copy the elements of the old array to the new one.
  • To remove an item from the stack – Pop funtion – we must return the last item of the stack, an update the index pointer accordingly. Notice that when the stack is empty – there are no elements in the array – we will simple throw an exception indicating that the operation is not valid because because the stack is empty.
  • Peek works like removing an item of the stack, except that since we are only peeking, and not actually removing we will not update the index pointer.

Now about the cost of doing Push, Pop, and Peek. Most of the time will be quite good, since we are accessing an array – constant time – and updating the variable index. But there is once instance where the Push function can be significantly expensive: when we try to add an element to the array. In that case we will need to create a new data array, and copy the elements from the  old to the new one, so we will end up with a linear cost for that particular case. Providing a constructor that allow the user to specify the size of the stack, we can reduce the occurrences of that costly operation for those instances where we know which the  size of the data.

And that´s all for today, thanks for reading 🙂 !

Advertisements