ADT
Főnév
ADT (tsz. ADTs)
Az absztrakt adattípus (ADT) egy olyan elméleti, matematikai modellt jelent, amely meghatározza az adott típusú adatokon végrehajtható műveleteket és azok viselkedését, de nem foglalkozik azok konkrét implementációjával. Az ADT tehát egy tisztán absztrakt fogalom, amely elválasztja a műveletek logikai definícióját a belső adatreprezentációtól.
1. Az absztrakt adattípus fogalma
Az absztrakt adattípus egyértelműen meghatározza:
- milyen műveletek végezhetők el rajta (interface)
- ezeknek a műveleteknek milyen viselkedést kell biztosítaniuk (szemantika)
- milyen feltételek mellett érvényesek ezek a műveletek (elő- és utófeltételek)
Ezek a definíciók azonban nem tartalmazzák:
- milyen belső adattárolási technikákat kell használni (implementáció)
- milyen konkrét algoritmusokkal kell megvalósítani ezeket a műveleteket
2. Példa absztrakt adattípusra
Vegyük például a Stack (verem) ADT-t:
| Művelet | Leírás |
|---|---|
push(x) |
Az x elemet a verem tetejére helyezi. |
pop() |
Kiveszi a legfelső elemet a veremből. |
top() |
Megnézi, mi van a verem tetején. |
isEmpty() |
Eldönti, hogy a verem üres-e. |
size() |
Megadja a veremben tárolt elemek számát. |
Egy absztrakt stack definíciója például formálisan így írható le:
ADT Stack<T>
Operations:
push(Stack s, T elem): Stack // új elem beszúrása a verem tetejére
pop(Stack s): Stack // legfelső elem eltávolítása
top(Stack s): T // legfelső elem lekérdezése
isEmpty(Stack s): Boolean // ellenőrzi, hogy üres-e a verem
size(Stack s): Integer // elemszám lekérdezése
Ebből egyértelmű, mit kell tudnia egy veremnek, de az nincs meghatározva, hogy ezt hogyan valósítják meg (például tömbbel, láncolt listával, stb.).
3. Az ADT jellemzői
- Absztrakció: az implementáció részleteinek elrejtése.
- Egységes interfész: minden implementáció azonos viselkedést garantál.
- Encapsuláció (bezárás): a felhasználó csak az interfészt látja, a belső állapot nem látható.
- Újrahasznosíthatóság: ugyanaz az ADT más-más adatszerkezetekkel valósítható meg.
4. Az ADT és az adatszerkezet (data structure) közötti különbség
Az ADT-kat nem szabad összekeverni az adatszerkezetekkel:
| Absztrakt adattípus (ADT) | Adatszerkezet (Data Structure) |
|---|---|
| Egy absztrakt fogalom, amely az adat viselkedését és műveleteit írja le. | Konkrét implementáció, belső adatábrázolással. |
| Nem tartalmaz részleteket a belső reprezentációról. | Pontosan meghatározza, hogyan kell fizikailag tárolni az adatokat. |
| Stack (verem), Queue (sor), List (lista), Set (halmaz). | Tömb (array), láncolt lista (linked list), bináris fa (binary tree). |
Tehát az ADT egy koncepció, míg az adatszerkezet ennek egy adott megvalósítása.
5. Az ADT használatának előnyei
Modularitás
- Egy ADT interfész jól definiált, így könnyen beilleszthető bármilyen környezetbe.
Rugalmasság
- Az implementáció könnyen lecserélhető anélkül, hogy az ADT-t használó kódot meg kellene változtatni.
- Például, egy verem lehet tömb-alapú vagy láncolt listás, a felhasználó ebből semmit nem vesz észre.
Könnyű karbantartás és fejlesztés
- Az ADT tiszta interfésze miatt könnyen ellenőrizhető és tesztelhető.
Absztrakció szintjének növelése
- Az ADT segítségével magasabb szinten fogalmazhatjuk meg a feladatokat (például „verembe helyezés” vs. „array-ba beszúrás”)
6. Tipikus ADT példák
Néhány gyakran használt ADT példa:
- Stack (verem) – utoljára bekerült elem jön ki először (LIFO – Last In First Out)
- Queue (sor) – elsőnek bekerült elem jön ki először (FIFO – First In First Out)
- List (lista) – sorrendezett elemek, bárhova történő beszúrás és törlés lehetősége
- Set (halmaz) – egyedi elemek gyűjteménye, ismétlés nélkül
- Map (leképezés) – kulcs-érték párok tárolása, asszociatív kereséssel
- Priority Queue (prioritásos sor) – mindig a legmagasabb prioritású elem kerül ki először
7. Példa absztrakt adattípus definíciójára (Set – halmaz)
ADT Set<T>
Operations:
insert(Set s, T elem): Set // elem beszúrása a halmazba
remove(Set s, T elem): Set // elem eltávolítása a halmazból
contains(Set s, T elem): Boolean // elem halmazhoz tartozásának ellenőrzése
union(Set s1, Set s2): Set // két halmaz egyesítése
intersection(Set s1, Set s2): Set // két halmaz metszete
difference(Set s1, Set s2): Set // két halmaz különbsége
Ebben a definícióban nincs említés arról, hogy az elemeket miként tároljuk (például tömb, láncolt lista vagy hash-tábla formájában).
8. Összegzés
Az absztrakt adattípus (ADT) egy olyan formális, matematikai fogalom, amely absztrakt módon írja le az adatokon végezhető műveleteket és azok elvárt viselkedését. Az ADT-k révén lehetőségünk nyílik arra, hogy magasabb absztrakciós szinten gondolkodjunk, tisztán elkülönítve az adatok kezelésének logikáját a konkrét implementációtól.
Az ADT-k használata az alábbi előnyöket biztosítja:
- Rugalmasság és modularitás
- Könnyű karbantarthatóság
- Az implementációk könnyű cserélhetősége
- Tiszta és érthető szoftverarchitektúra kialakítása
Ezért a programtervezés során az absztrakt adattípusok az egyik legfontosabb alapfogalomnak tekintendők.