algorithm - 用于在恒定时间内推送、弹出和出列操作的自定义数据结构

Question

我在一次采访中问过这个问题。再现它。

编写自定义 DS，其中 Push()、Pop() 和 Dequeue() 操作将在恒定时间内完成。例如输入是 1,2,3,4 然后我们调用 pop()，应该返回 4。如果我们调用 dequeue，应该返回 1。O(1) 中的所有内容。

我已经回答了，但不确定这是否是最好的空间复杂性。

Answer 1

双向链表可以提供。

dequeue()通过同时指向 head 和 tail 的指针，您可以有效地实现两者pop()( O(1))。

类似于以下内容：（假设垃圾收集语言和简化版本，不是空/空安全）：

push(e):
  n = new Node(e)
  last.next = n
  n.previous = last
  last = n       
pop():
  e = last.value
  last.previous.next = null
  last = last.previous
  return e
dequeue():
  e = head.value
  head = head.next
  head.previous = null
  return e

关于空间复杂度：
解决方案是Theta(n)空间，很容易看出任何亚线性解决方案都无法存储所有数据 - 并且在某些情况下会失败。