Структуры данных: очередь, стек, куча, массив, дерево, граф, BFS, DFS, сложность

Этот материал — справочник по ключевым структурам данных с вопросами для проверки знаний и подборкой практических советов.

В двух словах

Массив, стек, очередь, куча, дерево и граф — это основные структуры данных, на которых строятся эффективные алгоритмы. Каждая предназначена для своего сценария: поддержание порядка обхода, управление приоритетами, представление иерархий и сетей. Выбор структуры определяется требованиями к времени доступа, памяти и операциям.

Краткое описание

Массив хранит элементы в памяти подряд, обеспечивает доступ по индексу за O(1) и служит основой для многих более сложных структур. Стек работает по принципу LIFO, push и pop занимают O(1), подходит для отката операций, стека вызовов и парсеров. Очередь следует FIFO, enqueue и dequeue — O(1), применяется в BFS и буферизации. Куча (Priority Queue с определённым порядком элементов) позволяет вставить и извлечь минимум за O(log n), посмотреть без удаления за O(1). Дерево организует иерархические данные, в сбалансированных вариантах поиск, вставка и удаление работают за O(log n). Граф моделирует связи между вершинами, может быть представлен списком смежности или матрицей смежности в зависимости от плотности связей.

Ключевые моменты для экзаменов

• Временные сложности: доступ в массиве O(1), push/pop в стеке O(1), enqueue/dequeue в очереди O(1), insert/extract в куче O(log n), операции в сбалансированном дереве поиска O(log n)
• Порядок элементов: LIFO для стека, FIFO для очереди, приоритет для кучи
• Обход структур: BFS с очередью, DFS со стеком (рекурсивно или итеративно)
• Графы в программах: представление через список смежности или матрицу, выбор зависит от плотности
• Практическое применение: планирование задач с Priority Queue, функция отката через Stack, очередь сообщений, поиск маршрутов в сети
• Безопасность: проверка границ массива,防止извлечение из пустого стека/очереди, валидация приоритетов
• Экономия ресурсов: правильный выбор структуры снижает время выполнения и объём памяти
• Документирование: описание выбранной структуры, её инвариантов и гарантии сложности

Основные компоненты

1. Массив, ёмкость, доступ по индексу, линейность в памяти
2. Стек, push, pop, вершина, инвариант LIFO
3. Очередь, enqueue, dequeue, фронт и конец, инвариант FIFO
4. Priority Queue, свойство упорядочения, минимум и максимум
5. Узлы дерева, родитель, дети, высота, глубина
6. Балансирование, AVL, красно-чёрное дерево, B-дерево для работы с памятью
7. Вершины графа, рёбра, степень, вес, направленность
8. Представление графа, список смежности, матрица смежности
9. Обход структур, BFS, DFS, прямой обход, обход в ширину, обход в глубину
10. Инварианты и тестирование, порядок в куче, порядок в дереве поиска, отсутствие циклов в дереве

Практический пример

// 1. BFS по графу со списком смежности через очередь
Queue<Node> q = new LinkedList<>()
Set<Node> seen = new HashSet<>()
q.add(start), seen.add(start)
while (!q.isEmpty()) {
Node u = q.remove()
visit(u)
for (Node v : adj[u]) {
if (!seen.contains(v)) { seen.add(v), q.add(v) }
}
}

// 2. Минимальная куча для выбора узла в алгоритме Дейкстры
PriorityQueue<State> pq = new PriorityQueue<>(byDistance)
pq.add(source)
while (!pq.isEmpty()) {
State s = pq.remove()
if (s.dist > best[s.node]) continue
relaxEdgesAndPushBetterStates(s, pq)
}

Объяснение: BFS использует очередь для послойного обхода, Дейкстра выбирает узел с наименьшей стоимостью через Priority Queue.

Плюсы и минусы

Массив

• Очень быстрый доступ по индексу, компактное размещение в памяти

• Фиксированный размер, дорогие вставки в середину

Стек

• Простые операции O(1), идеален для отката

• Доступ только к вершине

Очередь

• Стабильный порядок, развязка между производителем и потребителем

• Нет прямого доступа к элементам

Куча

• Быстрый выбор по приоритету

• Нет упорядоченного просмотра всех элементов, эффективен только вершинный доступ

Дерево

• Упорядоченные данные с логарифмическими операциями

• Сложность балансирования

Граф

• Очень гибкий, моделирует любые сетевые структуры

• Выше сложность реализации и выбора алгоритма

Типичные вопросы на проверку знаний (с кратким ответом)

1. Список смежности или матрица смежности? Для разреженных графов с малым числом рёбер список смежности экономит память O(n + m) вместо O(n²) и быстрее перебирает соседей.

2. Как работают стек и очередь? Стек: последний вошёл, первый вышел (LIFO). Очередь: первый вошёл, первый вышел (FIFO).

3. Свойство минимальной кучи? Каждый узел меньше или равен своим детям, минимальный элемент находится в корне.

4. Вставка и удаление в куче? O(log n) через подъём и спуск элементов, просмотр корня O(1).

5. Почему сбалансированные деревья — O(log n)? Высота остаётся пропорциональна логарифму размера, поэтому путь до любого элемента логарифмичен.

6. Как работает BFS? Уровень за уровнем через очередь, находит кратчайшие пути в невзвешенных графах и проверяет достижимость.

7. Как представить дерево в памяти? Связанные узлы с указателями на детей или неявно в массиве как куча, с расчётом индексов по формуле 2i и 2i+1.

8. Priority Queue быстрее отсортированного списка? Вставка и извлечение O(log n) вместо O(n), первый просмотр остаётся O(1).

9. Проблемы доступа по индексу в массиве? Выход за границы, ошибки на один, отсутствие проверок, потенциальная уязвимость.

10. Когда DFS лучше BFS? При топологической сортировке, обнаружении циклов, поиске компонент связности и когда нужно целенаправленно исследовать глубокие ветви.

Основные источники

1. https://de.wikipedia.org/wiki/Datenstruktur
2. https://en.cppreference.com/w/cpp/container
3. https://docs.oracle.com/javase/tutorial/collections/