📚

ArrayDequeを使ってKotlinでQueueやStackを扱う

2021/10/25に公開

KotlinでQueueやStackを扱いたいときに、ArrayDequeというクラスが便利だったので紹介します。
KotlinであればJavaのjava.util.ArrayDequeクラスを使うこともできますが、kotlin.collections.ArrayDequeはマルチプラットフォーム下で利用可能なので、より汎用性の高いクラスです。
以降、本記事でArrayDequeと記載したものは全てkotlin.collections.ArrayDequeを指しています。

ArrayDequeのDequeは「Double ended queue」の略で、先頭と末尾の両端から要素の追加や削除ができるQueueという意味です。読み方は「deck」です。
ArrayDequeはAbstractMutableListの実装クラスのため、get(index)によって先頭と末尾以外の要素を直接することもできます(Queueの一種にしては妙な気もしますが)。

ArrayDequeをQueueとして扱う

QueueはFirst In First Out (FIFO)のデータ構造のことです。
したがって、Queueに対する各操作に対応するArrayDequeの処理は以下のようになります。

Queueに対する操作	操作の意味	ArrayDequeによる実現
enqueue	- Queueの末尾に要素を追加する	`ArrayDeque#add(item)`
dequeue	- Queueの先頭から要素を取得する - 取得した要素をQueueから削除する	`ArrayDeque#removeFirst()`
peek	- Queueの先頭から要素を取得する - 取得した要素はQueueから削除しない	`ArrayDeque#first()`
isEmpty	- Queueの要素が空かどうか判定する	`ArrayDeque#isEmpty()`

fun main() {
    println("initialize")
    val queue = ArrayDeque(listOf(1, 2, 3))
    println(queue) // -> [1, 2, 3]

    println("enqueue")
    queue.add(4)
    println(queue) // -> [1, 2, 3, 4]

    println("dequeue")
    println(queue.removeFirst())
    println(queue) // -> [2, 3, 4]
    
    println("peek")
    println(queue.first())
    println(queue) // -> [2, 3, 4]

    println("isEmpty")
    println(queue.isEmpty()) // -> false
    println(queue) // -> [2, 3, 4]
}

ArrayDequeをStackとして扱う

StackはLast In First Out (LIFO)のデータ構造のことです。
したがって、Stackに対する各操作に対応するArrayDequeの処理は以下のようになります。

Stackに対する操作	操作の意味	ArrayDequeによる実現
push	Stackの末尾に要素を追加する	`ArrayDeque#add(item)`
pop	Stackの末尾から要素を取得する取得した要素をStackから削除する	`ArrayDeque#removeLast()`
peek	Stackの末尾から要素を取得する取得した要素はStackから削除しない	`ArrayDeque#last()`
isEmpty	Stackの要素が空かどうか判定する	`ArrayDeque#isEmpty()`

fun main() {
    println("initialize")
    val stack = ArrayDeque(listOf(1, 2, 3))
    println(stack) // -> [1, 2, 3]

    println("push")
    stack.add(4)
    println(stack) // -> [1, 2, 3, 4]

    println("pop")
    println(stack.removeLast())
    println(stack) // -> [1, 2, 3]
    
    println("peek")
    println(stack.last())
    println(stack) // -> [1, 2, 3]
    
    println("isEmpty")
    println(stack.isEmpty()) // -> false
    println(stack) // -> [1, 2, 3]
}

ArrayDequeをQueueとして扱う

ArrayDequeをStackとして扱う

Discussion