How to build a stack (array implementation)

Stack is a data structure based on last in first out (LIFO) policy. A good real-life example is a pile of plates. Just like a pile of plates, a stack allows for operating data that resides at the "end" of the stack. In other words, you can add an item to the top and remove an item from the top.

A stack implements two basic operations:

  • Push - adds an item to the top of the collection
  • Pop - removes the most recently added item

 

stack

 

A stack can be implemented using an array or using a linked list. We're going to implement our Stack based on an array. For simplicity sake, lets first look at the stack implementation with a fixed size. We'll look at a stack without size limitation after that.

A stack with a fixed size

The best way to fix the stack's size is to pass that size to the constructor.

    public class StackFixedSize<T>
    {
        private readonly T[] _data;
        private int _count;

        public StackFixedSize(int size)
        {
            _data = new T[size];
        }
    }

Now we just need to implement the Push and Pop method:

The Push method:

    /// <summary>
    /// Add item on the top of the stack
    /// </summary>
    public void Push(T value)
    {
        _data[_count++] = value;
    }

The Pop method:

    /// <summary>
    /// Return a value from the top of the stack
    /// </summary>
    public T Pop()
    {
        return _data[--_count];
    }

A stack based on an array

One of the limitations in our previous implementation is a fixed stack size. To remove this limitation, we need to be able to increase and shrink our array size. First off, we need a method that moves the _data array to an array with a different size. This can be done with a Resize method.

The Resize method:

    /// <summary>
    /// Resize internal array
    /// </summary>
    private void Resize(int length)
    {
        var result = new T[length];

        for (int i = 0; i < _data.Length; i++)
        {
            result[i] = _data[i];
        }

        _data = result;
    }

Now, we need to check in the Push and Pop methods the array size in case we need to increase or shrink the _data array.

The Push method:

    /// <summary>
    /// Add item to the top of the stack
    /// </summary>
    public void Push(T value)
    {
        if (_data.Length == _count)
        {
            Resize(_data.Length * 2);
        }

        _data[_count++] = value;
    }

The Pop method:

    /// <summary>
    /// Return a value from the top of the stack
    /// </summary>
    public T Pop()
    {
        T result = _data[--_count];
        _data[_count] = default(T);

        if (_count > 0 && _count == _data.Length / 4)
        {
            Resize(_data.Length / 2);
        }

        return result;
    }

Note: The above code is not production ready, it does not check all corner cases such as the case with no elements in the stack. The main goal is to show how a stack can be implemented and what is under the hood.

Video Lesson