abstract data type
Főnév
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.
🧠 Alapgondolat
Az absztrakt adatszerkezet leírja:
- Mit lehet vele csinálni (műveletek),
- De nem mondja meg, hogyan csináljuk (implementáció).
Ez a szemlélet elválasztja az elméleti viselkedést az implementáció részleteitől.
📋 Példa: Verem (Stack) ADT
Műveletek (interface):
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?
Viselkedés:
- Utolsóként betett elem jön ki először → LIFO: Last In, First Out
- Nem tudsz közvetlenül hozzáférni az alsó elemekhez
Megvalósítás:
- Tömb (array) használatával
- Egyszerű láncolt listával
🛠️ Absztrakt adatszerkezet vs Konkrét adatszerkezet
| 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ó) |
Példák:
| 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 |
🎯 Miért hasznos az ADT?
- Elrejtjük a részleteket → tiszta interfész
- Könnyebb karbantartani → megváltoztathatjuk az implementációt, a külső kód nem sérül
- Átláthatóbb → világosan el van választva, hogy mit lehet csinálni és hogyan
- Újrafelhasználható → ugyanaz az elv, több különböző megvalósítással
📚 Formális definíció
Egy ADT meghatározása:
- Adathalmaz: milyen értékek tárolhatók
- Műveletek halmaza: milyen műveletek hajthatók végre
- Axiómák, szabályok: milyen elvek mentén működik (pl.
pop(push(x)) = x, ha nem üres)
🧪 További példák
| 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 |
✅ Összefoglalás
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.
- Collection
- Container
- List
- String
- Set
- multiset
- Map
- multimap
- Graph
- Tree
- Stack
- Queue
- priority queue
- double-ended queue
- double-ended priority queue
- abstract data type - Szótár.net (en-hu)
- abstract data type - Sztaki (en-hu)
- abstract data type - Merriam–Webster
- abstract data type - Cambridge
- abstract data type - WordNet
- abstract data type - Яндекс (en-ru)
- abstract data type - Google (en-hu)
- abstract data type - Wikidata
- abstract data type - Wikipédia (angol)