ArrayDeque: черга й стек «із коробки», базові операції та пастки

1. Навіщо ще одна структура, якщо є MutableList?

Коли ви щойно опанували MutableList, здається, що ви знайшли універсальний швейцарський ніж. Хочеться все зберігати списком: і історію команд, і чергу завдань, і стек дій. І так, можна: Kotlin не забороняє. Але іноді список починає поводитися як валіза без ручки: ніби й несете, а постійно незручно.

Проблема зазвичай спливає у двох ситуаціях. Перша — вам потрібно швидко додавати й забирати елементи з початку (наприклад, «першим прийшов — першим пішов»). Друга — вам потрібно швидко працювати з останніми елементами, як в історії дій («останню дію — відкотити»). У таких випадках ArrayDeque часто читається простіше й за змістом чесніше.

З погляду стандартної бібліотеки Kotlin, ArrayDeque<T> — це двостороння черга (double-ended queue): ви можете додавати й видаляти елементи і з початку, і з кінця. Вона реалізована на основі масиву, що розширюється: за потреби він збільшується.

2. ArrayDeque по-людськи: двостороння черга

Якщо перекласти термін deque мовою побутових аналогій, вийде щось на кшталт «черги з дверима і спереду, і ззаду». Звичайна черга в магазині працює строго з двох боків: ви стаєте в кінець, а обслуговують із початку. А ArrayDeque — це черга, де касир уміє обслуговувати й з іншого кінця (дивний магазин, зате структура даних щаслива).

Важливо, що ArrayDeque у Kotlin закриває одразу два класичні сценарії. Якщо ви використовуєте кінець для додавання, а початок — для видалення, це черга FIFO. Якщо ви використовуєте кінець і для додавання, і для видалення — це стек LIFO. І все це робиться стандартними методами — без написання власних «велосипедів» на MutableList.

Нижче — мінісхема, щоб закріпити візуально:

flowchart LR
    subgraph FIFO["Черга FIFO"]
      A1["addLast(x)"] --> A2["... черга ..."] --> A3["removeFirst()"]
    end

    subgraph LIFO["Стек LIFO"]
      B1["addLast(x)"] --> B2["... стек ..."] --> B3["removeLast()"]
    end

3. Базові операції ArrayDeque

Перед тим як «вбудовувати» ArrayDeque у наш навчальний застосунок, важливо опанувати зовсім базову механіку. З MutableList ми звикли до add(...), removeAt(...), індексів і lastIndex. У ArrayDeque фокус інший: ми працюємо з початком і кінцем, а не з індексами.

Головні операції можна запамʼятати так: addFirst/addLast — це «покласти елемент», removeFirst/removeLast — «забрати елемент і видалити», а first()/last() — «піддивитися елемент, не видаляючи». У документації Kotlin це показано на невеликому прикладі.

Створення ArrayDeque

import kotlin.collections.ArrayDeque

fun main() {
    val empty = ArrayDeque<Int>()
    println(empty) // []

    val deque = ArrayDeque(listOf(1, 2, 3))
    println(deque) // [1, 2, 3]
}

Зверніть увагу на приємний момент зі світу Kotlin-колекцій: навіть якщо колекція лежить у val, її все одно можна змінювати (змінюється вміст, а не посилання). Це загальний принцип для mutable-колекцій.

Додавання і «піддивляння» першого/останнього

import kotlin.collections.ArrayDeque

fun main() {
    val d = ArrayDeque(listOf(1, 2, 3))

    d.addFirst(0)
    d.addLast(4)

    println(d)         // [0, 1, 2, 3, 4]
    println(d.first()) // 0
    println(d.last())  // 4
}

Цей фрагмент майже повторює приклад з офіційної сторінки про колекції — і це добре. Якщо приклад «канонічний», мозку простіше за нього зачепитися.

Видалення та перевірка порожнечі

Видалення — місце, де новачки найчастіше «ловлять» виняток і потім сумно дивляться на трасу стеку. Річ у тім, що removeFirst() і removeLast() припускають: елемент є. Якщо дек порожній — буде помилка.

Тому корисний рефлекс такий: перед видаленням перевіряємо isNotEmpty() або isEmpty(). Ці функції є в колекціях Kotlin і постійно стають у пригоді в захисному коді.

import kotlin.collections.ArrayDeque

fun main() {
    val d = ArrayDeque<Int>()

    if (d.isNotEmpty()) {
        println(d.removeFirst())
    } else {
        println("Дек порожній — видаляти нічого") // Дек порожній — видаляти нічого
    }
}

4. Черга FIFO на ArrayDeque

Черга FIFO — один із найприродніших життєвих патернів: приходять завдання, а ми обробляємо їх за порядком. У програмуванні черги трапляються в логіці «планувальник завдань», «список повідомлень на обробку», «друк документів», «пакетна обробка команд». Навіть якщо ви поки не пишете складні системи, черга — корисна ментальна модель.

У ArrayDeque черга FIFO робиться максимально просто: додаємо в кінець через addLast, а забираємо з початку через removeFirst. Тобто ми ніби говоримо структурі: «постав нового в хвіст» і «обслугуй першого з голови».

