1. Зачем ещё одна структура, если есть MutableList?
Когда вы только освоили MutableList, кажется, что вы нашли универсальный швейцарский нож. Хочется всё хранить списком: и историю команд, и очередь задач, и стек действий. И да, можно — Kotlin не запрещает. Но иногда список начинает вести себя как чемодан без ручки: вроде и несёшь, но постоянно неудобно.
Проблема обычно всплывает в двух ситуациях. Первая — вам нужно быстро добавлять/забирать элементы с начала (например, «первым пришёл — первым ушёл»). Вторая — вам нужно быстро работать с последними элементами, как в истории действий («последнее действие — откатить»). В этих случаях ArrayDeque часто читается проще и по смыслу честнее.
С точки зрения стандартной библиотеки Kotlin, ArrayDeque<T> — это двусторонняя очередь (double-ended queue): можно добавлять и удалять элементы и с начала, и с конца. Она реализована на основе «растущего массива» (resizable array), который расширяется по мере надобности.
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
}
Этот фрагмент почти повторяет пример из официальной страницы про коллекции, и это хорошо: если пример «канонический», значит мозгу проще за него зацепиться.
Удаление и проверка пустоты
Удаление — место, где новички чаще всего «ловят» исключение и потом печально смотрят на stack trace. Дело в том, что removeFirst() и removeLast() предполагают: элемент есть. Если deque пустая — будет ошибка.
Поэтому важный рефлекс: перед удалением проверяем isNotEmpty() или isEmpty(). Эти функции есть у коллекций Kotlin и постоянно пригождаются в защитном коде.
import kotlin.collections.ArrayDeque
fun main() {
val d = ArrayDeque<Int>()
if (d.isNotEmpty()) {
println(d.removeFirst())
} else {
println("Deque пустая, удалять нечего") // Deque пустая, удалять нечего
}
}
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 чаще выступает как «рабочий контейнер», а не как «результат вычислений».
Если хочется простой «ментальный фильтр», можно держать в голове вот такую табличку:
| Что вы хотите делать чаще всего | Инструмент-кандидат | Почему |
|---|---|---|
| Добавлять/удалять с начала и конца | |
Методы прямо выражают смысл (addFirst/removeLast и т.д.) |
| Работать по индексам, хранить порядок, сортировать | |
Это «родной дом» индексов и сортировок |
| Доступ «по ключу» и накопления «ключ → значение» | |
Поиск по ключу — основной контракт карты |
| Делать отчёты и итоги без мутации | |
Чистые вычисления читаются легче |
Где ещё часто встречается ArrayDeque
Чтобы чуть расширить кругозор (без обязательств «идти и решать олимпиады»), полезно знать: очереди и деки часто появляются в алгоритмах обхода графов и поиска пути. В материалах Kotlin это даже мелькает в разборе Advent of Code, где упоминают ArrayDeque как удобную очередь.
Это не значит, что вам срочно нужно учить графы. Это значит, что вы уже сегодня берёте в руки инструмент, который пригодится и в «обычной прикладной разработке» (история действий, обработка задач), и в более алгоритмических задачах, если вы до них дойдёте.
8. Типичные ошибки при работе с ArrayDeque
Ошибка №1: удалять из пустой deque без проверки.
removeFirst() и removeLast() предполагают, что элемент существует. Если deque пустая, вы получите исключение. Лечится просто: перед удалением проверяйте 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 начинают добавлять «на будущее», хотя программа не использует ни очередь, ни стек. В итоге появляется лишнее состояние, которое нужно поддерживать. Хороший критерий: если вы не можете в одном предложении объяснить, где у структуры «начало» и «конец» в вашей логике, скорее всего, она вам пока не нужна.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