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:
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 (
_outbound) to handle the rest of the queue.
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
Here’s an implementation of this approach:
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
_outboundstack 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
_outboundempty, we reverse the
_inboundstack, satisfing the class invariant.
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.