A queue is a first-in, first-out data structure: the least recently enqueued item is the next item dequeued. Its interface typically includes Enqueue, Peek, Dequeue, and IsEmpty. section 2.4
An immutable queue returns a new queue after each operation rather than changing the existing one. A linked list makes one end cheap, but efficient operations at both ends require a different arrangement. section 2.4
Build an immutable queue from two immutable stacks:
- Store newly enqueued items in an enqueue stack. section 2.4
- Store items ready for removal in a dequeue stack. section 2.4
- Peek at, or pop from, the dequeue stack; when it is empty, transfer the enqueue stack into it in reversed order. section 2.4
Listing 2.6 An immutable queue interface
interface IImQueue<T> : IEnumerable<T>
{
IImQueue<T> Enqueue(T item);
T Peek();
IImQueue<T> Dequeue();
bool IsEmpty { get; }
}
Use the interface listing to inspect the compact immutable queue contract. section 2.4
Persistent queue values
Starting with the empty queue, enqueueing 10, 20, and 30 produces [10, 20, 30]. Dequeuing successively produces [20, 30], [30], and []; earlier queue values remain available for reuse. 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;
}
}
Use the implementation listing to trace empty-queue handling, two-stack storage, and persistent updates. section 2.4
