作为持久数据结构实现的堆栈

Question

在阅读了一些关于不可变性的文章之后，我发现有持久数据结构。在下面，我实现了一个堆栈作为一个持久的数据结构。

我喜欢当前状态下的代码

• 它包含不，如果-陈述
• 没有一种方法比一行长。
• 它像递归一样工作。

Implementation

该实现基于抽象Stack，它有两种具体的数据类型：EmptyStack和NonEmptyStack。Stack需要实现4种方法，如下所述。

public interface Stack {

    /**
     * @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 push(E top);

    /**
     * removes the top element of the {@code Stack}
     *
     * @return a {@code Stack} without the top element
     */
    Stack pop();

    /**
     * @return if {@code Stack} is empty {@code Optional.empty};
     * otherwise {@code Optional.of(E)} where {@code E} is the top element
     */
    Optional top();
}

EmptyStack表示基本情况:当Stack没有元素时。对于每个方法，很容易预测所有返回值：

• size总是0
• push()将始终返回一个带有新top元素和当前实例的NonEmptyStack，作为前一个版本。
• pop()不能返回顶级元素，因此它总是返回一个EmptyStack
• top()不能返回顶级元素，因此它总是返回一个Optional.empty

class EmptyStack implements Stack {

    @Override
    public int size() {
        return 0;
    }

    @Override
    public Stack push(E top) {
        return new NonEmptyStack<>(top, this);
    }

    @Override
    public Stack pop() {
        return this;
    }

    @Override
    public Optional top() {
        return Optional.empty();
    }

}

另一方面，还有NonEmptyStack，它表示包含元素的Stack。NonEmptyStack由顶部的元素组成，Stack作为其尾部，表示以前的版本。

• 对于新的top元素，size总是上一个版本加1的大小。
• push()将始终返回一个带有新top元素和当前实例的NonEmptyStack，作为前一个版本。
• pop()总是返回尾部
• top()总是返回表示顶部的元素，因为它可以是null，所以我使用了Optional.ofNullable

class NonEmptyStack implements Stack {

    private final Stack tail;
    private final E top;

    NonEmptyStack(E top, Stack tail) {
        this.tail = tail;
        this.top = top;
    }

    @Override
    public int size() {
        return 1 + tail.size();
    }

    @Override
    public Stack push(E top) {
        return new NonEmptyStack<>(top, this);
    }

    @Override
    public Stack pop() {
        return tail;
    }

    @Override
    public Optional top() {
        return Optional.ofNullable(top);
    }

}

EmptyStack和NonEmptyStack是包私有的，因此客户端只与Stack交互，而不是与D62的两种不同实现交互。为此，我创建了一个工厂StackFactory，它以Stack的形式返回EmptyStack，客户端从不直接与具体实现交互。

public class StackFactory {

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

}

单元测试

import org.junit.jupiter.api.Test;

import java.util.Optional;

import static org.junit.jupiter.api.Assertions.*;

class EmptyStackTest {

