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

Структура данных — это способ организовать набор элементов и правила доступа к ним: по индексу, только к последнему добавленному, только к первому или без повторов.

Основные структуры данных условно делятся на четыре вида: список (доступ по индексу, повторы разрешены), стек (LIFO), очередь (FIFO) и множество (без повторов). Отдельно стоит карта (словарь) для пар «ключ–значение». В Java их описывают интерфейсы List, Deque, Queue, Set и Map из Collection Framework.

Стек работает по принципу LIFO («последним пришёл — первым ушёл»): добавление (push) и извлечение (pop) идут с одного конца, доступен только последний добавленный элемент. Пример — стопка тарелок. Стек применяют для отмены действий (undo), проверки парности скобок, обхода в глубину; так же устроен стек вызовов в JVM.

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

Обе структуры допускают повторы и не дают доступа к элементам в середине. В Java стек — это Deque, очередь — Queue; обе можно реализовать классом ArrayDeque.

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

Множество — набор элементов без повторов и без индексов. Его главная операция — быстро проверить, есть ли элемент; повторный add() ничего не меняет и возвращает false. В Java — интерфейс Set: HashSet порядок не гарантирует, LinkedHashSet сохраняет порядок вставки, TreeSet хранит элементы отсортированными.

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

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

Двусторонняя очередь (deque, интерфейс Deque) позволяет добавлять и удалять элементы с обоих концов. Если работать только с одним концом (push()/pop()), получается стек; если добавлять в хвост и забирать из головы (offer()/poll()) — очередь.

Поэтому ArrayDeque заменяет и устаревший класс Stack, и обычную очередь: Deque<Integer> stack = new ArrayDeque<>();

Размер массива задаётся при создании и больше не меняется, а список растёт и уменьшается при добавлении и удалении элементов. Массив может хранить примитивы (int[]), а список — только объекты (List<Integer>).

Внутри ArrayList лежит обычный массив, который при заполнении заменяется на больший.