Realtime Queue
Operations
$ \mathtt{new}()
空の queue を作成する
時間計算量$ \Theta(1) 空間計算量$ \Theta(1)
$ \mathtt{front}()
先頭要素を取得する
時間計算量 $ \Theta(1)
$ \mathtt{push}(x)
x を末尾に追加した queue を作成する
時間計算量$ \Theta(1) 空間計算量$ \Theta(1)
$ \mathtt{pop}()
先頭要素を削除した queue を作成する
時間計算量$ \Theta(1) 空間計算量$ \Theta(1)
Summary
stack を 2 つ用いた queue をベースに、先頭側と末尾側の list が等しい長さになった時点で回転する (Banker's Queue)
回転操作をスケジュール化し、各操作毎に末尾側の回転と先頭側のコピーを進めることで最悪定数時間の操作を実現する
References
Notes
list の遅延評価は手続き型言語的には破壊的にリストを構築することに対応している
償却計算量になっても構わないならば、回転を必要になるまで行わないことで少し楽になるかもしれない (Implementaions の実装例はその方針)
先頭への push にも対応できるようだが、回転のタイミングをスケジュールに任せていると不可能？ (要検証)
Implementations