常量时间中Push,Pop和Dequeue操作的自定义数据结构

Question

我在一次采访中问了这个问题.再现它.

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

我已回答,但不确定这是否是最好的空间复杂性.

Answer 1

双重链表可以提供它.

通过指向头部和尾部的指针,您可以实现两者dequeue()并pop()有效地实现(O(1)).

类似的东西:(假设垃圾收集语言,简化版本,非null /空安全):

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