[Kotlin] ArrayDequeとは?: Queue・Stack・Listをひとつで扱えるコレクション

## はじめに

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

↓公式

https://kotlinlang.org/api/core/kotlin-stdlib/kotlin.collections/-array-deque/

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

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

https://docs.oracle.com/javase/jp/8/docs/api/java/util/ArrayDeque.html

### 環境

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

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などのコレクションをコンストラクタに渡して初期化するのがベーシックかな。

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

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

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

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

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

## 要素の追加

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

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

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

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

### インデックス指定

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


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

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


## 要素の取り出し

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

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

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


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

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

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

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

### インデックス指定

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

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

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


## 要素の参照

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

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

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

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

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

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

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

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

### インデックス指定

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

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

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

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

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

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

## まとめ

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

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

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