How is my implementation of an immutable stack?

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 {

    private final T head;
    private final ImStack tail;

    public ImStack ( T head, ImStack tail)
    {
        this.head = head;
        this.tail = tail;
    }

    public ImStack pop()
    {
        return this.tail;
    }
    public ImStack push( T e)
    {
        return new ImStack( 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 reverse()
    {
        ImStack resultStack = new ImStack ( null,null);
        ImStack tempStack;
        tempStack = this;
        for ( int i = 0 ; i < this.size(); i++)
        {
            resultStack = resultStack.push(tempStack.peek());
            tempStack = tempStack.pop();
        }
        return resultStack;
    }
}

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  ImStack 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 stack = new ImStack(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 subclass¹ 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 tail) {
  this.head = head;
  this.tail = tail != null ? tail : new ImEmptyStack();
}

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 {
  public int size() {
    return 1 + tail.size();
  }
}

class ImEmptyStack extends ImStack {
  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());
}

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 accumulator = new ImEmptyStack();
  ImStack current     = this;
  while(!( current instanceof ImEmptyStack )) {
    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 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.

StackExchange Code Review Q#32991, answer score: 7