改進數據結構

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。