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

21-11-18 banq

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

 

不可变的Stack

传统的堆栈Stack实现通常使用一个数组加上一个到当前顶部的偏移量,或者一个单链表,其中指向列表的指针指向顶部。

从不变性的角度来看,数组不是很好,因为它是一个旨在读取和更新的数据块。

基于列表的堆栈是更自然的选择。堆栈有两种可能性:

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

要将对象压入堆栈,请为新单元分配数据,并将其指向当前的“顶部”单元。这不会影响现有堆栈。然后将顶部更改为指向刚刚分配的单元格。

要移除对象,请将顶部指针移至当前单元格中的“下一个”指针。这只会改变“顶部”。

因此,我们需要有一个堆栈,它占用的空间与项目的数量成正比,并且需要 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)。)

猜你喜欢