Абстрактні типи даних: стеки, списки, вектори, словники, множини, черги

📌 Про що ця тема

Тут перевіряють, чи розумієш ти абстрактні типи даних (АТД) — моделі зберігання даних, які описують, ЩО можна робити з даними, але не ЯК це реалізовано всередині. Ключове поняття: АТД задається набором операцій і їхньою поведінкою, а не кодом. На іспиті часто дають вибрати правильну структуру під задачу або визначити результат послідовності операцій.

📖 Головне

• Стек (stack) — працює за принципом LIFO (last in, first out): останній доданий елемент виймається першим. Операції: push (додати зверху), pop (зняти верхній), top/peek (переглянути верхній). Аналогія — стопка тарілок.

• Черга (queue) — працює за принципом FIFO (first in, first out): першим виходить той, хто першим увійшов. Операції: enqueue (додати в кінець), dequeue (взяти з початку). Аналогія — черга людей.

• Список (list) — впорядкована послідовність елементів з доступом за позицією (індексом). Можна вставляти, видаляти, читати елемент у будь-якому місці. Елементи можуть повторюватися, порядок зберігається.

• Вектор (vector, динамічний масив) — список із швидким доступом за індексом (пряма адресація). Читання за індексом — миттєве, O(1); вставка в кінець — швидка, а в середину — повільна, бо треба зсувати елементи.

• Множина (set) — колекція УНІКАЛЬНИХ елементів БЕЗ урахування порядку. Операції: додати, видалити, перевірити належність. Повторів немає. Є операції об'єднання, перетину, різниці множин.

• Словник (dictionary / map / асоціативний масив) — зберігає пари «ключ → значення». Ключі унікальні, доступ до значення — за ключем, а не за номером. Операції: додати пару, знайти значення за ключем, видалити.

• Головна ідея АТД: та сама структура (напр. стек) може бути реалізована через масив або список — користувач про це не думає, він працює лише з операціями.

• Складність операцій важлива: доступ за індексом у векторі — O(1), пошук елемента в неупорядкованому списку — O(n), пошук у словнику/множині (на хеш-таблиці) — у середньому O(1).

🔢 Як це працює на прикладі

Приклад 1 (стек). Виконуємо: push(3), push(7), push(5), pop(), push(9), pop().

Після push(3),(7),(5) стек знизу вгору: 3,7,5. pop() знімає 5. push(9): 3,7,9. pop() знімає 9. Залишок у стеку: 3,7. Вийняті: 5, потім 9.

Приклад 2 (черга). enqueue(A), enqueue(B), dequeue(), enqueue(C), dequeue().

Черга A,B → dequeue повертає A → лишається B → enqueue(C): B,C → dequeue повертає B. У черзі лишається C. Вийняті по порядку: A, B.

⚠️ Типові помилки

• Плутають стек і чергу: у стеку виходить ОСТАННІЙ (LIFO), у черзі — ПЕРШИЙ (FIFO). Це найчастіша втрата балів.

• Думають, що множина зберігає порядок або допускає дублікати — ні: лише унікальні елементи, порядок не гарантований.

• Плутають словник і список: у списку доступ за числовим індексом, у словнику — за ключем (який може бути рядком).

• Вважають, що pop/dequeue лише переглядають елемент. Насправді вони ВИДАЛЯЮТЬ його; переглядає без видалення — top/peek.

• Думають, що вставка в середину вектора така ж швидка, як у кінець — ні, потрібен зсув елементів.

🎯 Що завчити напам'ять

• Стек = LIFO, операції push / pop / top.

• Черга = FIFO, операції enqueue / dequeue.

• Множина = унікальні, без порядку.

• Словник = пари «ключ → значення», доступ за ключем.

• Вектор = доступ за індексом O(1).

🧠 Перевір себе

1. Який елемент вийде першим зі стеку після push(1), push(2), push(3)?

2. Чи може множина містити {5, 5, 2}?

3. За чим звертаються до значення у словнику — за індексом чи за ключем?

4. Виконай для черги: enqueue(X), enqueue(Y), dequeue(). Що повернулось?

Відповіді: 1 — 3 (останній доданий, LIFO); 2 — ні, лише {5, 2}, дублікати неможливі; 3 — за ключем; 4 — X (перший доданий, FIFO).