How is my implementation of an immutable stack?

Question

Below is my implementation of an immutable stack class. The reverse function is trying to return a stack with all elements reversed. Is my implementation good? Maybe the reverse function can be faster?

public class ImStack<T> {
 private final T head;
 private final ImStack<T> tail;
 public ImStack ( T head, ImStack<T> tail)
 {
 this.head = head;
 this.tail = tail;
 }
 public ImStack<T> pop()
 {
 return this.tail;
 }
 public ImStack<T> push( T e)
 {
 return new ImStack<T>( e, this);
 }
 public T peek()
 {
 return this.head;
 }
 public boolean isEmpty()
 {
 if ( head == null && tail == null)
 return true;
 else return false;
 }
 public int size()
 {
 if ( isEmpty())
 return 0;
 else return 1 + tail.size();
 }
 public ImStack<T> reverse()
 {
 ImStack<T> resultStack = new ImStack<T> ( null,null);
 ImStack<T> tempStack;
 tempStack = this;
 for ( int i = 0 ; i < this.size(); i++)
 {
 resultStack = resultStack.push(tempStack.peek());
 tempStack = tempStack.pop();
 }
 return resultStack;
 }
}

• 200_success: Stacks typically don't support a reverse() operation, since that would violate the last-in, first-out principle, which is the purpose of stacks.
• CodesInChaos: size() might overflow the stack, I'd prefer an iterative version.

Answer 1

Writing an elegant immutable stack is difficult in Java, mainly due to the lack of multiple return values. But your code does look quite fine.

I am comparing your API with Scala's immutable stack. One interesting bit is that there the signature of push translates to:

public <T2 super T> ImStack<T2> push(T2 e)

which looks uncomfortable but makes a lot of sense too: Adding elements to a stack can widen the type but never narrow it down. Keeping the current type is a special case of this.

Your isEmpty method is unfortunately flawed. Assume I have created a stack of one element, like:

Object myObject = null;
ImStack<Object> stack = new ImStack<Object>(myObject, null);

Now stack.peek() is correctly null. On an empty stack, this should have created an exception, not returned a null.

One solution to solve this problem is to have isEmpty() always return false. We also create a private subclass1 of ImStack called ImEmptyStack, where isEmpty() returns true, and peek() throws an exception. In your constructor, you create a new empty stack as tail when that argument would be null:

ImStack(T head, ImStack<? extends T> tail) {
 this.head = head;
 this.tail = tail != null ? tail : new ImEmptyStack<T>();
}

_{1: Actually, subclassing here leads to problems. The two classes should both be subtypes of a common interface. So basically, the Composite Pattern.}

By overriding the size() in the ImEmptyStack, you can simplify that as well:

class ImStack<T> {
 public int size() {
 return 1 + tail.size();
 }
}
class ImEmptyStack<T> extends ImStack<T> {
 public int size() {
 return 0;
 }
}

Back to your isEmpty() method, code like this should never happen:

if ( head == null && tail == null)
 return true;
else return false;

because it is equivalent to return(head == null && tail == null). Every time you write code like return foo() ? true : false, you know you can simplify that.

I'd like to sketch your reverse() method in a more functional manner, using an accumulator argument:

public ... reverse() {
 return this.reverse(new ImEmptyStack<T>());
}
private ... reverse(ImStack<...> acc) {
 return tail.reverse(acc.push(head));
}
// Empty stack:
private ... reverse(... acc) {
 return acc;
}

This is as efficient as your solution, because your size call also traverses the whole stack recursively. The advantage of my solution is the simplicity. Of course, it is trivial to rewrite this to an iterative solution, because the above sketch is tail recursive:

reverse() {
 ImStack<T> accumulator = new ImEmptyStack();
 ImStack<T> current = this;
 while(!( current instanceof ImEmptyStack<T> )) {
 accumulator = accumulator.push(current.peek());
 current = current.pop();
 }
 return accumulator;
}

Note that .pop() can never return null in my adaption of your code (an empty stack should throw an exception).

---

Something minor that I noticed is your inconsistent spacing around the argument lists of your methods:

ImStack ( T head, ImStack<T> tail) // left outer and inner space
pop() // no space
push( T e) // left inner space

This is no problem in itself, but it would be better to settle for one style.

• amon: @CodesInChaos thanks, fixed :) (in the future, you can also suggest a fix directly by clicking on "edit" under the question, and making the change. If it had been wrong, it can always be reverted.)
• CodesInChaos: I know how to edit, I have a few hundred of them on SO. But in my experience most posters aren't comfortable with that kind of change and prefer a comment.
• user2894168: It is really a great help to me. Thank you very much :)