Абстрактний тип даних (АТД) — це математична модель для типів даних, де тип даних визначається поведінкою (семантикою) з точки зору користувача даних, а саме в термінах можливих значень, можливих операцій над даними цього типу і поведінки цих операцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення — в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних зазвичай подаються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних намагаються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не за швидкістю) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Приклади
Наприклад, цілі числа — це абстрактний тип даних, який визначається як значення …, −2, −1, 0, 1, 2, … , і поводиться відповідно до звичної математики (з увагою про цілочисельне ділення), за допомогою операцій додавання, віднімання, множення і ділення, а також операції більше ніж, менше ніж і т. д. незалежно від того, як цілі числа представлені за допомогою комп'ютера. Очевидно, що «поведінка» включає в себе різні аксіоми (асоціативність і комутативність складання і т. д.) і умови за операціями (не може ділити на нуль). Зазвичай цілі числа представлені в структурі даних у вигляді двійкових чисел, найчастіше як доповняльний код, але може бути двійково-десятковий код або обернений код, але користувач абстрагується від конкретного вибору уявлення, і може просто використовувати ці дані у вигляді цілих чисел.
АТД складається не тільки з операцій, але і значень початкових даних і обмежень на операції. «Інтерфейс», як правило, стосується лише операцій, і, можливо, деяких з обмежень на операції, зокрема попередні умови і постумови, але не інші обмеження, такі як відносини між операціями.
Наприклад, абстрактний стек, який має LIFO структуру, може бути визначений за допомогою трьох операцій: PUSH, котра вставляє елемент даних в стек; POP, яка видаляє елемент даних з нього; і PEEK або TOP, яка отримує доступ до елементу даних в вершині стека без видалення. Абстрактна черга, яка має FIFO структуру, також буде мати три операції: ENQUEUE, яка вставляє елемент даних в чергу; DEQUEUE, яка видаляє перший елемент даних з нього; і FRONT, що отримує доступ і служить першим елементом даних в черзі. Там не було б ніякої можливості диференціювати ці два типи даних, якщо математичне обмеження не вводиться, тоді це для стека вказує, що кожна POP завжди повертає найостанніший втиснутий елемент, який ще не вискочив. При аналізі ефективності алгоритмів, які використовують стеки, можна також вказати, що всі операції не приймають той же самий час, незалежно від того, скільки елементів даних були витіснені в стек, і що стек використовує постійну кількість схов для кожного елемента.
Вступ
Абстрактні типи даних — це чисто теоретичні об'єкти, які використовуються (між іншим) для спрощення опису абстрактних алгоритмів, також для класифікації та оцінки структури даних, і формального опису систем типів мов програмування. Проте АТД можуть бути реалізовані за допомогою певних типів даних або структур даних, у багатьох відношеннях і в багатьох мовах програмування; або описані в формальній мові специфікації. АТД часто реалізуються у вигляді модулів: інтерфейс модуля оголошує процедури, які відповідають операціям АТД, іноді з коментарями, які описують обмеження. Ця стратегія приховування інформації дозволяє реалізації модуля бути зміненою без порушення клієнтських програм.
Термін Абстрактний Тип Даних також можна розглядати, як узагальнений підхід ряду алгебричних структур, таких, як решітки, групи і кільця., Chapter 7,section 40. Поняття абстрактних типів даних пов'язане з поняттям абстракції даних, це важливо в об'єктно-орієнтованому програмування та методології проектування за контрактом на розробку програмного забезпечення.
Визначення абстрактного типу даних
Абстрактний тип даних визначається як математична модель об'єктів даних, які становлять тип даних, а також функції, які працюють на цих об'єктах. Там немає стандартних конвенцій, для визначення їх. Широкий поділ може бути проведений між «імперативними» і «функціональним» стилів визначення.
Визначення імперативного стилю
У філософії імперативних мов програмування, абстрактна структура даних задумана як сутність, яка є змінним-це означає, що він може перебувати в різних станах в різний час. Деякі операції можуть змінити стан АТД; таким чином, порядок, в якому оцінюються операції має важливе значення, і та ж сама операція на одних і тих же суб'єктах, можуть мати різні ефекти, якщо виконуються в різний час, так само, як інструкції комп'ютера, або команди і процедури імперативної мови. Щоб підкреслити цю точку зору, прийнято казати, що операції виконуються або застосовуються, не стільки, скільки оцінюються. Імперативний стиль часто використовується при описі абстрактних алгоритмів. (Дивіться Мистецтво програмування Дональда Кнута для отримання більш докладної інформації)
Абстрактна змінна
Визначення імперативного стилю АТД часто залежать від поняття абстрактної змінної, яку можна розглядати, як найпростіший нетривіальний АТД. Абстрактна змінна V є змінний об'єкт, який допускає дві операції: store(V, х), де х є значення невизначеного характеру; fetch(V), що дає значення, з тим обмеженням, що fetch(V) завжди повертає значення х, котре використовуються в самий останній операції store(V, х) на тій же самій змінної V. Як і в багатьох мовах програмування, операція store(V, x) часто пишеться V ← x (або деякі аналогічні позначення) і fetch(V) мається на увазі кожен раз, коли змінна V використовується в контексті, де потрібно значення. Так, наприклад, V ← V + 1 зазвичай розуміється, як скорочення для store(V,fetch(V) + 1).
У цьому визначенні неявно передбачається, що збереження значення в змінну U не робить ніякого впливу на стан окремої змінної V. Для того, щоб зробити це припущення явним, можна було б додати, що обмеження якщо U і V є різні змінні, то послідовність { store(U, x); store(V, y) } еквівалентна послідовності store(V, y); store(U, x) }. У більш загальному плані, при визначенні АТД часто припускають, що будь-яка операція, яка змінює стан одного екземпляра АТД не робить ніякого впливу на стан будь-якого іншого екземпляру (в тому числі інших екземплярів одного і того ж АТД), хіба тільки аксіоми АТД не означають, що два екземпляри пов'язані (псевдонімами) в цьому сенсі. Наприклад, при розширенні визначення абстрактної змінної, щоб включити абстрактні структури, операція, яка вибирає поле з структурою змінної R повинен дати змінну V, яка є псевдонімом до тієї частини R.
Означення абстрактної змінної V може також обмежити записані значення x членів певної множини X, називається діапазон, або тип V. Як і в мовах програмування, такі обмеження можуть спростити опис і аналіз алгоритмів, а також поліпшити їх читаність.
Зверніть увагу, що це визначення нічого не говорить про результат оцінки fetch(V), коли V є не-ініціалізована, тобто, перед виконанням будь-якої операції збереження на V. Алгоритм, який робить це, як правило, вважається недійсним, оскільки його ефект не визначений. (Проте, є деякі важливі алгоритми, ефективність яких значною мірою залежить від припущення, що така вибірка є законною, і повертає деяке довільне значення в діапазоні змінної.)
Створення екземпляра Деяким алгоритмам необхідно створювати нові екземпляри деякого АТД (наприклад, нові змінні, або нові стеки). Для опису таких алгоритмів, він, як правило, включає в АТД визначення операції Create(), який дає екземпляр АТД, як правило, з аксіом, еквівалентних результат операції Create() відрізняється від будь-якого екземпляру, які використовується алгоритмом. Ця аксіома може бути посилена, щоб виключити також часткове накладення спектрів з іншими екземплярами. З іншого боку, ця аксіома досі дозволяє реалізації операції Create() отримати раніше створений екземпляр, який став недоступним для програми.
Приклад: абстрактний стек (імперативний стиль) Як інший приклад, визначення абстрактного стека імперативним стилем може вказати, що стан стека S може бути змінений тільки за допомогою операцій push(S, x), де х деяке значення невизначеного характеру; pop(S), що надає значення як результат, з тим обмеженням, що Для будь-якого значення х і будь-якої абстрактної змінної V, послідовність операцій { push(S,x); V ← pop(S)} еквівалентна операції V ← x. Так як привласнення V ← x, за визначенням, не може змінити стан S, ця умова означає, що V ← pop(S) відновлює S в стан він мав до операції push(S,x). З цієї умови і з властивостей абстрактних змінних, то це означає, наприклад, що послідовність
{ push(S, x); push(S, y); U ← pop(S); push(S, z); V ← pop(S); W ← pop(S) }
де х, у та z є будь-які значення, а U, V, W попарно різні змінні, еквівалентно
{ U ← y; V ← z; W ← x }
При цьому неявно передбачається, що операції на екземплярі стека не змінюють стан будь-якого іншого екземпляру АТД, в тому числі інших стеків; а саме Для будь-яких значень x, y, а також будь-яких різних стеків S і T, послідовність { push(S,x); push(T,y)} еквівалентна послідовності { push(T,y); push(S,x)}. Абстрактне визначення стека зазвичай включає в себе також булеву функцію empty(S) і операцію create(), яка повертає екземпляр стека, з аксіом, еквівалентних create() ≠ S для будь-якого стека S (новостворений стек відрізняється від усіх попередніх стеків); empty(create()) (новостворений стек порожній); not empty(push(S, x)) (заштовхуючи щось в стек робить його непустим);
Стиль одного екземпляру
Іноді АТД визначається так, якби тільки один його екземпляр існував під час виконання алгоритму, і всі операції були застосовані до цього екземпляру, який явно не записаний. Наприклад, абстрактний стек, який вказано вище, може бути визначений з операціями push(x) та pop(), які працюють на єдиному існуючому стеку. Визначення АТД в цьому стилі можна легко переписати, щоб визнати, що кілька екземплярів АТД співіснують, шляхом додавання явного параметра екземпляру (наприклад, S в попередньому прикладі) для кожної операції, яка використовує або змінює неявне екземпляр.
З іншого боку, деякі АТД не можуть бути визначені за значенням, не припускаючи декількох екземплярів. Це той випадок, коли одна операція приймає два різних екземпляра АДТ як параметри. Для прикладу, розглянемо доповнюючи визначення абстрактного стека з операцією compare(S, T), яка перевіряє, чи стеки S і Т містять одні й ті ж елементи в тому ж порядку.
Визначення функціонального стилю