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:
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:
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