DualArrayDeque

Dequeは先頭と末尾がO(1)で処理できるやつ。ArrayStackは末尾の追加・削除がO(1)…それだったらArrayStackを向かい合わせにすれば良いじゃない！というデータ構造。

(kcatSyarrAの目つ１) | (2つ目のArrayStack)

みたいな感じで配置する。

https://gyazo.com/cd87f37247c0ef7d6bd78d99978a82af

みたいに左右のバランス調整も行われる。balanceは要素を全部ずらすので要素数をnとしたとき計算量はO(n)になる。

balanceする条件は「左右のいずれかの要素数が全体の要素数nの1/4未満になったとき」

https://gyazo.com/a92e07ee9d46f7f753192f1e94d5150e

この図を睨むと前回のbalance()を発動した直後から今回balanceを発動する直前までに、n/2 - 1 回以上addが行われていることがわかる。詳しいのはポテンシャルΦを使ったp.42の証明を読みましょう