2015-02-05

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

入奴と出奴～ｗｗｗｗｗｗｗｗｗ

　　　　　　　　　　↓入奴

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

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

　　　　　　　　　　↑出奴

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

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

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

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

動作奴～ｗｗｗｗ個数nのリストを[n]表記奴～ｗｗｗｗｗｗｗ

入、入～～ｗｗｗｗｗ調整奴～～ｗｗｗｗｗｗ

[1][1]

入、入、入～ｗｗｗｗｗ調整不要～ｗｗｗｗｗｗｗｗ

[4][1]

入～～ｗｗｗｗｗここで調整奴～～ｗｗｗｗｗｗｗ

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

入、入、入、入、入入入入～ｗｗｗｗｗｗ再度調整奴～ｗｗｗｗｗｗ

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

入入入入入入入入入入入入入入入入ｗｗｗｗｗｗｗｗ調整必要奴～ｗｗｗｗｗｗｗ

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

入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入～～ｗｗｗｗｗｗｗ調整奴～ｗｗｗｗｗｗｗ

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

入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入入～～ｗｗｗｗｗｗｗやっと調整奴～ｗｗｗｗｗｗｗ

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

調整間隔指数関数的増大奴～ｗｗｗｗｗｗｗｗｗ

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

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

取り出しも同様奴～ｗｗｗｗｗｗｗ

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出出～～～～ｗｗｗｗｗｗｗ

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

出出出出出出出出出出出出出出出出出出出出出出出出出出出出出～ｗｗｗｗｗｗ

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

長ければ長いほど調整コスト相殺奴～～ｗｗｗｗｗｗｗｗｗｗ

実装簡単、効率的データ構造奴～～～ｗｗｗｗ

参考文献奴～ｗｗｗｗｗ