Stack as a Persistent Data Structure Implementation

Question

After reading some articles about immutability, I found out that there are persistent data structures. In the following, I implemented a stack as a persistent data structure.

What I like about the code in the current state

• it contains no if-statements
• no method is longer than one line
• it works like recursion

Implementation

The implementation is based on the abstraction Stack, which has two concrete data-types: EmptyStack and NonEmptyStack. A Stack needs to implement 4 methods as described below.

public interface Stack<E> {
 /**
 * @return the number of elements
 */
 int size();
 /**
 * adds a new element to the top of the {@code Stack}
 *
 * @param top represents the new element to be added
 * @return a {@code Stack} with {@code top} on it
 */
 Stack<E> push(E top);
 /**
 * removes the top element of the {@code Stack}
 *
 * @return a {@code Stack} without the top element
 */
 Stack<E> pop();
 /**
 * @return if {@code Stack} is empty {@code Optional.empty};
 * otherwise {@code Optional.of(E)} where {@code E} is the top element
 */
 Optional<E> top();
}

The EmptyStack represents the base case: when a Stack has no element. For each method it is easy to predict all return values:

• the size is always 0
• push() always will return a NonEmptyStack with the new top element and the current instance as the previous version
• pop() can't return a top element; so it always will return an EmptyStack
• top() can't return a top element; so it always will return an Optional.empty

class EmptyStack<E> implements Stack<E> {
 @Override
 public int size() {
 return 0;
 }
 @Override
 public Stack<E> push(E top) {
 return new NonEmptyStack<>(top, this);
 }
 @Override
 public Stack<E> pop() {
 return this;
 }
 @Override
 public Optional<E> top() {
 return Optional.empty();
 }
}

On the other hand there is the NonEmptyStack which represents a Stack that contains elements. A NonEmptyStack is made up of its element on the top and a Stack as its tail, which represents the previous version.

• the size is always the size of the previous version plus 1 for the new top element
• push() always will return a NonEmptyStack with the new top element and the current instance as the previous version
• pop() always returns the tail
• top() always returns the element which represents the top and since it can be null I used Optional.ofNullable

class NonEmptyStack<E> implements Stack<E> {
 private final Stack<E> tail;
 private final E top;
 NonEmptyStack(E top, Stack<E> tail) {
 this.tail = tail;
 this.top = top;
 }
 @Override
 public int size() {
 return 1 + tail.size();
 }
 @Override
 public Stack<E> push(E top) {
 return new NonEmptyStack<>(top, this);
 }
 @Override
 public Stack<E> pop() {
 return tail;
 }
 @Override
 public Optional<E> top() {
 return Optional.ofNullable(top);
 }
}

EmptyStack and NonEmptyStack are package-private therewith a client only interacts with a Stack instead of two different implementations of it. For that I created a Factory StackFactory which returns an EmptyStack as a Stack and the clients never interacts directly with a concrete implementation.

public class StackFactory<E> {
 public Stack<E> create() {
 return new EmptyStack<>();
 }
}

Unit Tests

import org.junit.jupiter.api.Test;
import java.util.Optional;
import static org.junit.jupiter.api.Assertions.*;
class EmptyStackTest {
 private final Stack<String> EMPTY_STACK = new EmptyStack<>();
 @Test
 void givenAnEmptyStack_whenQueryTheSize_thenExpect0() {
 // arrange
 // act
 int size = EMPTY_STACK.size();
 // assert
 assertEquals(0, size);
 }
 @Test
 void givenAnEmptyStack_whenPushAnElementToIt_thenExpectANonEmptyStack() {
 // arrange
 // act
 Stack<String> stack = EMPTY_STACK.push("first");
 // assert
 assertTrue(stack instanceof NonEmptyStack);
 }
 @Test
 void givenAnEmptyStack_whenRemoveTheFirstElement_thenExpectAnEmptyStack() {
 // arrange
 // act
 Stack<String> stack = EMPTY_STACK.pop();
 // assert
 assertTrue(stack instanceof EmptyStack);
 }
 @Test
 void givenAnEmptyStack_whenAccessTopElement_thenExpectItDoNotExists() {
 // arrange
 // act
 Optional<String> top = EMPTY_STACK.top();
 // assert
 assertTrue(!top.isPresent());
 }
}