    private final Stack 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 stack = EMPTY_STACK.push("first");
        // assert
        assertTrue(stack instanceof NonEmptyStack);
    }

    @Test
    void givenAnEmptyStack_whenRemoveTheFirstElement_thenExpectAnEmptyStack() {
        // arrange
        // act
        Stack stack = EMPTY_STACK.pop();
        // assert
        assertTrue(stack instanceof EmptyStack);
    }

    @Test
    void givenAnEmptyStack_whenAccessTopElement_thenExpectItDoNotExists() {
        // arrange
        // act
        Optional 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 stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
        // act
        int size = stack.size();
        // assert
        assertEquals(1, size);
    }

    @Test
    void givenNonEmptyStackWitOneItemAndANewItem_whenInstantiateAndQueryTheSize_thenExpect2() {
        // arrange
        NonEmptyStack nonEmptyStack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
        Stack stack = new NonEmptyStack<>(ITEM, nonEmptyStack);
        // act
        int size = stack.size();
        // assert
        assertEquals(2, size);
    }

    @Test
    void givenEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
        // arrange
        Stack stack = new EmptyStack<>();
        // act
        Stack nonEmptyStack = stack.push(ITEM);
        // assert
        assertEquals(Optional.of(ITEM), nonEmptyStack.top());
    }

    @Test
    void givenNonEmptyStackAndItem_whenPushTheItemToTheStack_thenTheItemShouldBeInTheStack() {
        // arrange
        Stack emptyStack = new EmptyStack<>();
        Stack firstChange = emptyStack.push("value");
        // act
        Stack stack = firstChange.push(ITEM);
        // assert
        assertEquals(Optional.of(ITEM), stack.top());
    }

    @Test
    void givenNonEmptyStackWithOneItem_whenRemoveTheTopItem_thenExpectEmptyStack() {
        // arrange
        Stack testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>());
        // act
        Stack stack = testCandidate.pop();
        // assert
        assertTrue(stack instanceof EmptyStack);
    }

    @Test
    void givenNonEmptyStackWithTwoItems_whenRemoveTheTopItem_thenExpectNonEmptyStack() {
        // arrange
        Stack testCandidate = new NonEmptyStack<>(ITEM, new EmptyStack<>()).push(ITEM);
        // act
        Stack stack = testCandidate.pop();
        // assert
        assertTrue(stack instanceof NonEmptyStack);
    }

    @Test
    void givenNonEmptyStack_whenQueryTopItem_thenExpectTopItem() {
        // arrange
        Stack stack = new NonEmptyStack<>(ITEM, new EmptyStack<>());
        // act
        Optional top = stack.top();
        // assert
        assertEquals(Optional.of(ITEM), top);
    }

}

示例

public class Main {

    public static void main(String[] args) {

        Stack stack = new StackFactory().create()
                                                        .push("first")
                                                        .push("second")
                                                        .push("third");

        Stack modified = stack.pop()
                                      .pop();

        modified.top()
                .ifPresent(System.out::println); // "first"

        modified.pop()
                .top()
                .ifPresent(System.out::println); // nothing happens 

    }
}

这个小实验很有趣。非常感谢您的反馈，非常感谢您阅读我的代码！:]

Answer 1

在这个实现中，null条目是有问题的。从公共接口中，无法判断堆栈是否有空项，或者已经到达底部:在这两种情况下，top()都将返回Optional.empty()。

悄悄地把nulls变成Optional.empty()s似乎是不对的。我会做以下几件事之一：

1. 不要在堆栈中存储null条目。相反，在push上抛出一个null值异常。
2. 停止使用Optionals，而是在空堆栈上调用top时抛出异常。添加empty方法以确定堆栈是否为空。

除此之外，非常干净的简单代码！一些较小的评论。

注意，push在EmptyStack和NonEmptyStack中都有相同的实现。如果您愿意，它们可以从实现push的单个抽象类继承。这是一个判断调用:重复的代码有点糟糕，但是添加一个全新的抽象类是很复杂的。也许治愈方法比疾病更糟糕..。

计算size是缓慢的:时间O(n)。如果您担心这一点，可以在构造函数中计算和存储大小。

Answer 2

为了创建一个StackFactory而实例化Stack的需要似乎是多余的。我建议将create()作为一个static方法，这反过来意味着，与类StackFactory不同，需要一个类型参数的是方法create()：

public class StackFactory {

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

然后，您可以这样调用该方法：

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

请注意，在上面的示例中，您需要显式地将类型参数String传递给方法create()，因为新创建的Stack没有直接分配给类型Stack的变量，因此编译器无法推断调用方法 create()为String的类型参数E。

Answer 3

我想指出，每次需要空堆栈时，都没有必要创建EmptyStack的新实例。可以使用单个静态实例。此外，可以通过在StackFactory中使用静态工厂方法来避免EmptyStack。

public class EmptyStack implements Stack {

    private static final Stack INSTANCE = new EmptyStack<>();

    @SuppressWarnings("unchecked")
    public static  Stack instance() {
        return (Stack) INSTANCE;
    }

    private EmptyStack() {}

    // ...

}

为了获得更好的API，我将向Stack接口添加一个静态的D5方法：

public interface Stack {

    public static  Stack empty() {
     return EmptyStack.instance();
    }

    // ...
}