改进数据结构

Question

如果我有一个像堆栈一样的数据结构，我使用双链表来实现，我还添加了一个始终保持中间元素的指针。

我想通过添加一个方法peekAt（k）来修改它，它将返回O（log（k））中第K个插入的元素。

任何想法，我该怎么办呢？谢谢。

Answer 1

如果将它实现为double linked list，则不能在O(log(k))时间返回k-th elementh，因为链接列表不具有对元素的随机访问权限。我建议将您的堆栈作为(dynamic) array而不是您可以实现的O(1)访问。

编辑：

如果你也快insertion/deletion希望在任何地方，那么我建议使用一个balanced binary tree。