import org.junit.jupiter.api.Test;
import java.util.Optional;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;
class NonEmptyStackTest {
 private final String ITEM = "first";
 @Test
 void givenEmptyStackAndItem_whenInstantiateAndQueryTheSize_thenExpect1() {
 // arrange
 Stack<String> stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
 // act
 int size = stack.size();
 // assert
 assertEquals(1, size);
 }
 @Test
 void givenNonEmptyStackWitOneItemAndANewItem_whenInstantiateAndQueryTheSize_thenExpect2() {
 // arrange
 NonEmptyStack<String> nonEmptyStack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
 Stack<String> stack = new NonEmptyStack<>(ITEM, nonEmptyStack);
 // act
 int size = stack.size();
 // assert
 assertEquals(2, size);
 }
 @Test
 void givenEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
 // arrange
 Stack<String> stack = new EmptyStack<>();
 // act
 Stack<String> nonEmptyStack = stack.push(ITEM);
 // assert
 assertEquals(Optional.of(ITEM), nonEmptyStack.top());
 }
 @Test
 void givenNonEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
 // arrange
 Stack<String> emptyStack = new EmptyStack<>();
 Stack<String> firstChange = emptyStack.push("value");
 // act
 Stack<String> stack = firstChange.push(ITEM);
 // assert
 assertEquals(Optional.of(ITEM), stack.top());
 }
 @Test
 void givenNonEmptyStackWithOneItem_whenRemoveTheTopItem_thenExpectEmptyStack() {
 // arrange
 Stack<String> testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>());
 // act
 Stack<String> stack = testCandidate.pop();
 // assert
 assertTrue(stack instanceof EmptyStack);
 }
 @Test
 void givenNonEmptyStackWithTwoItems_whenRemoveTheTopItem_thenExpectNonEmptyStack() {
 // arrange
 Stack<String> testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>()).push(ITEM);
 // act
 Stack<String> stack = testCandidate.pop();
 // assert
 assertTrue(stack instanceof NonEmptyStack);
 }
 @Test
 void givenNonEmptyStack_whenQueryTopItem_thenExpectTopItem() {
 // arrange
 Stack<String> stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
 // act
 Optional<String> top = stack.top();
 // assert
 assertEquals(Optional.of(ITEM), top);
 }
}

Example

public class Main {
 public static void main(String[] args) {
 Stack<String> stack = new StackFactory<String>().create()
 .push("first")
 .push("second")
 .push("third");
 Stack<String> modified = stack.pop()
 .pop();
 modified.top()
 .ifPresent(System.out::println); // "first"
 modified.pop()
 .top()
 .ifPresent(System.out::println); // nothing happens 
 }
}

---

This little experiment was very entertaining. I appreciate every feedback and thank you very much for reading my code! :]

Answer 1

In this implementation, null entries are problematic. From the public interface, it is impossible to tell if the stack has a null entry, or has reached the bottom: in both cases, top() will return Optional.empty().

It seems wrong to silently convert nulls into Optional.empty()s. I would do one of the following:

1. Do not store null entries in the stack. Instead, throw an exception on pushing a null value.

2. Stop using Optionals and instead throw an exception when top is called on an empty stack. Add an empty method to determine if the stack is empty.

Other than that, very clean simple code! A few smaller comments.

Note that push has the same implementation in both EmptyStack and NonEmptyStack. If you like, they could inherit from a single abstract class implementing push. This is a judgement call: repeated code is kinda bad, but adding a whole new abstract class is complicated. Perhaps the the cure is worse than the disease...

Computing size is slow: time O(n). If you are worried about this, you could compute and store the size in the constructor.

• Stingy: Since Java 8, methods defined in an interface can have a default implementation. So you wouldn't have to create a separate abstract class to avoid the code duplication in the push methods.

Answer 2

The need to instantiate a StackFactory in order to create a Stack seems superfluous. I would suggest making create() a static method, which in turn would mean that, instead of the class StackFactory, it will be the method create() that needs a type parameter:

public class StackFactory {
 public static <E> Stack<E> create() {
 return new EmptyStack<>(); //compiler can infer the type parameter for the newly created Stack from the method's return type
 }
}

Then you can call the method like this:

Stack<String> stack = StackFactory.<String>create()
 .push("first")
 .push("second")
 .push("third");

Note that, in the above example, you need to explicitly pass the type parameter String to the method create(), because the newly created Stack is not directly assigned to a variable of type Stack<String> and the compiler can therefore not infer the type parameter E for the call to the method <E> create() to be String.

Answer 3

I'd like to point out, that it's unnecessary to create a new instance of EmptyStack every time you need an empty stack. A single static instance can be used. Additionally StackFactory can be avoided by having a static factory method in EmptyStack.

public class EmptyStack<E> implements Stack<E> {
 private static final Stack<?> INSTANCE = new EmptyStack<>();
 @SuppressWarnings("unchecked")
 public static <X> Stack<X> instance() {
 return (Stack<X>) INSTANCE;
 }
 private EmptyStack() {}
 // ...
}

For a nicer API, I'd add a static empty() method to the Stack interface:

public interface Stack<E> {
 public static <X> Stack<X> empty() {
 return EmptyStack.instance();
 }
 // ...
}