45. Implementing an immutable stack
A common coding challenge in interviews sounds like this: implement an immutable stack in Java. In case you need a quick overview of immutability concepts and the principles of writing an immutable class then I strongly recommend you Java Coding Problems, First Edition, Problems 47-52.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 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 the ImmutableStack.empty() method as follows:
Stack<String> s = ImmutableStack.empty(String.class); In the bundled code, you can how this stack can be used further.