Java中不可变的队列如何实现？ - XP123

函数式语言通常具有不可变的数据类型——一旦创建了对象，您就无法更改它，尽管您可以将其作为其他对象的一部分包含在内。不可变对象更容易推理，并防止代码的两部分认为它们具有更改数据的独占访问权限的错误。我们将研究一种使用两个Stack以不可变方式实现队列Queue的方法。

不可变的Stack
传统的堆栈Stack实现通常使用一个数组加上一个到当前顶部的偏移量，或者一个单链表，其中指向列表的指针指向顶部。
从不变性的角度来看，数组不是很好，因为它是一个旨在读取和更新的数据块。
基于列表的堆栈是更自然的选择。堆栈有两种可能性：

空堆栈，由 null 表示，-或-
包含内容的堆栈，由对包含值的单元格的引用和对堆栈其余部分的“下一个”引用表示。

要将对象压入堆栈，请为新单元分配数据，并将其指向当前的“顶部”单元。这不会影响现有堆栈。然后将顶部更改为指向刚刚分配的单元格。
要移除对象，请将顶部指针移至当前单元格中的“下一个”指针。这只会改变“顶部”。
因此，我们需要有一个堆栈，它占用的空间与项目的数量成正比，并且需要 O(1) 时间。（O(1) 意味着它使用固定的最大步数，并且永远不必循环其内容。）

传统的队列Queue
与堆栈Stack一样，传统队列有两种常见的实现方式：数组版本和列表版本。标记。我意识到这听起来很混乱。在一个真实的例子上追踪它，你就会明白它为什么有效。（有关更深入的讨论，请参阅参考资料中的“编程：使用隐藏的内容”。）
从不变性的角度来看，这两种方法都有缺陷：我们要么更新数组的内容，要么在现有单元格中处理指针。两者都不是一成不变的。
两种方法都需要 O(1) 来添加或删除，但都使用可变性。

从堆栈Stack派生除的队列Queue
我们想要一个不变的队列，它占用的空间与队列中的单元格数量成正比，添加或删除项目的时间复杂度为 O(1)。下面的两栈算法很接近。（我的灵感来自参考文献中Haskell 书中的版本。）
这个想法是你有两个堆栈：ins和outs两个Stack。每当您添加新项目时，就将其添加到ins堆栈中。每当您移除它时，您就将其从outs堆栈中移除。
删除显然是一个棘手的问题——对象如何进入outs堆栈以将其删除？诀窍是：如果你想删除，而outs堆栈中没有任何东西，那么首先从insto弹出所有内容outs，然后从中删除outs。
这是 Java 中的一个实现。它使用 Java Stack 类，它实际上是一个基于数组的实现，但这对我们来说并不重要。我们只关心它是一个 O(1) 堆栈。

public class Queue<T> {
    private Stack<T> ins = new Stack<>();
    private Stack<T> outs = new Stack<>();

    public boolean isEmpty() {
        return ins.isEmpty() && outs.empty();
    }

    public void insert(T item) {
        ins.push(item);
    }

    public T remove() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        if (outs.isEmpty()) {
           Queue.emptyStackTo(ins, outs);
        }
        return outs.pop();
    }

    private static <T> void emptyStackTo(
            Stack<T> ins, Stack<T> outs) {
        while (!ins.isEmpty()) {
            outs.push(ins.pop());
        }
    }
}

我们要求队列不变地工作。在我们的代码中，我们持有两个堆栈。这些都是不可变的，所以我们的队列也是不可变的。
大小应该与项目的数量成正比。堆栈告诉我们：每条数据都在两个堆栈之一中。所以使用的空间量是两个堆栈空间的总和。
最后，我们想要 O(1) 的性能。堆栈为我们提供了它们push()和pop()操作。我们add()只是调用了一个堆栈操作，所以它是 O(1)。不过，remove()比较麻烦。
Remove()在调用堆栈的 O(1) 之前，可能必须将一个堆栈清空到另一个堆栈中pop()。但是我们的复制操作可能必须在某个时候复制一整堆数据。这个副本与使用的空间成正比——我们称之为 O(n)，其中 n 代表项目的数量。这使得我们的操作 O(n)。
我发现这个算法在几个层面上很有趣：

我喜欢看到以不同方式实现的队列，没有数组或棘手的链表。
看看不变性如何改变数据结构很有趣。随着我们使用更多的函数式语言和更多的多线程系统，这样的技术将变得更加重要。（见Okasaki在参考文献）。
这是摊销时间界限的一个很好的例子。（这让我想知道我们是否可以以某种方式降低 O(n)。）