<分区>
我遇到了这个问题，想问问实现这个目标的最佳方法是什么。
给定一个 FIFO 队列。您可以假设队列包含整数。每次发生插入或删除时，都会创建一个新版本的队列。在任何时候，您都必须以最小的时间和空间复杂度打印(队列的全部内容)队列的任何旧版本。
标签 algorithm
<分区>
我遇到了这个问题，想问问实现这个目标的最佳方法是什么。
给定一个 FIFO 队列。您可以假设队列包含整数。每次发生插入或删除时，都会创建一个新版本的队列。在任何时候，您都必须以最小的时间和空间复杂度打印(队列的全部内容)队列的任何旧版本。
最佳答案
这是假设您指的是 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]
^ ^
要打印一个版本，您只需要为每个版本存储两个值:指针所在的位置。在该版本中，打印与队列大小成线性关系。
向量可以变大，但如果您希望能够打印任何版本，则必须存储其中曾经存在的每个元素。
如果您认为这是一个问题，您也可以使用链表来避免调整数组大小。删除时确保不要从内存中删除节点。
关于algorithm - 打印队列的任何旧版本，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18293084/