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 is, that it contains no if-statements, no method is longer than one line and that 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! :]