持久化队列数据结构

Question

我需要创建一个持久队列类，其中函数enqueue接受一个元素并将其加入当前队列，并返回新队列。但原始队列保持不变。同样，dequeue函数删除前面的元素并返回新队列，但原始队列保持不变。这当然可以在O（队列长度）内完成，但我能否更快地完成？

- Aditya Nambiar

---

你需要不可变队列有什么原因吗？ - Njol

@Gab 是的，因为回答无用的问题是没有意义的。如果我们知道提问者的意图，就可以建议比提问者最初打算采取的更好的方法来完成任务。 - Njol

回到主题上来：我认为你无法在不对每个元素进行迭代的情况下复制任何集合的每个元素。因此，对我来说，比O（n）更好似乎是不合理的。 - ccjmne

我们在家里得到了这个东西，但我就是想不明白。 - Aditya Nambiar

@ccjmne 我们不能将返回值放入队列中，然后再将其删除吗？我知道在返回后执行会停止，但有没有绕过这个问题的方法？ - Aditya Nambiar

@AdityaNambiar 我会尽量避免必须删除它，可以看看我的回答。 - Peter Lawrey

Answer 1

我建议查看 Scala 实现。类顶部的注释描述了所选方法（复杂度：O(1)）。

Queue 是由一对 List 实现的，其中一个包含“in”元素，另一个包含“out”元素。
元素添加到“in”列表中并从“out”列表中移除。当“out”列表用尽时， 队列通过将“out”列表替换为“in.reverse”，将“in”替换为“Nil”而进行旋转。

将项目添加到队列中始终具有成本 O(1)。删除项目的成本为 O(1)，除非需要进行旋转，在这种情况下，会产生 O(n) 的成本，其中 n 是队列中元素的数量。当发生这种情况时，保证有 n 个具有 O(1) 成本的删除操作。删除项目的平均成本为 O(1)。

http://xuwei-k.github.io/scala-library-sxr/scala-library-2.10.0/scala/collection/immutable/Queue.scala.html

- Gab

Answer 2

你可以使用链表作为队列（不是 LinkedList，而是你自己的实现）。

添加新元素时，只需创建一个新的队列类实例，将其起始元素设置为复制的队列的起始元素，并创建一个新的结束元素。

删除元素类似，但将新队列的结束元素设置为复制队列的倒数第二个元素。

队列类可能如下所示：

static class Node {
    final Node next;
    final Object o;
    Node(Node next, Object o) {...}
}

final Node start, end;

private Queue(Node start, Node end) {...}

public Queue(Object o) {
    start = end = new Node(null, o);
}

public Queue add(Object o) {
    return new Queue(start, new Node(end, o));
}

public Queue remove() {
    return new Queue(start, end.next);
}

这个队列的add和remove方法的复杂度为O(1)。

请注意，您只能按相反的顺序（即最新的元素优先）迭代此队列。也许你可以想出一些可以从另一方向甚至在两个方向上迭代的东西。

- Njol

---

一个双向链表应该允许你在两个方向上进行迭代。 - Peter Lawrey

@PeterLawrey 但是这样你就无法以O(1)的时间复杂度添加或删除节点了，因为你需要复制每个节点（如果我的代码被天真地扩展了一个新的“Node previous”）。 - Njol

好的观点。每个队列都需要有自己的前一个字段。如果您只有一个生产者，这将不是太大的问题。 - Peter Lawrey

Answer 3

我所使用的是Java Chronicle（免责声明：这是我编写的）。这是一个无界的非堆持久队列，存储在磁盘或tmpfs（共享内存）上。

在这种方法中，您的消费者跟踪队列中的位置，但实际上没有删除任何条目（除了每日或每周维护周期）。

这避免了除添加到队列之外的修改队列的需要，也不需要复制它。

因此，对于每个消费者，维护多个引用以确定每个消费者认为是队列尾部的位置是O（1）。

由于Chronicle使用紧凑的二进制形式，您可以存储的数据量受限于磁盘空间。例如，即使在具有8 GB内存的计算机上，2 TB驱动器也可以存储这么多数据，然后您必须旋转队列日志。

- Peter Lawrey

---

使用这种方法，您无法在不修改数据结构的情况下添加元素。 - Njol

如果需要的话，您也可以记录结束位置。要拍摄快照，您只需要知道起始和结束位置即可，时间复杂度为O(1)。问题只会在您想要添加到多个快照并且不能应用任何排队消息过滤器时出现。 - Peter Lawrey