引き続き、「みんなのデータ構造」という本を読む。
みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート
これまでのメモ
今回は「P35. 2.4 ArrayDeque 配列を使った高速な双方向キュー」。
TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ArrayDeque.ts
メモ
ArrayDeque とは
- ArrayStack、ArrayQueue と同じく、List インターフェースを実装したデータ構造の1つ
- List インターフェースとは...は こちらを参照
- 両端に対しての追加と削除が効率的にできるデータ構造
ArrayDeque の実行時間
get(i)およびset(i, x)の実行時間はO(1)add(i, x)およびremove(i)の実行時間はO(1 + min{i, n - i})resize()を考慮しても、resize()の実行時間は m 回の操作でO(m)なので、O(1 + min{i, n - i})
ArrayDeque の考え方
基本的にはArrayQueueと同じ。循環配列を用いる。
ArrayQueue との違いとして、ArrayDeque では配列の 両端から 要素の追加と削除を効率よく実行できる必要がある。
これを実現するため、 add(i, x) および remove(i) では、 i < n / 2 かどうかを確認する。
つまり、追加／削除しようとしている場所が、配列全体の左半分なのか右半分なのかで場合分けする。
i < n / 2 の場合、配列の左端から i 個の要素を1つずつ左にずらす。
そうでない場合、配列の i 番めから右端までの n - i 個の要素を1つずつ右にずらす。
こうすると、 add(i, x) または remove(i) における操作の回数は min{i, n - i} となる。
i = 0 のときも i = n のときも操作回数が少なく済むことがわかる。
疑問など
add/remove のサンプルコード内のコメント、実際には a[0],... ではなく a[j % a.length],... な気がする。
