An immutable stack keeps last-in, first-out behavior without changing an existing stack. Push returns a stack with a new top item; Pop returns the stack beneath the top. Keep a reference to the old stack, and it remains available after either operation. section 2.2
The interface separates the operations callers need from the linked-list implementation:
- Push returns a new stack. Peek reads the top item, and Pop returns the remaining stack; Peek and Pop require a nonempty stack. section 2.2
- IsEmpty lets callers check that requirement. Implementing IEnumerable<T> also lets the stack serve where a sequence is needed. section 2.2
- Represent the empty stack with an object rather than a null reference. A nonempty stack stores an item and a reference to its tail; pushing creates a new head that points to the existing stack. section 2.2
Listing 2.2 Implementing the immutable stack
class ImStack<T> : IImStack<T>
{
private class EmptyStack : IImStack<T> #1
{
public EmptyStack() { }
public IImStack<T> Push(T item) => new ImStack<T>(item, this); #2
public T Peek() => throw new InvalidOperationException();
public IImStack<T> Pop() => throw new InvalidOperationException();
public bool IsEmpty => true;
public IEnumerator<T> GetEnumerator()
{
yield break;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); #3
}
public static IImStack<T> Empty { get; } = new EmptyStack(); #4
private readonly T item;
private readonly IImStack<T> tail;
private ImStack(T item, IImStack<T> tail) #5
{
this.item = item;
this.tail = tail;
}
public IImStack<T> Push(T item) => new ImStack<T>(item, this);
public T Peek() => item;
public IImStack<T> Pop() => tail;
public bool IsEmpty => false;
public IEnumerator<T> GetEnumerator()
{
for (IImStack<T> s = this; !s.IsEmpty; s = s.Pop())
yield return s.Peek();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
The C# implementation shows the empty-stack object and the new-head construction used by Push. section 2.2
One stack, two branches
Starting with [], push 10 to get [10]. Push 20 onto that stack to get [20, 10], or push 30 onto the same [10] stack to get [30, 10]. Neither branch replaces the other. Popping [30, 10] returns [10]; popping again returns []. The branches can share their unchanged tail. section 2.2
There is a useful type-system consequence, with a qualification. A C# interface containing Push(T) cannot be covariant in T because the method takes T as input. Move Push to an extension method, and the remaining stack interface can be covariant: a stack of a derived type can be treated as a stack of its base type before another base-type value is pushed. section 2.3
Listing 2.5 A covariant immutable stack
interface IImStack<out T> : IEnumerable<T> #1
{
T Peek(); #2
IImStack <T> Pop();
bool IsEmpty { get; }
}
class ImStack<T> : IImStack<T>
{
…
public static IImStack<T> Push(T item, IImStack<T> tail) => #3
new ImStack<T>(item, tail);
…
}
static class Extensions #4
{
public static IImStack<T> Push<T>(this IImStack<T> stack, T item) =>
ImStack<T>.Push(item, stack);
}
IImStack<Tiger> s1 = ImStack<Tiger>.Empty;
IImStack<Tiger> s2 = s1.Push(new Tiger());
IImStack<Tiger> s3 = s2.Push(new Tiger());
IImStack<Animal> s4 = s3; #5
IImStack<Animal> s5 = s4.Push(new Giraffe());
Console.WriteLine(s5.Bracket());
The listing shows the covariant interface, extension-method Push, and a stack used through a broader element type. section 2.3
For production C#, System.Collections.Immutable already provides immutable collections. Building this stack is useful for understanding the design: decide which operations would mutate a conventional stack, make those operations return new values, and preserve old versions by sharing unchanged structure. section 2.2 section 2.0