Ось коротка демонстрація:

import kotlin.collections.ArrayDeque

fun main() {
    val q = ArrayDeque<String>()

    q.addLast("read file")
    q.addLast("parse data")
    q.addLast("build report")

    println(q.removeFirst()) // read file
    println(q.removeFirst()) // parse data
    println(q)               // [build report]
}

Якщо ви помітили, тут немає жодного індексу. Це не «обмеження», а підказка: структура робить ваш код ближчим до змісту. Якщо ви пишете чергу через індекси списку, то вже трохи вдаєте, що вам потрібен список, хоча насправді вам потрібна черга.

5. Стек LIFO на ArrayDeque

Стек LIFO — це інша повсякденна логіка: ви складаєте тарілки стопкою й берете верхню. У програмуванні стек зазвичай зʼявляється там, де є «історія» та «відкат»: історія дій користувача, історія команд, вкладені виклики, повернення назад. Ми не заглиблюватимемося в теоретичні нетрі, але практичний сценарій undo дуже зрозумілий навіть новачкові.

У ArrayDeque стек робиться так: додаємо в кінець через addLast, а забираємо теж із кінця через removeLast. З погляду читання коду це виглядає як «покласти зверху» і «зняти зверху».

import kotlin.collections.ArrayDeque

fun main() {
    val stack = ArrayDeque<String>()

    stack.addLast("open settings")
    stack.addLast("change theme")
    stack.addLast("save")

    println(stack.removeLast()) // save
    println(stack.removeLast()) // change theme
    println(stack)              // [open settings]
}

Так, можна було б зробити те саме через MutableList і removeAt(lastIndex). Але ArrayDeque тут виграє тим, що назви методів описують зміст: «зняти з кінця» — це рівно те, що ви робите.

6. ArrayDeque у CLI-застосунку: історія додавань і undo

Тепер найцікавіше: давайте акуратно «приземлимо» ArrayDeque на наш практичний проєкт (консольний трекер витрат/нотаток). У попередні дні ми вже робили команди на кшталт add, list, remove і вчилися оновлювати колекції, не ламаючи обходу. Сьогодні додамо маленьку, але дуже життєву можливість: скасовувати останнє додавання.

Одразу чесно: ми зробимо undo простим. Він скасовуватиме лише останні операції add (і тільки в тому порядку, у якому вони виконувалися). Це не промисловий Git, а навчальний приклад. Нам важливо відчути, чому «стек історії» — це ArrayDeque.

Міні-модель даних

Оскільки до класів і data class у нас ще далеко, зберігатимемо витрати як Pair<String, Int>, де first — категорія, а second — сума. Це ми вже вміємо з попередніх днів про Pair/Triple.

typealias Expense = Pair<String, Int> // якщо typealias у вас за курсом ще не було, просто приберіть цей рядок

Якщо typealias у вашому потоці ще не проходили — нічого страшного: можна писати Pair<String, Int> прямо в коді. Зміст не змінюється.

Стек історії додавань

Ідея така: коли користувач вводить команду add, ми додаємо запис у список витрат і паралельно кладемо цей самий запис у стек history. Коли користувач вводить undo, ми дістаємо останній запис із history і видаляємо останній запис зі списку витрат.

import kotlin.collections.ArrayDeque

fun main() {
    val expenses = mutableListOf<Pair<String, Int>>()
    val history = ArrayDeque<Pair<String, Int>>() // стек: останнє додавання зверху

    expenses.add("food" to 250)
    history.addLast("food" to 250)

    expenses.add("taxi" to 600)
    history.addLast("taxi" to 600)

    println(expenses) // [(food, 250), (taxi, 600)]
}

Реалізація undo

Зараз зробимо «наївний, але зрозумілий» undo: він працює лише тоді, коли є що скасовувати. Тому ми використовуємо перевірку isNotEmpty() — це той самий маленький запобіжник, який рятує від видалення з порожньої структури.

import kotlin.collections.ArrayDeque

fun undoLastAdd(
    expenses: MutableList<Pair<String, Int>>,
    history: ArrayDeque<Pair<String, Int>>
) {
    if (history.isEmpty()) {
        println("Нема чого скасовувати") // Нема чого скасовувати
        return
    }

    history.removeLast()
    expenses.removeLast()
    println("Останнє додавання скасовано") // Останнє додавання скасовано
}

Тут є тонкий момент: removeLast() у MutableList видаляє останній елемент. Ми припускаємо, що history і expenses синхронізовані (ми додавали туди завжди парами). Це нормальна навчальна модель. У реальному проєкті ви б захищалися краще, але поки наша мета — зрозуміти структуру.

Мініцикл команд: add і undo

Зберемо невеликий фрагмент «командного циклу». Він не претендує на ідеальність, але показує, де саме ArrayDeque лягає за змістом.

import kotlin.collections.ArrayDeque

