algorithm - 一定時間でのプッシュ、ポップ、およびデキュー操作のカスタムデータ構造

Question

私はインタビューの1つでこの質問をしました。それを再現します。

Push（）、Pop（）、およびDequeue（）操作が一定時間で実行されるカスタムDSを記述します。たとえば、入力が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)スペースです。サブリニアソリューションではすべてのデータを保存できず、場合によっては失敗することが簡単にわかります。