Структуры данных
Полный гид для студентов: стек, очередь, деревья и хеш-таблицы. Поймите, когда какая структура решает задачу быстрее всех.
Что такое структура данных?
Структура данных — это способ组织овать и хранить данные в памяти компьютера так, чтобы с ними было удобно работать: быстро добавлять, удалять, искать и изменять.
Представьте: у вас тысяча книг. Можно сложить их в кучу на полу — тогда поиск нужной книги займёт вечность. А можно поставить на полку по алфавиту или разложить по жанрам. Структура данных — это и есть «поставить книги на полку». Разная организация подходит для разных задач.
Каждая структура имеет свои сложности операций — O-нотация. Она показывает, как растёт время выполнения с увеличением объёма данных. O(1) — мгновенно, O(log n) — очень быстро, O(n) — пропорционально объёму.
🏗️ Зачем это нужно?
Правильная структура данных может ускорить программу в тысячи раз. Плохой выбор — замедлить до тормозов. Один и тот же алгоритм на массиве может работать за O(n²), а на хеш-таблице — за O(n).
📐 Как читать O-нотацию?
n — количество элементов. O(1) = время не зависит от n. O(log n) = при увеличении n вдвое время растёт на 1 шаг. O(n) = время растёт пропорционально. O(n²) = при удвоении n время ×4.
Стек
Stack • LIFOСтруктура данных по принципу Last In — First Out: последний добавленный элемент извлекается первым. Доступ только к верхнему элементу — это делает стек предсказуемым и сверхбыстрым.
💡 Представьте стопку тарелок: кладёте сверху — снимаете сверху. Нижнюю тарелку не достанете, пока не уберёте все верхние.
Очередь
Queue • FIFOПринцип First In — First Out: элементы обрабатываются строго в порядке поступления. Первый вошёл — первый вышел. Идеальна для моделирования реальных очередей и обработки задач по порядку.
💡 Как очередь в магазине: кто встал первым — того и обслужат первым. Новые люди встают в конец.
Дерево
Tree • Бинарное дерево поискаИерархическая структура из узлов, где каждый имеет не более двух потомков. В бинарном дереве поиска (BST) левый потомок меньше родителя, правый — больше. Это даёт быстрый поиск за O(log n).
💡 Как книга с оглавлением: каждый раздел делится на подразделы, каждый подраздел — на пункты. Вы идёте от общего к частному, не перечитывая книгу целиком.
Хеш-таблица
Hash Table • Ключ → ЗначениеМассив фиксированного размера + хеш-функция, которая превращает ключ в индекс массива. Благодаря этому поиск, добавление и удаление работают в среднем за O(1) — мгновенно.
💡 Как шкаф с пронумерованными ячейками: вы кладёте вещь в ячейку с номером, который высчитывает формула. Чтобы найти — считаете номер снова и сразу идёте туда.
| Структура | Принцип | Доступ | Поиск | Вставка | Удаление | Память |
|---|---|---|---|---|---|---|
| Стек | LIFO | O(1) top | O(n) | O(1) | O(1) | Минимальная |
| Очередь | FIFO | O(1) front | O(n) | O(1) | O(1) | Минимальная |
| Дерево (BST) | Иерархия | O(log n) | O(log n) | O(log n) | O(log n) | Средняя |
| Хеш-таблица | Ключ → Индекс | O(1)* | O(1)* | O(1)* | O(1)* | Высокая |
⚡ Как выбрать правильную структуру?
Каждая структура данных оптимальна для своей задачи. Вот простое правило: спросите себя, что именно вам нужно делать с данными.
Стек
«Мне нужен доступ только к последнему элементу» — Undo, структура вызовов, обратный обход
Очередь
«Нужно обработать строго по порядку поступления» — печать, BFS, планировщик задач
Дерево
«Данные иерархические и нужен быстрый поиск с有序ностью» — файловая система, HTML DOM
Хеш-таблица
«Нужен мгновенный доступ по ключу, порядок не важен» — кэш, словарь, индексация
Отмена в редакторе
Каждое действие (набор текста, форматирование) записывается в стек. Нажали Ctrl+Z — извлекается последнее действие. Можно отменить все действия по очереди.
HTTP-запросы к серверу
Сервер получает запросы от пользователей и ставит их в очередь. Обрабатывает по порядку поступления — так обеспечивается справедливость для всех клиентов.
Файловая система
Корневая папка — вершина дерева. Подпапки — ветви. Файлы — листья. Путь C:\Users\Documents\file.txt — это обход дерева от корня к листу.
Кэш браузера
URL — ключ, HTML-код — значение. При повторном запросе браузер вычисляет хеш URL и мгновенно находит страницу в кэше, не обращаясь к сети.
BFS-обход графа
Поиск в ширину (BFS) использует очередь: сначала изучаем все соседи текущего узла, потом — их соседей. Находит кратчайший путь в невзвешенном графе.
DOM-дерево в HTML
Браузер превращает HTML-код в дерево объектов (Document Object Model). JavaScript находит, добавляет и удаляет элементы — все манипуляции идут через дерево.
Правило «одного конца»
Стек = работа с одним концом (верхом). Очередь = работа с двумя концами (вход и выход). Запомните: стек — это «всё с одной стороны», очередь — «вход слева, выход справа».
Баланс скорости и памяти
Хеш-таблица быстрее всех (O(1)), но тратит больше памяти. Дерево сбалансировано — ищет быстро (O(log n)), и экономит память. Выбирайте компромисс.
Когда дерево лучше хеш-таблицы?
Когда нужен有序ный обход (от меньшего к большему) или диапазонный запрос (все значения между 10 и 50). Хеш-таблица перемешивает данные —有序ность теряется.
Асимптотика на экзамене
Запомните: стек и очередь — все основные операции O(1). Дерево (сбалансированное) — O(log n). Хеш-таблица — O(1) в среднем, O(n) в худшем (при коллизиях).