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

Question

我在一次采访中问过这个问题。复制它。

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

我已经回答了，但不确定那是否是最好的 w.r.t.空间复杂度。

Answer 1

doubly Linked List可以提供。

通过同时指向头部和尾部的指针，您可以有效地实现 dequeue() 和 pop()(O(1) ).

类似于以下内容:(假设垃圾收集语言和简化版本，不是 null/empty 安全的):

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)空间，很容易看出任何次线性解决方案都无法存储所有数据——并且在某些情况下会失败。