Immutability Matters
Simple Queues

Thinking about the functionality we need from a simple immutable queue, we need to easily add a new item onto the end of the queue, and to easily remove an existing item from the front of the queue.

As hinted at previously, we can create a simple immutable queue by composing together two different immutable stacks. We can use one immutable stack to collect new items being enqueued onto the queue, adding them to the stack as they arrive, and another stack to provide items to dequeue from the queue, removing them as they are needed.

An incomplete declaration of SimpleImmutableQueue<T> looks like this:

internal class SimpleImmutableQueue<T> : IImmutableQueue<T>
{
    // Stack for incoming items added to the queue
    private readonly IImmutableStack<T> _inbound;

    // Stack for outgoing items ready to remove from the queue
    private readonly IImmutableStack<T> _outbound;

    // A simple queue is never empty
    public bool IsEmpty => false;

    // The item at the head of this queue
    public T Head { get; }

    public SimpleImmutableQueue(T head)
        : this(head, 
            ImmutableStack<T>.Empty, 
            ImmutableStack<T>.Empty)
    {
    }

    public SimpleImmutableQueue(
        T head,
        IImmutableStack<T> inbound,
        IImmutableStack<T> outbound)
    {
        Head = head;
        _inbound = inbound;
        _outbound = outbound;
    }
}

We use a dedicated property for the head of the queue, so it’s always quick and easy to access, plus a pair of initially empty queues (_inbound and _outbound) to handle the rest of the queue.

For an ImmutableQueue<int> containing just the value 1, we can show this as a simple diagram:

Enqueuing the value 2, we have to make a choice about which of the stacks should receive the new value. Let’s add it to the _outbound queue so that it’s easily available when we need it:

In fact, let’s make that an invariant of our implementation, that we never leave _outbound empty unless _inbound is also empty.

As we add three more values (3, 5, and 8), each gets pushed onto our _inbound stack:

Here’s an implementation of this approach:

public IImmutableQueue<T> Enqueue(T value)
{
    if (_outbound.IsEmpty)
    {
        Debug.Assert(_inbound.IsEmpty);
        return new SimpleImmutableQueue<T>(
            Head, _inbound,_outbound.Push(value));
    }

    return new SimpleImmutableQueue<T>(
        Head, _inbound.Push(value), _outbound);
}

The Debug.Assert() call is checking that our class invarient has been maintained.

Dequeuing values from the queue is slightly more complex. Here’s what we have after a dequeue removing the 1 from the queue shown above:

The head value 2 came from our _outbound stack. Since that was now empty, we reversed our _inbound stack in preparation for our next dequeue, leaving an empty stack in its place.

The algorithm to use isn’t terribly complex:

• If our _outbound stack is already empty, we’ve just dequeued our last item, so we’ll return an empty queue. (This works because of the class invariant that we introduced above).
• Otherwise, we promote the top item from the stack as our new head.
• If that promotion leaves _outbound empty, we reverse the _inbound stack, satisfing the class invariant.

public IImmutableQueue<T> Dequeue()
{
    if (_outbound.IsEmpty)
    {
        Debug.Assert(_inbound.IsEmpty);
        return ImmutableQueue<T>.Empty;
    }

    var head = _outbound.Peek;
    var outbound = _outbound.Discard();
    var inbound = _inbound;

    if (outbound.IsEmpty)
    {
        outbound = inbound.Reverse();
        inbound = ImmutableStack<T>.Empty;
    }

    return new SimpleImmutableQueue<T>(head, inbound, outbound);
}

While this implementation is fully functional, it has one nasty characteristic that renders it unsuitable for production use. See if you can spot the flaw before we discuss the problem and one possible solution.

14 January 2017: Modified code examples to use IsEmpty instead of Empty to test for stacks with no items as previously discussed.