Структуры данных в Java: список, стек, очередь и множество

Положите в класс Stack числа 1, 2, 3 через push() и выведите его: получится [1, 2, 3]. Сделайте то же с ArrayDeque — и увидите [3, 2, 1]. Обе коллекции «стеки», а вывод противоположный. Чтобы такие вещи не путали, сначала нужно понять сами структуры данных, а уже потом классы Java, которые их реализуют.

Структура данных — это способ организовать набор элементов и правила доступа к ним: по индексу, только к последнему добавленному, только к первому или без повторов. Основные структуры данных в Java условно делятся на четыре вида: список, стек, очередь и множество. Отдельно стоит карта (словарь) для пар «ключ–значение». Все они реализованы в Collection Framework — его устройство разобрано в уроке Коллекции в Java.

Список

Список — это упорядоченная последовательность элементов, в которой у каждого элемента есть индекс (номер позиции, начиная с 0), а одинаковые элементы могут повторяться. К любому элементу можно обратиться по индексу, вставить новый элемент в любое место или удалить его.

В англоязычной литературе список также называют последовательностью (sequence). Как именно хранятся элементы, абстрактный список не определяет. В Java есть две основные реализации: ArrayList хранит элементы во внутреннем массиве (урок List и ArrayList), а LinkedList — в узлах, каждый из которых ссылается на следующий и предыдущий элементы (урок LinkedList).

На рисунке ниже в список добавлены буквы A, B, C, A, A. Буква A встречается трижды — в списке это разрешено. Каждая буква отмечена своим индексом.

Стек (LIFO)

Стек — это структура данных, в которой элементы извлекаются по принципу «последним пришёл — первым ушёл» (Last-In-First-Out, LIFO). Доступен только верхний, последний добавленный элемент; добавление (push) и извлечение (pop) происходят с одного конца. Повторяющиеся элементы стек допускает.

Хороший пример стека — стопка тарелок. Верхнюю тарелку положили в стопку последней (Last-In), но взять её можно первой (First-Out). Самую нижнюю тарелку, наоборот, положили первой, а достать её получится только после того, как сняты все верхние. Взять тарелку из середины, не снимая верхние, нельзя.

По этому же принципу устроен стек вызовов в JVM: метод, вызванный последним, завершается первым. Стек применяют для отмены действий (undo), проверки парности скобок, обхода в глубину.

Очередь (FIFO)

Очередь — это структура данных, в которой элементы извлекаются по принципу «первым пришёл — первым ушёл» (First-In-First-Out, FIFO): элементы добавляются в хвост (enqueue), а забираются из головы (dequeue). Поэтому элементы выходят из очереди в том же порядке, в каком были добавлены.

Как и стек, очередь не даёт доступа к произвольному элементу — только к концам. Разница в том, что у стека добавление и извлечение идут с одного конца, а у очереди — с разных, как в очереди в кассу или на конвейере. Повторяющиеся элементы очередь допускает. Очередь применяют для задач, которые обрабатываются по мере поступления: печать документов, обработка запросов, обход в ширину.

В Java очередь описывает интерфейс Queue, а двустороннюю очередь, которая может работать и как стек, — Deque (урок Queue и Deque). Особый вид очереди, где первым выходит не самый ранний, а самый приоритетный элемент, — PriorityQueue.

Множество

Множество — это набор элементов без повторов: каждый элемент встречается в нём не больше одного раза, а индексов у элементов нет. Главная операция множества — быстро проверить, содержится ли в нём элемент; попытка добавить уже существующий элемент ничего не меняет.

Хороший пример множества — автомобили на парковке: у каждой машины уникальный номер, двух машин с одинаковым номером там быть не может, а порядок, в котором они стоят, значения не имеет.

Абстрактное множество не упорядочено, но в Java есть реализации и с порядком: HashSet порядок не гарантирует, LinkedHashSet сохраняет порядок вставки (урок Set и HashSet), а TreeSet хранит элементы отсортированными (урок SortedSet и TreeSet).

Карта (словарь)

Карта (словарь, ассоциативный массив) — это структура данных, которая хранит пары «ключ–значение»: ключи уникальны, как элементы множества, а значение находят по ключу, а не по индексу. Пример — телефонная книга, где по имени находят номер.

В Java карту описывает интерфейс Map с реализациями HashMap, LinkedHashMap и TreeMap — они разобраны в уроке Map.

Сравнение структур данных

Структуры данных различаются тремя признаками: к каким элементам есть доступ, допускаются ли дубликаты и есть ли у элементов индексы. От этого зависит, какой интерфейс и класс Java выбрать под задачу.

Какую реализацию брать по умолчанию и чем классы отличаются по скорости операций, показано в таблице урока Коллекции в Java.

Одни и те же данные в четырёх структурах

Если добавить одну и ту же последовательность букв A, B, C, A, D в список, стек, очередь и множество, каждая структура вернёт данные по-своему: список — по индексу, стек — с конца, очередь — с начала, а множество просто не примет повтор. Что выведет этот код?

import java.util.*;

public class DataStructuresDemo {
    public static void main(String[] args) {
        String[] letters = {"A", "B", "C", "A", "D"};

        List<String> list = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        Queue<String> queue = new ArrayDeque<>();
        Set<String> set = new HashSet<>();

        for (String s : letters) {
            list.add(s);     // в конец списка
            stack.push(s);   // на вершину стека
            queue.offer(s);  // в хвост очереди
            set.add(s);      // повтор "A" будет отброшен
        }

        System.out.println("Список: " + list + ", get(3) = " + list.get(3));
        System.out.println("Стек: pop() = " + stack.pop() + ", затем " + stack.pop());
        System.out.println("Очередь: poll() = " + queue.poll() + ", затем " + queue.poll());
        System.out.println("Множество: size() = " + set.size() + ", add(\"A\") = " + set.add("A"));
    }
}

Вывод:

Список: [A, B, C, A, D], get(3) = A
Стек: pop() = D, затем C
Очередь: poll() = A, затем B
Множество: size() = 4, add("A") = false

Список хранит все пять букв, включая повтор. Стек отдаёт последние добавленные D и C, очередь — первые добавленные A и B. Во множестве четыре элемента: вторая A не добавилась, и повторный add("A") возвращает false. Для пустого стека или очереди pop() бросит NoSuchElementException, а poll() вернёт null — разница между методами подробно разобрана в уроке Queue и Deque.