A two-stack queue implements FIFO behavior with separate immutable stacks: one receives enqueued items, while the other supplies dequeued items. When the dequeue stack is empty, it receives all items moved from the enqueue stack. section 2.4
The implementation preserves a useful invariant and handles three dequeue situations:
- A nonempty queue always has a nonempty dequeue stack; the first enqueued item therefore goes there. section 2.4
- Popping when the dequeue stack has multiple items is O(1); an empty dequeue stack triggers transfer from the enqueue stack. section 2.4
Listing 2.7 An immutable queue implementation
class ImQueue<T> : IImQueue<T>
{
public static IImQueue<T> Empty { get; } =
new ImQueue<T>(ImStack<T>.Empty, ImStack<T>.Empty); #1
private readonly IImStack<T> enqueues;
private readonly IImStack<T> dequeues;
private ImQueue(IImStack<T> enqueues, IImStack<T> dequeues)
{
this.enqueues = enqueues;
this.dequeues = dequeues;
}
public IImQueue<T> Enqueue(T item) =>
IsEmpty ? #2
new ImQueue<T>(enqueues, dequeues.Push(item)) :
new ImQueue<T>(enqueues.Push(item), dequeues);
public T Peek() => dequeues.Peek(); #3
public IImQueue<T> Dequeue()
{
IImStack<T> newdeq = dequeues.Pop(); #4
if (!newdeq.IsEmpty)
return new ImQueue<T>(enqueues, newdeq);
if (enqueues.IsEmpty)
return Empty;
return new ImQueue<T>(ImStack<T>.Empty, enqueues.Reverse()); #5
}
public bool IsEmpty => dequeues.IsEmpty;
public IEnumerator<T> GetEnumerator()
{
foreach (var item in dequeues)
yield return item;
foreach (var item in enqueues.Reverse())
yield return item;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
static class Extensions
{
public static IImStack<T> Reverse<T>(this IImStack<T> stack)
{
var result = ImStack<T>.Empty;
for (; !stack.IsEmpty; stack = stack.Pop())
result = result.Push(stack.Peek());
return result;
}
}
Inspect the generic immutable queue interface and implementation, including persistence, the empty singleton, enqueue placement, and dequeue logic. section 2.4
Persistent queue sequence
Successive enqueues of 10, 20, and 30 produce [10, 20, 30]; three dequeues produce [20, 30], [30], and []. Earlier queue versions remain reusable.
