java - 持久队列数据结构

Question

我需要创建一个持久队列类，其中 enqueue 函数将一个元素放入当前队列并返回新队列。原始队列如何保持不变。类似地，dequeue 函数删除前面的元素并返回新队列，但原始队列保持不变。这当然可以在 O(队列长度)内完成，但我可以更快地完成吗？？

Answer 1

您可以使用链表作为队列(不是 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)。

请注意，您只能以相反的顺序迭代此队列(即最新的元素在前)。也许您可以想出一些可以反向迭代甚至双向迭代的东西。