「みんなのデータ構造」学習メモ：2.3 ArrayQueue

引き続き、「みんなのデータ構造」という本を読む。
みんなのデータ構造（紙書籍+電子書籍） – 技術書出版と販売のラムダノート

amazon

みんなのデータ構造

前回

• 「みんなのデータ構造」学習メモ：2.1 ArrayStack

今回は「P32. 2.3 ArrayQueue 配列を使ったキュー」。

TypeScript によるソースコード
https://github.com/zaki-yama/open-data-structures-typescript/blob/master/src/ArrayQueue.ts

メモ

ArrayQueue とは

• 前回の ArrayStack と同じく、List インターフェースを実装したデータ構造の1つ
  • List インターフェースとは...は 前回参照
• いわゆるキュー。入れた順に取り出す（FIFO）
  • イメージは「コンビニのレジに並ぶ列」

ArrayQueue の実行時間

• add(i, x) および remove(i) の実行時間は
  • resize() を考慮しなければ O(1)
  • resize() も m 回の操作で O(m) なので、resize() を考慮すると O(1 + 1) ？（特に明言なし）

FIFO Queue の実装に ArrayStack が適切でない理由

ArrayStack は配列のどちらか一方からの要素の追加／削除を高速に行えることを考えればよかった。
これに対し、ArrayQueue はどちらか一方から要素の追加、もう一方から要素の削除となる。
ので、ArrayStack で実現すると要素の追加または削除の必ずどちらかで全要素の移動が発生する。

すなわち要素数 n に比例する実行時間がかかってしまい効率が悪い。

どうするか

もし、無限長の配列があれば効率的なキューを簡単に実装できる。

• j: 次に remove する要素のインデックス
• n: 配列内の要素数

だけを持っていればいいはず。

実際には無限長というのは現実的でないため、これを 剰余算術 で模倣する。
剰余算術とはXをYで割った余り、mod のこと。

インデックス j を配列 a の長さで割れば、必ず余り j % a.length は配列のサイズ内 0, ..., a.length - 1 におさまることを利用する。

このような配列 a を循環配列を呼ぶ。

a, j, n に具体的な数字を用いた例：

こうすれば、

• 要素の追加（add(x)）
  • 循環配列の末尾 a[(j+n) % a.length] に要素を追加
  • n++
• 要素の削除（remove()）
  • インデックス j の位置の要素 a[j] を削除
  • j を1つずらす。 (j + 1) % a.length となる
  • n--

というわけで、add/remove の実行時間は要素数によらず定数時間になる。

resize() については ArrayStack と同じ考え方。

疑問

ArrayStack のときのように任意のインデックスに対する add(i, x)/remove(i) とせず、add(x)/remove() 決め打ちだったのはなんでだろう。
たぶん次の 2.4 ArrayDeque のための前置きのような位置付けでさらっと終わってるんだと思うが、納得感がなかった。