読者です 読者をやめる 読者になる 読者になる

出、出~~wwwww銀行員待行列解説奴~wwwwwww

銀行員待行列(Banker's deque)、二つのリストで構成奴~~wwwww

入奴と出奴~wwwwwwwww

          ↓入奴

三(^o^)ノ [(^o^)ノ, (^o^)ノ, (^o^)ノ]

ヽ(^o^)三 [ヽ(^o^), ヽ(^o^), ヽ(^o^)]

          ↑出奴

追加は入奴にcons、取り出しは出奴にuncons奴~wwwリストなので基本定数時間奴~wwwwww

リスト枯渇防止の為、リストの長さに以下の条件課奴~~~wwwwww

length (入奴) <= length (出奴) * 3 + 1
length (出奴) <= length (入奴) * 3 + 1

条件充足不能場合、|length (入奴) - length (出奴)| <= 1なるよう余剰分反転後短い側の末尾に結合して調整奴~wwwww時間計算量O(length (入奴) + length (出奴))必要~~~~wwwwww

動作奴~wwww個数nのリストを[n]表記奴~wwwwwww

入、入~~wwwww調整奴~~wwwwww

[1][1]

入、入、入~wwwww調整不要~wwwwwwww

[4][1]

入~~wwwwwここで調整奴~~wwwwwww

[5][1] → [3][3]

入、入、入、入、入入入入~wwwwww再度調整奴~wwwwww

[11][3] → [7][7]

入入入入入入入入入入入入入入入入wwwwwwww調整必要奴~wwwwwww

[23][7] → [15][15]

入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入~~wwwwwww調整奴~wwwwwww

[47][15] → [31][31]

入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入~~wwwwwwwやっと調整奴~wwwwwww

[95][31] → [63][63]

調整間隔指数関数的増大奴~wwwwwwwww

相対的調整コスト、限りなく0に漸近奴~~~wwwww

\displaystyle
\sum_{k=0}^{\infty} \frac{1}{a^k} (a \gt 1)
収束故、償却定数時間奴~~~~wwwwwwwww

取り出しも同様奴~wwwwwww

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~~~~wwwwwww

[63][20] → [41][40]

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出~wwwwww

[40][12] → [26][26]

長ければ長いほど調整コスト相殺奴~~wwwwwwwwww

実装簡単、効率的データ構造奴~~~wwww

参考文献奴~wwwww

  • Chris Okasaki (1999). Purely Functional Data Structures