Today I will breakdown the implementation of an immutable generic stack in C# 7, with full LINQ integration. I decided to do this after reading some good posts by drifter1 exploring different storage structures in C.

Introduction

I am sure everyone knows what stack based storage is, simple LIFO (Last In First Out) storage that traditionally you "push" new values onto the top of the stack, to get them back off you "pop" them off the top until all the values have been removed.

This is implemented using an immutable linked list, where the head of the stack is the head of the linked list. I decided to go with immutability for a few reasons:

• Complete thread safety if you store immutable data
• The ideal fit for this storage type
• I like immutability :)

The immutability means I had to take one liberty with the normal interface push/pop interface, the reasons for this will become self evident when you see the implementation.

Empty

This is how you create every new list, all stacks you create will share this common base.

var stack1 = ImmutableStack<int>.Empty;
var stack2 = ImmutableStack<int>.Empty;

Push

Adds new values to the stack, when called you get back a new stack with the value on the top. The original stack still exists.

// SBD 0.01 for the first to comment with the book I was thinking of :)
var book = ImmutableStack<int>.Empty.Push(4).Push(2);
var newStack= stack.Push(5);

The book stack still contains 4, 2 while newStack contains 5, 4, 2. The 4, 2 values and storage are shared in both.

Pop

Removes the top of the stack and returns you the new stack with the item removed. This is the break in the normal implementation caused by immutability, I could have gone with a (value, newStack) tuple but felt my work around was cleaner.

// stack just contains the value 10.
var stack = ImmutableStack<int>.Empty.Push(10).Push(20).Pop();

Value

You can look at the top value on the stack using this property

// value = 20
var value = ImmutableStack<int>.Empty.Push(10).Push(20).Value;

IsEmpty

Just tells you if the stack is empty or not

var empty = ImmutableStack<int>.Empty.IsEmpty;
var notEmpty = ImmutableStack<int>.Empty.Push(10).IsEmpty;

Count

The number of values contained in the stack

LINQ

I implemented the IEnumerable interface to provide full LINQ integration

// Prints the following
// Next value is 20
// Next value is 10
foreach (var value in ImmutableStack<int>.Empty.Push(10).Push(20))
{
    Console.WriteLine($"Next value is {value}");
}

Implementation

I have tried to keep this as paired down and clean as possible. The various parts should be obvious from the API description.

public class ImmutableStack<T> : IEnumerable<T>
{
    public static ImmutableStack<T> Empty 
        = new ImmutableStack<T>();

    private readonly ImmutableStack<T> _stack;
    private readonly T _value;

    public T Value
    {
        get
        {
            if (IsEmpty)
            {
                throw new Exception("List is empty");
            }

            return _value;
        }
    }

    public int Count { get; }
    public bool IsEmpty => Count == 0;

    // Constructors are private to force use of Empty
    private ImmutableStack() { }

    private ImmutableStack(
        T value, ImmutableStack<T> stack)
    {
        _stack = stack;
        _value = value;
        Count = stack.Count + 1;
    }

    public ImmutableStack<T> Push(T value)
        => new ImmutableStack<T>(value, this);

    public ImmutableStack<T> Pop()
    {
        if (IsEmpty)
        {
            throw new Exception("List is empty");
        }

        return _stack;
    }

    public IEnumerator<T> GetEnumerator()
    {
        var current = this;
        while (!current.IsEmpty)
        {
            yield return current.Value;
            current = current._stack;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

Interested in any feedback as always

Woz