Data structures in C# – Part 2 – Stacks

Posts in this Series:

• Linked Lists
• Stacks (this post)
• Queues
• Trees

In the last post I’ve talked about one of the most basic data structures, the linked list. In this post we will start talking about stacks.

A stack is a LIFO (Last In –First out) data structure, it’s like a pile of plates: you start stacking them and, when you need one, you remove the top of the pile, the last you’ve put.

Its structure is very similar to the linked list, but you have these operations on it:

• Push – add a new item to the stack
• Pop – remove the top item from the stack
• Peek – take a look at the top of the stack but don’t remove the item

As you can see, you can only operate on the top of the stack, you cannot add or remove an item in the middle of the stack. As we’ve seen in the last article, creating a generic stack is pretty much the same as creating a non generic one, so we will only develop a generic one in this article.

The Push method will add a new item in the top of the stack, thus setting the _top field to point to the newly created node:

private NodeList<T> _top;
private int _count;

public void Push(T obj)
{
    var node = new NodeList<T>;
    {
        Data = obj,
        Next = _top
    };
    _top = node;
    _count++;
}

The Pop method checks the top of the stack. If it’s null (empty stack), it throws an InvalidOperationException. If the stack isn’t empty, the top and count are updated and the old top is returned:

public T Pop()
{
    if (_top == null)
        throw (new InvalidOperationException("The stack is empty"));
    var result = _top;
    _top = _top.Next;
    _count--;
    return result.Data;
}

Peek is very simple, it only checks if there is any data in the top of the stack and returns its data:

public T Peek()
{
    if (_top != null)
        return _top.Data;
    throw (new InvalidOperationException("The stack is empty"));
}

Our stack is ready. If you take a closer look, you will see that the stack can be implemented with a Linked List: Push will insert an item at the top (with Insert), Pop will get the top item, remove it and return it. Peek will get the top item and return it:

public class StackAsList<T>;
{

    private readonly LinkedList<T> _linkedList = new LinkedList<T>();

    public void Push(T obj)
    {
        _linkedList.Insert(obj);
    }

    public T Peek()
    {
        if (_linkedList.Count == 0)
            throw (new InvalidOperationException("The stack is empty"));
        return _linkedList[_linkedList.Count-1];
    }

    public T Pop()
    {
        if (_linkedList.Count == 0)
            throw (new InvalidOperationException("The stack is empty"));
        var result = _linkedList[_linkedList.Count - 1];
        _linkedList.Remove(result);
        return result;
    }

    public int Count => _linkedList.Count;

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

}

Pretty simple, no? Now we have two implementations of the stack, in the next article we will see the Queue.

The source code for this series of articles is in https://github.com/bsonnino/DataStructures