As discussed last time, the solution to our performance problem is to ensure our
_inbound stack doesn’t get too large before we reverse it. This means we need to reverse it early; we can’t leave reversal until it’s needed to replace
Once we’ve reversed the stack, we need somewhere to keep it around until the existing
_outbound stack empties and needs replacing. If a lot of items are enqueued at once, we might have several intermediate stacks to keep around until needed. We need to ensure they are kept in order so that their items are fed out in the right order.
If only we had a data structure that allowed us to maintain an ordered sequence of immutable stacks, taking stacks off the head and adding stacks to the tail when needed.
Hang on, we do:
That’s right, our trick is to create a recursive type definition.
An incomplete definition of
ComplexImmutableQueue<T> looks like this:
This is pretty much the same as our existing
SimpleImmutableQueue<T> but with the addition of
_buffer for keeping track of any intermediate buffers that we’ve already reversed.
We’re not going to get rid of
SimpleImmutableQueue<T>, there’s no need. If our queue never gets big enough to require the intermediate buffering, we don’t need to pay the memory cost of the buffer. Instead, we’ll modify
SimpleImmutableQueue<T> so that when we
.Enqueue() an item that takes the
_inbound queue past a threshold, we’ll promote to use a
Let’s walk through how this works as we add a million items. Assuming we limit the size of our
_inbound stack to sixteen items, this is what our queue will look like after we’ve queued the first eighteen items:
When we go to
.Enqueue() the next item, we can’t add it to the
_inbound stack because the stack would exceed our threshold if it got any larger. Instead, we create a new stack for
_inbound, reverse the previous one, and put it into our
_buffer for later use.
As we add the remaining items to reach a million, each intermediate stack of sixteen items ends up enqueued in our buffer, and we end up with something like this:
Our first two items are held as the
Head of the queue and in the
_outbound stack. The last fourteen items in the
_inbound stack; and all the remaining items are held in our intermediate buffer.
Here’s the code to implement this:
The implementation for
ComplexImmutableQueue<T>.Enqueue() is very similar; the only significant difference is that we don’t start with an empty intermediate
_buffer, but instead use the buffer we’ve already started. The actual implementation is left as an exercise for the reader.
As discussed earlier, we need to implement
IEnumerable<T> for each of our queue implementations. Fortunately, we can build upon the way we’ve previously enabled enumeration of immutable stacks:
Updated 6 Feb: Fixed some errors in the code so the behaviour matches the discussion.