algorithm - 打印队列的任何旧版本

Question

我遇到了这个问题，并想问什么是实现这一目标的最佳方法。

给定一个 FIFO 队列。您可以假设队列包含整数。每次插入或删除时，都会创建一个新版本的队列。在任何时候，您都必须以最小的时间和空间复杂度打印（队列的全部内容）任何旧版本的队列。

Answer 1

这是假设您的意思是 FIFO 队列而不是其他类型的队列，例如优先级队列。

将其存储在一个数组中并保留两个指针变量，一个指向其头部，另一个指向其尾部。

例如：

insert 3 2 5 9 - version 1
q = [3 2 5 9]
     ^     ^
delete, delete - version 2
q = [3 2 5 9]
         ^ ^
insert 6 3 4 - version 3
q = [3 2 5 9 6 3 4]
         ^       ^

要打印一个版本，您只需要为每个版本存储两个值：指针所在的位置。然后，打印在该版本的队列大小中是线性的。

矢量可以变大，但如果您希望能够打印任何版本，则必须存储其中曾经存在的每个元素。

如果您认为这是一个问题，您还可以使用链表来避免数组大小调整。只要确保在删除时不要从内存中删除节点。

Answer 2

您的问题是使队列成为部分持久的数据结构。

部分持久化意味着您可以查询任何版本，但您只能在最新版本中进行更新。

几年前，我发表了关于使任何指针数据结构持久化的演讲。它基于Driscoll、Sarnak、Sleator 和 Tarjan 的“使数据结构持久化”。

显然，任何队列都可以实现为链接数据结构。如果您想要最简单的实用版本，您可能会对上述 PDF 中第 91 页中描述的称为“胖节点方法”的方法感兴趣。

这个想法是在每个节点中存储几个指向对应于不同版本队列的下一个元素的指针。每个指针都分配了一个版本号，称为时间戳。

对于每个插入或删除操作，您只更新更新操作触及的节点中的指针。

对于队列版本中的查找操作i-th，您只需遵循最大时间戳不超过的指针i。您可以使用二进制搜索找到要跟随的指针。

在给定的 PDF 中，还有一种更复杂但也更有效的方法，称为“节点复制方法”。

Answer 3

有许多可能的解决方案。这是一个保证所有操作O(log(n))和正常操作摊销的操作O(log(log(n))。

保留一个操作计数器。根据插入操作的顺序将项目存储在跳过列表中（有关其定义，请参见http://en.wikipedia.org/wiki/Skip_list ）。当一个元素被移除时，填写移除操作的id。为了访问效率，保留一对指向当前头部和当前尾部的指针。

要插入一个元素，请将其添加到当前尾部。要返回一个元素，请将其返回到当前头部。要返回过去的状态，请在跳过列表中搜索 then 头部，然后开始遍历列表，直到您阅读 then 尾部。

这里的log(n)操作是找到过去的头，并且（非常偶尔地）插入一个恰好是跳过列表中高节点的新头。

Answer 4

现在让我们假设在一个 FIFO 队列中，头指针位于数组的开头，而尾指针位于当前插入的末尾。然后通过将当前尾部位置指针值存储在一个变量中，该变量在未来插入期间用作头部指针位置，并且尾部位置再次结束该插入。这样，只需使用单个变量并且只进行插入，就可以从数组的开头打印到尾指针的先前版本。

insert 3 2 1 4
a=[3 2 1 4]  --version 1    
   ^     ^ 
   b     e
p = e;


insert 5 7 8
a=[3 2 1 4 5 7 8] --version 2    
           ^   ^
           b   e
here version 1 = position 0 to position p = [3 2 1 4]
p = e;

delete 3
a=[2 1 4 5 7 8] --version 3    
         ^   ^
         b   e
here version 2 = position 0 to position p =[2 1 4 7 8]

where
b = beginning 
e = end

因此，通过使用单个变量来保存以前版本的尾部位置并假设开始位置始终为 0 ，可以轻松打印以前的版本。