abstract data type (tsz. abstract data types)
A ADT vagyis absztrakt adatszerkezet (angolul: Abstract Data Type) egy elméleti modell arra, hogyan lehet adatokat rendszerezni és azokon műveleteket végezni — anélkül, hogy megmondanánk, hogyan valósítjuk ezt meg.
Az absztrakt adatszerkezet leírja:
Ez a szemlélet elválasztja az elméleti viselkedést az implementáció részleteitől.
push(x): új elem a verem tetejérepop(): a felső elem eltávolításatop(): a felső elem lekérdezéseisEmpty(): üres-e a verem?
| Fogalom | Leírás |
|---|---|
| Absztrakt adatszerkezet (ADT) | Csak azt mondja meg, mit csinálhatsz vele |
| Konkrét adatszerkezet | Azt is megmondja, hogyan csinálod meg (implementáció) |
| ADT | Lehetséges megvalósítás (adatszerkezet) |
|---|---|
| Verem | Tömb, láncolt lista |
| Sor | Körkörös tömb, láncolt lista |
| Lista | Dinamikus tömb (vector), láncolt lista |
| Halmaz | Hash tábla, bináris keresőfa (BST) |
| Térkép (kulcs-érték) | HashMap, Red-Black Tree |
| Prioritási sor | Bináris kupac, Fibonacci heap |
Egy ADT meghatározása:
pop(push(x)) = x, ha nem üres)
| ADT | Jellemző működés |
|---|---|
| Sor (Queue) | FIFO: First In, First Out |
| Verem (Stack) | LIFO: Last In, First Out |
| Lista (List) | Index alapján elérhető elemek |
| Halmaz (Set) | Ismétlődés nélküli elemek, műveletek: unió, metszet |
| Térkép (Map) | Kulcs-érték párok tárolása |
| Gráf (Graph) | Csomópontok és élek halmaza |
Az absztrakt adatszerkezet egy elméleti leírás: “Milyen adatokat tartalmaz, és milyen műveleteket lehet rajta végrehajtani” — de nem mondja meg, hogy hogyan csináljuk meg!
Ez a szemlélet programozási nyelvektől független, és segít moduláris, karbantartható és robosztus programokat írni.