Структуры данных
Структуры данных — бесплатная интерактивная симуляция из StudyFi Lab. Работает прямо в браузере, без регистрации и установки.
Стеки, очереди, списки, деревья и графы
Эксперименты
Стек
Стек похож на стопку тарелок: добавляем (push) и снимаем (pop) только сверху, поэтому последним пришёл — первым ушёл (LIFO). Указатель top отмечает вершину; push и pop выполняются за O(1). Стек используют отмена действий в редакторе, кнопка «Назад» в браузере и вызовы функций в программе (стек вызовов).
Попробуй: Положи 1, 2, 3 и трижды выполни pop — числа выйдут в обратном порядке. Затем попробуй девятый push.
Очередь
Очередь похожа на очередь в кассу: новые элементы встают в конец (enqueue, указатель rear) и уходят из начала (dequeue, указатель front), поэтому первым пришёл — первым ушёл (FIFO). В массиве её хранят как кольцевой буфер: оба указателя после последней ячейки возвращаются к ячейке 0, поэтому enqueue и dequeue выполняются за O(1). Очереди управляют печатью, запросами к серверу и буферизацией видео.
Попробуй: Включи кольцевой вид, добавь шесть чисел, извлеки четыре и добавь ещё четыре — rear перескочит из ячейки 7 в ячейку 0.
Связный список
Каждый узел хранит значение и ссылку next на следующий узел; последний указывает на null, а список начинается с указателя head. Вставка в начало стоит O(1), но чтобы дойти до позиции i или найти значение, приходится идти узел за узлом — O(n). В отличие от массива ничего не сдвигается, меняются только ссылки; так устроены плейлисты, истории действий и списки свободной памяти.
Попробуй: Найди последнее значение и посчитай шаги указателя, затем вставь число в начало — это всегда один шаг.
Двоичное дерево поиска
В каждом узле меньшие значения идут влево, большие — вправо. Поэтому поиск и вставка проходят один путь от корня и занимают O(h), где h — высота дерева; у сбалансированного дерева h ≈ log₂ n. У удаления три случая: лист просто исчезает, узел с одним потомком заменяется этим потомком, а узел с двумя потомками берёт значение своего симметричного (in-order) преемника. Симметричный обход выдаёт значения по возрастанию; похожие деревья лежат в основе индексов баз данных.
Попробуй: Удали корень — у него два потомка, поэтому увидишь поиск преемника. Затем нажми «Вставить отсортированные значения»: дерево вырождается в список, и высота растёт до n.
Граф: BFS и DFS
Поиск в ширину (BFS) берёт вершины из очереди: сначала все соседи старта, потом их соседи — слой за слоем, поэтому он находит кратчайший путь по числу рёбер. Поиск в глубину (DFS) берёт вершины из стека и уходит как можно дальше, прежде чем вернуться. Оба посещают каждую вершину и ребро один раз: O(V + E). BFS используют навигаторы и «друзья друзей» в соцсетях, DFS — лабиринты и поиск циклов.
Попробуй: Пройди по шагам от вершины 0 и сравни очередь со стеком. Затем выбери стартом вершину 7 — порядок обхода полностью изменится.
Частые вопросы
Что такое «Структуры данных»?
Структуры данных — бесплатная интерактивная симуляция из StudyFi Lab. Работает прямо в браузере, без регистрации и установки. Стеки, очереди, списки, деревья и графы
Приложение «Структуры данных» бесплатное?
Да. Приложение «Структуры данных» полностью бесплатное. Оно работает в браузере на компьютере, планшете и телефоне, аккаунт не нужен.
Что можно изучить в приложении «Структуры данных»?
Стек, Очередь, Связный список, Двоичное дерево поиска, Граф: BFS и DFS.
Что показывает эксперимент «Стек»?
Стек похож на стопку тарелок: добавляем (push) и снимаем (pop) только сверху, поэтому последним пришёл — первым ушёл (LIFO). Указатель top отмечает вершину; push и pop выполняются за O(1). Стек используют отмена действий в редакторе, кнопка «Назад» в браузере и вызовы функций в программе (стек вызовов).
Что показывает эксперимент «Очередь»?
Очередь похожа на очередь в кассу: новые элементы встают в конец (enqueue, указатель rear) и уходят из начала (dequeue, указатель front), поэтому первым пришёл — первым ушёл (FIFO). В массиве её хранят как кольцевой буфер: оба указателя после последней ячейки возвращаются к ячейке 0, поэтому enqueue и dequeue выполняются за O(1). Очереди управляют печатью, запросами к серверу и буферизацией видео.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.