はじめに

KotlinでListをサクッとQueueに変換したくて出会ったクラスArrayDeque

↓公式

ちゃんと調べると、QueueだけでなくStackとしても、さらにListとしても扱えるようだったので整理してみます。

ちなみにJavaにもArrayDequeはあるのですが、今回はそちらには触れません。

環境

今回の記事を書いている環境はこちらです

Kotlin: 1.9.22
JVM: 21.0.5 (Amazon.com Inc. 21.0.5+11-LTS)
OS: Mac OS X 15.1.1 aarch64

データ構造

そもそもQueueとかStackってなんだっけ

Queue（キュー）はFIFO（First In First Out）つまり最初に入った要素が最初に取り出せる「先入れ先出し」の構造を持つコレクション。ところてんがよく例として出てくるやつですね。（今の若い人にも伝わるのだろうか、、）
コレクションから取り出した要素は基本的に削除されるのも特徴かな。

対してStack（スタック）はLIFO（Last In First Out）つまり最後に入った要素が最初に取り出せる「後入れ先出し」の構造。カゴなどであれば、ものが上に積まれていくので最後に積んだものを最初に取り出せる。そんなイメージ。
こちらも取り出した要素は基本的に削除される。

ArrayDeckって何?

ArrayDequeの公式ドキュメント冒頭にはこんな風に書かれています。

dequeデータ構造の可変長配列による実装。
dequeという名前は"double ended queue（両端キュー）"の略で、通常は "deck（デック）"と発音する。
コレクションは、両端へアクセスするための便利なメソッドを提供する。またMutableListインターフェイスを実装しているので、インデックスによる効率的なget/set操作もサポートしている。

簡単に言うと、deque（両端キュー）は先頭と末尾どちらからも要素を追加できるし、どちらからも取り出せるということです。
加えてMutableListでもあるので、インデックス指定で要素を追加したり取り出したりもできると。

ちょっと不思議な感じです。

初期化

ListやSetなどのコレクションをコンストラクタに渡して初期化するのがベーシックかな。

// 1,2,3のリストをArrayDequeにする
val deque = ArrayDeque(listOf(1, 2, 3))

コンストラクタに数値（Int）を渡すこともできる。
事前に必要なサイズ数が分かっている場合のパフォーマンス最適化などで使われる。

// 事前に1,000要素分のサイズを確保
val deque = ArrayDeque<Int>(1000)

何も渡さないと空になる。

// 空のArrayDeque
val deque = ArrayDeque<Int>()

要素の追加

addFirst(element)で先頭に要素を追加する。戻り値はない（Unit）。
先頭への追加は、単方向のQueueやStackにはない動き。

val deque = ArrayDeque(listOf(1,2,3))
deque.addFirst(10)
// deque: [10, 1, 2, 3]

addLast(element)で末尾に要素を追加する。これも戻り値はない（Unit）。
Queueでいうenqueue（エンキュー）や、Stackでいうpush（プッシュ）。

val deque = ArrayDeque(listOf(1,2,3))
deque.addLast(10)
// deque: [1, 2, 3, 10]

インデックス指定

単なるadd(element)でBooleanを返す関数もあり、こちらは末尾に追加する。
また、追加先をインデックス指定できる関数add(index, element)もある。戻り値はない。

val deque = ArrayDeque(listOf(1,2,3))
deque.add(10)
deque.add(2, 20)
// deque: [1, 2, 20, 3, 10]

これらはList由来の関数ですね。

要素の取り出し

removeFirst()で先頭の要素を取得して取り除く。
Queueでいうところのdequeue（デキュー）。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.removeFirst()
// elm: 1, deque: [2, 3]

removeLast()で末尾の要素を取得して取り除く。
Stackでいうところのpop（ポップ）。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.removeLast()
// elm: 3, deque: [1, 2]

取り出せる要素がないとき

ちなみに要素が空だと、どちらもNoSuchElementExceptionをスローする。
これを避けるためにremoveFirstOrNull()やremoveLastOrNull()が提供されている。この場合、空だったらnullが返ってくる。

val deque = ArrayDeque<Int>()
deque.removeLast()       // NoSuchElementException
deque.removeLastOrNull() // null

インデックス指定

ListとしてremoveAt(index)でインデックスを指定して要素を取り出すことができる。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.removeAt(1)
// elm: 2, deque: [1, 3]

他のListと同様、removeAtOrNull()という関数はない。

要素の参照

「参照」は「取り出し」とは異なり、コレクションから要素を取り除かない。

first()で先頭の要素を参照できる。
Queueでいうところのpeek（ピーク）。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.first()
// elm: 1, deque: [1, 2, 3]

last()で末尾の要素を参照できる。
Stackにおけるpeek（ピーク）。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.last()
// elm: 3, deque: [1, 2, 3]

参照できる要素がないとき

参照の場合も、要素が空だとNoSuchElementExceptionをスローする。
firstOrNull()やlastOrNull()が提供されているので、これらを使えば、空だったとしてもnullが返ってくる。

val deque = ArrayDeque<Int>()
deque.first()       // NoSuchElementException
deque.firstOrNull() // null

インデックス指定

Listのようにget(index)でインデックスを指定して要素を参照できる。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque.get(1)
// elm: 2, deque: [1, 2, 3]

インデックス演算子を使って配列のようにアクセスもできる。こちらの方が推奨。

val deque = ArrayDeque(listOf(1,2,3))
val elm = deque[1]
// elm: 2, deque: [1, 2, 3]

getOrNullも（一般的なListと同様に）用意されているので、範囲外のインデックスを指定した場合に例外ではなくnullが返ってくるようにもできる。

val deque = ArrayDeque(listOf(1,2,3))
deque[5]           // IndexOutOfBoundsException
deque.getOrNull(5) // null

まとめ

KotlinのArrayDequeについて簡単にまとめてみました。

両端キューとして先頭と末尾のどちらにもアクセスできるし、関数名もaddFirst,removeLastなど何が起こるか分かりやすいシンプルな名前でいいですね。
OrNull系の関数も用意されているので、nullの懸念がある時も回避しやすいのがKotlinらしくていいなと思いました。

必要に応じて適切なデータ構造を選択できるよう、引き出しの一つとして覚えておこうと思います。