50. Implementing an immutable stack

A common coding challenge in interviews is this: Implement an immutable stack in Java.

Being an abstract data type, a stack needs at least this contract:

public interface Stack<T> extends Iterable<T> {
  boolean isEmpty();
  Stack<T> push(T value);
  Stack<T> pop();
  T peek();    
}

Having this contract, we can focus on the immutable implementation. Generally speaking, an immutable data structure stays the same until an operation attempts to change it (for instance, to add, put, remove, delete, push, and so on). If an operation attempts to alter the content of an immutable data structure, a new instance of that data structure must be created and used by that operation, while the previous instance remains unchanged.

Now, in our context, we have two operations that can alter the stack content: push and pop. The push operation should return a new stack containing the pushed element, while the pop operation should return the previous stack. But, in order to accomplish this, we need to start from somewhere, so we need an empty initial stack. This is a singleton stack that can be implemented as follows:

private static class EmptyStack<U> implements Stack<U> {
  @Override
    public Stack<U> push(U u) {
      return new ImmutableStack<>(u, this);
    }
    @Override
    public Stack<U> pop() {
      throw new UnsupportedOperationException(
        "Unsupported operation on an empty stack");
    } 
    @Override
    public U peek() {
      throw new UnsupportedOperationException (
        "Unsupported operation on an empty stack");
    }
    @Override
    public boolean isEmpty() {
      return true;
    }
    @Override
    public Iterator<U> iterator() {
      return new StackIterator<>(this);
  }
}

The StackIterator is a trivial implementation of the Java Iterator. Nothing fancy here:

private static class StackIterator<U> implements Iterator<U> {
  private Stack<U> stack;
  public StackIterator(final Stack<U> stack) {
    this.stack = stack;
  }
  @Override
  public boolean hasNext() {
    return !this.stack.isEmpty();
  }
  @Override
  public U next() {
    U e = this.stack.peek();
    this.stack = this.stack.pop();
    return e;
  }
  @Override
  public void remove() {
  }
}

So far, we have the Iterator and an empty stack singleton. Finally, we can implement the logic of the immutable stack as follows:

public class ImmutableStack<E> implements Stack<E> {
  private final E head;
  private final Stack<E> tail;
  private ImmutableStack(final E head, final Stack<E> tail) {
    this.head = head;
    this.tail = tail;
  }
  public static <U> Stack<U> empty(final Class<U> type) {
    return new EmptyStack<>();
  }
  @Override
  public Stack<E> push(E e) {
    return new ImmutableStack<>(e, this);
  }
  @Override
  public Stack<E> pop() {
    return this.tail;
  }    
  @Override
  public E peek() {
    return this.head;
  }
  @Override
  public boolean isEmpty() {
    return false;
  }
  @Override
  public Iterator<E> iterator() {
    return new StackIterator<>(this);
  }
  // iterator code
  // empty stack singleton code
}

Creating a stack starts by calling theImmutableStack.empty() method, as follows:

Stack<String> s = ImmutableStack.empty(String.class);

In the bundled code, you can how this stack can be used further.