fun main() {
    val expenses = mutableListOf<Pair<String, Int>>()
    val history = ArrayDeque<Pair<String, Int>>()

    while (true) {
        val line = readln().trim()
        if (line == "exit") break

        val parts = line.split(" ")
        when (parts[0]) {
            "add" -> {
                val cat = parts.getOrNull(1) ?: continue
                val amount = parts.getOrNull(2)?.toIntOrNull() ?: continue

                val e = cat to amount
                expenses.add(e)
                history.addLast(e)

                println("OK") // OK
            }
            "undo" -> {
                if (history.isNotEmpty()) {
                    history.removeLast()
                    expenses.removeLast()
                    println("UNDO") // UNDO
                } else {
                    println("Нема чого скасовувати") // Нема чого скасовувати
                }
            }
            "list" -> println(expenses)
            else -> println("Невідома команда")
        }
    }
}

Так, тут є місця, які можна поліпшити (валідація введення, повідомлення про помилки, підтримка remove і узгодження історії). Але це нормально: ми додали ArrayDeque як інструмент, не перетворюючи приклад на «консольний комбайн». У навчальному коді корисно зупинятися вчасно — інакше стає складно зрозуміти, яка частина за що відповідає.

7. Коли ArrayDeque не підходить

Дуже хочеться закохатися в нову структуру й почати «пхати» її всюди, але краще відкласти емоції та ввімкнути інженерний режим. ArrayDeque хороша, коли ви справді працюєте з кінцями колекції. Якщо вам потрібен випадковий доступ («дай елемент за індексом i»), якщо вам потрібно постійно сортувати або шукати за ключем — це вже територія List/Map й операцій із колекціями, які ми проходили раніше.

Також важливо памʼятати, що ArrayDeque — mutable-структура. Вона чудово підходить для сценаріїв «накопичуємо й споживаємо». Але якщо ви будуєте пайплайни в стилі «не мутуємо вхідні дані» (як у наших розмовах про Sequence та читабельні ланцюжки), то ArrayDeque частіше виступає як «робочий контейнер», а не як «результат обчислень».

Якщо хочеться простого «ментального фільтра», можна тримати в голові ось таку табличку:

ArrayDeque

List / MutableList

Map / MutableMap

операції колекцій + fold

Де ще часто трапляється ArrayDeque

Щоб трохи розширити кругозір (без обовʼязку «йти й розвʼязувати олімпіади»), корисно знати: черги й деки часто зʼявляються в алгоритмах обходу графів і пошуку шляху. У матеріалах Kotlin це навіть миготить у розборі Advent of Code, де згадують ArrayDeque як зручну чергу.

Це не означає, що вам терміново потрібно вчити графи. Це означає, що ви вже сьогодні берете до рук інструмент, який стане в пригоді і в «звичайній прикладній розробці» (історія дій, обробка завдань), і в більш алгоритмічних задачах, якщо ви до них дійдете.

8. Типові помилки під час роботи з ArrayDeque

Помилка № 1: видаляти з порожнього дека без перевірки.
removeFirst() і removeLast() припускають, що елемент існує. Якщо дек порожній, ви отримаєте виняток. Лікується просто: перед видаленням перевіряйте isNotEmpty() або isEmpty(). Цей патерн загалом універсальний для колекцій Kotlin і регулярно рятує від ситуації «впали на рівному місці».

Помилка № 2: сплутати чергу і стек в одній і тій самій структурі.
Дуже часта логічна плутанина: ви додаєте через addLast, а видаляєте теж через removeLast, думаючи, що зробили FIFO, хоча насправді зробили LIFO. Мозку допомагає проста самоперевірка: FIFO завжди «додав у хвіст — забрав з голови», тобто addLast + removeFirst. LIFO завжди «додав зверху — забрав зверху», тобто addLast + removeLast.

Помилка № 3: намагатися використовувати ArrayDeque як список з індексами.
Коли рука тягнеться написати щось на кшталт «дай мені deque[3]», це сигнал: ви вибрали не ту структуру. ArrayDeque за змістом — про кінці, а не про довільний доступ. Якщо вам потрібен індексний доступ — поверніться до List/MutableList. Так код буде чеснішим і простішим для читання.

Помилка № 4: зберігати в ArrayDeque історію, але не синхронізувати її з основними даними.
У прикладі з undo ми тримали expenses і history синхронними. Якщо в реальному коді ви інколи додаєте витрату в expenses, але забуваєте додати її в history, то undo почне скасовувати «щось не те». Це не помилка ArrayDeque — це помилка дисципліни даних. Лікується тим, що зміни основного стану й історії робляться поруч, в одній гілці коду, як єдина дія.

Помилка № 5: перетворювати ArrayDeque на ще одну колекцію «про всяк випадок».
Іноді ArrayDeque додають «на майбутнє», хоча програма не використовує ані чергу, ані стек. У результаті зʼявляється зайвий стан, який потрібно підтримувати. Хороший критерій: якщо ви не можете одним реченням пояснити, де у цієї структури «початок» і «кінець» у вашій логіці, найімовірніше, вона вам поки не потрібна.

1

Опитування

Агрегації та продуктивність, рівень 25, лекція 4

Недоступний

Агрегації та продуктивність

Агрегації та продуктивність

Відкрити