An immutable stack is a last-in, first-out collection whose operations return new versions instead of changing existing ones. A linked top node points to the previous stack state, allowing each version to remain available. section 13.3.1
The implementation exposes three core behaviors:
- Push returns a new stack containing the item above the previous top. section 13.3.1
- Pop returns the top value and a new stack whose top is the previous node’s successor. section 13.3.1
- IsEmpty reports whether the stack has a top node. section 13.3.1
Versioned pushes and pop
Create stack1, derive stack2 with Push(1), derive stack3 with Push(2), then derive stack4 with Pop(out item). The earlier versions remain distinct. section 13.3.1
Listing 13.15 Immutable stack implementation
public class MyImmutableStack<T>
{
private record class StackItem(T Value, StackItem Next);
private readonly StackItem? _top;
public MyImmutableStack() {}
private MyImmutableStack(StackItem? top)
{
_top = top;
}
public MyImmutableStack<T> Push(T item)
{
return new MyImmutableStack<T>(new StackItem(item,_top);
}
public MyImmutableStack<T> Pop(out T? item)
{
if(_top == null)
throw new InvalidOperationException("Stack is empty");
item = _top.Value;
return new MyImmutableStack<T>(_top.Next);
}
public bool IsEmpty => _top == null;
}
Inspect the complete C# implementation built from a nullable top reference and nested StackItem records. section 13.3.1
