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.

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();
    }

    // ...
}