1.1.2. Поняття абстрактного типу даних. Абстрактні типи даних: стеки, списки, вектори, словники, множини, мультимножини, черги, черги з пріоритетами
Абстрактний тип даних (АТД) — це математична модель для типів даних, де тип даних визначається поведінкою (семантикою) з точки зору користувача даних, а саме в термінах можливих значень, можливих операцій над даними цього типу і поведінки цих операцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення — в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних зазвичай подаються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних намагаються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не за швидкістю) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Стек (англ. stack — «стос, стіс») в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елемента) в стеку можна проводити тільки з одним елементом, який міститься на верхівці стека та був уведений в стек останнім. Стек можна уявити як стопку тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку. Інша назва стека — «магазин», за аналогією з принципом роботи магазина в автоматичній зброї.
Список або послідовність — абстрактний тип даних, який являє собою зліченне число впорядкованих значень, де одне і теж саме значення може зустрічатися більше одного разу. Екземпляр списку — це комп'ютерне подання математичного поняття скінченної послідовності; (потенційно) нескінченний аналог списку — це потік. Списки є основним прикладом контейнерів, оскільки вони містять інші значення. Якщо ж значення зустрічається кілька разів, у кожному випадку воно розглядається, як окремий елемент.
Реалізація структури даних списку може надати деякі з таких операцій:
конструктор для створення порожнього списку;
операція для перевірки чи список порожній, чи ні;
операція для додавання об'єкта на початок списку;
операція для додавання об'єкта в список;
операція для визначення першого компонента (або «голови») списку;
операція для посилання на список, що складається з усіх компонентів списку, за винятком його першого елемента («голови»), (це називається «хвіст» списку).
Вектор — це абстрактна модель, яка імітує динамічний масив. Шаблон vector розміщений у заголовковому файлі <vector>. Як і всі стандартні компоненти, він розміщений у просторі імен std. Даний інтерфейс емулює роботу стандартного масиву мови C (наприклад швидкий довільний доступ до елементів), а також деякі додаткові можливості, такі, як автоматична зміни розміру вектора при вставці або видаленні елемента.
Всі елементи класу мають належати одному типові. Наприклад, не можна одночасно зберігати дані типів char і int у одному векторі. Клас vector володіє стандартним набором методів для доступу до елементів, додавання та видалення елементів, а також отримання кількості збережених елементів.
Типова реалізація вектора — це вказівник на динамічний масив. Розмір вектора — це кількість елементів, а об'єм — кількість використаної ним пам'яті.
Якщо при вставці в вектор нових елементів, його розмір стає більшим від його об'єму, відбувається перерозподіл пам'яті. Як правило, це призводить до того, що вектор виділяє нову область збереження, переміщуючи елементи і вільні старі області в нову ділянку пам'яті.
Оскільки адреси елементів при цьому змінюються, будь-які посилання, або ітератори елементів у векторі можуть стати недійсними. Використання недійсних посилань призводить до невизначеної поведінки.
Словник даних або сховище метаданих, як це визначено в Словнику обчислень IBM, є "централізованим сховищем інформації про такі дані, як значення, відношення до інших даних, походження, використання та формат". Oracle визначає його як набір таблиць з метаданими. Термін може мати одне з декількох близьких значень, що відносяться до баз даних і систем управління базами даних (СУБД).
Документ, що описує базу даних або колекцію баз даних
Вбудований компонент СУБД, необхідний для визначення його структури
Частина проміжного програмного забезпечення, що розширює або витісняє рідний словник даних СУБД
Словники - це змінюваний упорядкований тип даних:
дані у словнику - це пари ключ: значение
доступ до значень здійснюється за ключом
дані у словнику впорядковані за порядком додавання елементів
словники можна змінювати, тобто елементи словника можна змінювати, додавати, видаляти
ключ має бути об'єктом незмінного типу: число, рядок, кортеж
значення може бути даними будь-якого типу
В інших мовах програмування (не Python) тип даних подібний до словника може називатися асоціативний масив, хеш або хеш-таблиця.
Множина — абстрактний тип даних і структура даних в інформатиці, є реалізацією математичного об'єкта скінченна множина.
Дані типу «множина» дозволяють зберігати обмежене число значень певного типу без певного порядку. Повторення значень, як правило, неприпустимо. За винятком того, що множина в програмуванні скінченне, воно загалом відповідає концепції математичної множини. Для цього типу в мовах програмування зазвичай передбачені стандартні операції над множинами.
Множини можна реалізувати, використовуючи різні структури даних, які забезпечують різні часові затрати і просторові компроміси для різних операцій. Деякі реалізації створені для того, щоб покращити ефективність дуже спеціалізованих операцій, таких як: nearest або union. Реалізації описані для «загального використання», як правило, прагнуть оптимізувати element_of, add та delete операції. Простою реалізацією є використання списку (абстрактний тип даних), ігноруючи порядок елементів та уникаючи їх повтору. Це просто, але неефективно, бо операції на перевірку належності у множині чи видалення елементу O(n) повинні сканувати увесь список. Замість цього, множини часто реалізуються з використанням більш ефективних структур даних, а саме, різних видів дерев, префіксних дерев або хеш-таблиць.
Так як множини можна інтерпретувати як щось на зразок карти (індикаторною функцією), вони зазвичай реалізуються у той самий спосіб, що і (часткові) карти (асоціативні масиви) – у цьому разі значення кожної пари ключа-значення має тип одиниці або контрольного елемента (наприклад, 1), а саме збалансоване дерево для відсортованого масиву (O(log n) для більшості операцій) або хеш-таблицю для невідсортованого масиву (O(1) в середньому випадку, але O(n) в найгіршому випадку, для більшості операцій). Відсортована лінійна хеш-таблиця може бути використана для забезпечення детерміновано впорядкованих множин.
Крім того, у мовах, які підтримують карти, а не множини, множини можуть бути реалізовані на основі карти. Наприклад, загальна ідіома у мові програмування Perl, що конвертує масив у хеш, чиї параметри приймають параметри контрольного елемента, для використання як масиву. Узагальненням поняття множини є мультимножина чи сумка (англ. bag), яка подібна на множину, але дозволяє дублікати (повторення однакових значень).
Мультимножина — в математиці, це множина в якій для кожного елемента запам'ятовується не лише його входження, але й кількість входжень.
Мультимножина – це сукупність елементів довільної природи, що можуть дублюватися (повторюватися).
На відміну від масиву, мультімножина є необмеженою колекцією; при конструюванні типу мультимножин не вказується гранична кардинальність значень цього типу. Однак це не означає, що можливість вставки елементів у мультімножину дійсно не обмежена; стандарт лише не вимагає явного оголошення кордону. Ситуація аналогічна тій, яка виникає при роботі з таблицями, для яких в SQL не оголосить максимально допустиму кількість рядків.
Черга (англ. queue) в програмуванні — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній «базарній» черзі, у якій спочатку обслуговують того, хто прийшов першим, потім наступного і так далі.
англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).
англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповненість" (англ. queue underflow).
Черга може бути реалізована за допомогою масиву Q[1...n], в якому зберігаються дані та двох додаткових змінних head[Q] та tail[Q], в яких зберігаються індекси відповідно "голови" та "хвоста" черги, length[Q] - довжина черги.
Черга з пріоритетами (англ. priority queue) — це структура даних, що призначена для обслуговування множини елементів, кожний з яких додатково має "пріоритет", пов'язаний з ним. У пріоритетній черзі першим обслуговується елемент, який має найвищий пріоритет, відповідно елемент, що має найнижчий пріоритет буде обслугований останнім. У деяких реалізаціях, якщо два елементи мають однаковий пріоритет, вони подаються відповідно до порядку, в якому вони були закладені, в той час як в інших реалізаціях упорядкування елементів з однаковим пріоритетом не визначено.
Хоча черги з пріоритетами часто реалізуються купами, вони концептуально відрізняються від них. Черга пріоритетів - це абстрактне поняття, як "список" або "карта"; так само, як список може бути реалізована зв'язаним списком або масивом, черга з пріоритетом може бути реалізована купою або безліччю інших методів, таких як невпорядкований масив.
Черга з пріоритетами повинна підтримувати принаймні такі операції:
is_empty: перевіряє, чи черга порожня.
insert_with_priority: додає елемент до черги з відповідним йому пріоритетом.
pull_highest_priority_element: вилучає з черги елемент, що має найвищий пріоритет, повертаючи його.
Інші назви: "pop_element (Off)", "get_maximum_element" або "get_front (most) _element".
Деякі конвенції змінюють порядок пріоритетів, вважаючи, що менші значення мають вищий пріоритет, тому це може бути відоме як "get_minimum_element", і часто в літературі називається "get-min".
Також цю операцію можна замінити двома окремими функціями: "peek_at_highest_priority_element" і "delete_element", які можуть бути об'єднані для створення "pull_highest_priority_element".
Крім того, peek (у цьому контексті часто називається find-max або find-min), що повертає елемент з найвищим пріоритетом, але не змінює чергу, часто реалізується, і майже завжди виконується за час O ( 1 ) {\displaystyle O(1)}. Ця операція та її продуктивність O ( 1 ) {\displaystyle O(1)}мають вирішальне значення для багатьох застосувань пріоритетних черг.
Сучасніші реалізації можуть підтримувати складніші операції, такі як pull_lowest_priority_element, що перевіряє перші кілька елементів з найвищим або найнижчим пріоритетом, очищаючи чергу, очищаючи підмножини черги, виконуючи пакетну вставку, об'єднуючи дві або більше черг в одну, збільшуючи пріоритет будь-якого елемента тощо.
З точки зору обчислювальної складності, пріоритетні черги узгоджуються з алгоритмами сортування. Семантика пріоритетних черг, пропонує метод сортування: вставляти всі елементи, які слід сортувати, в чергу пріоритетів, і послідовно видаляти їх, таким чином вони виходитимуть у відсортованому порядку. Насправді це процедура, яка використовується кількома алгоритмами сортування, після видалення рівня абстракції, що надається чергою пріоритету.
