Physicist's Queue

Operations

$ \mathtt{empty}()

空の queue を作成する

時間/空間計算量$ \Theta(1)

$ \mathtt{head}()

先頭要素を取得する

時間計算量$ \Theta(1)

$ \mathtt{snoc}(x)

$ xを末尾に追加した queue を作成する

時間/空間計算量$ \Theta(1) \ {\rm amortized}

$ \mathtt{tail}()

先頭要素を削除した queue を作成する

時間/空間計算量$ \Theta(1) \ {\rm amortized}

Summary

Banker's Queue などと同様, 2 本の list で queue を管理し, 先頭側が末尾側より短くなったときに回転する.

$ \mathtt{head}に対応するため作業用リストを保持し, 回転などのタイミングで更新する.

$ \Psi = \min(2|W|, |F|-|R|)とすることで物理学者法で解析できる.

References

Okasaki, C. (1999). Purely functional data structures. Cambridge University Press.

Implementations

Problems