Immutability Matters
Queues

Moving on from our discussion of immutable stacks, let us look at how to effectively implement an ImmutableQueue<T>. What can the exercise teach us?

As before, let’s begin by declaring an interface for the functionality we want to have:

public interface IImmutableQueue<T>
{
    // The item at the front of the queue
    T Head { get; }

    // Test if this queue is empty
    bool IsEmpty { get; }

    // Add an item onto the end of the queue
    IImmutableQueue<T> Enqueue(T value);

    // Remove the front item from the queue
    IImmutableQueue<T> Dequeue();
}

We provide immediate access to the front of the queue (via Head) and an easy test to see if the queue is empty (see IsEmpty). There are just two ways to modify the queue - by adding a new item onto the end (Enqueue()) and by removing the head from the front (Dequeue()). Both of these return the new queue for our users to reference.

As with our original stack interface, the members are clearly split between queries on instance state and commands that change that state, returning a new queue instance. (See my earlier post on method archetypes for more on this.)

Implementing this interface for an empty queue is relatively simple:

// Internal class because we want to expose the interface instead 
internal class EmptyImmutableQueue<T> : IImmutableQueue<T>
{
    public bool IsEmpty => true;

    public T Head => throw new InvalidOperationException();

    public IImmutableQueue<T> Dequeue()
    {
        throw new InvalidOperationException();
    }

    public IImmutableQueue<T> Enqueue(T value)
    {
        return new SimpleImmutableQueue<T>(value);
    }
}

Just like SimpleImmutableStack<T>, writing our initial implementation of SimpleImmutableQueue<T> involves a key realization that makes the whole thing much easier to achieve. I’m going to leave that for next time, but I’ll give you a clue: there’s a reason this series started by talking about stacks.

Updated 23/1/2017: The implementation of EmptyImmutableQueue<T>.Head has been modified to properly throw an InvalidOperationException.