algorithm - 设计数据结构就像改进堆栈一样

Question

我被要求设计一个数据结构，它像一个堆栈一样工作，不受大小限制，它将支持以下方法，具有给定的运行时限制。

push(s) - push s to the data structure - O(1)
pop() - remove and return the last element inserted O(1)
middle() - return the element (without removing) with index n/2 by insertion order where n is the current amount of elements in the data structure. - O(1)
peekAt(k) - return the kth element by insertion order (the bottom of the stack is k=1) - O(log(k))

我想过使用链表，并始终保留一个指向中间元素的指针，但后来我在实现 peekAt(k) 时遇到了问题。有什么想法可以实现吗？

Answer 1

如果 O(1) 限制可以放宽到分摊 O(1)，典型的可变长度数组实现就可以了。当你为当前长度为 N 的数组分配空间时，在最后保留说 N 额外的空间。一旦超出此边界，按照相同的策略重新分配新大小，将旧内容复制到那里并释放旧内存。当然，您必须同时维护堆栈的分配长度和实际长度。 middle 和 peekAt 操作可以在 O(1) 中轻松完成。

相反，如果需要的话，如果数组占用的空间少于分配空间的 1/4，您也可以缩小数组。

所有操作的摊销时间为 O(1)。准确的意思是，从一开始任意K次栈操作，一共要执行O(K)条指令。特别地，N 次推送后的重新分配次数为 O(log(N))，由于重新分配而复制的元素总数不会超过 1 + 2 + 4 + 8 ... + N <= 2N = O(N).

---

如果内存管理器的 allocate 和 free 在 O(1) 中执行，这可以渐进地更好地完成，每个操作都需要非摊销的 O(1)适用于任何尺寸。基本思想是维护当前分配的堆栈和 2x 更大的 future 堆栈，并提前开始准备更大的副本。每次将一个值压入当前堆栈时，再将两个元素复制到 future 堆栈中。当当前堆栈已满时，其所有元素都将已复制到 future 堆栈中。之后，丢弃当前堆栈，声明 future 堆栈现在是当前堆栈，并分配一个新的 future 堆栈(当前为空，但分配的比当前堆栈大 2 倍)。

如果您还需要收缩，当您的堆栈占用分配空间的 1/2 到 1/4 时，您可以以类似的方式维护一个较小的副本。

正如您从描述中看到的，虽然这在理论上可能更好，但它通常更慢，因为它必须维护堆栈的两个副本而不是一个。但是，如果您对每个操作都有严格的实时 O(1) 要求，则此方法会很有用。