Структури даних
Структури даних — безкоштовна інтерактивна симуляція зі 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 перетворить їх на картки, тести й подкасти.