Mi az absztrakt adattípus (ADT) és miért érdemes szétválasztani az implementációtól?

Question

Accepted Answer

Az **absztrakt adattípus** értékek egy halmazát és az azokon engedélyezett **műveletek** határoz meg, tisztán a **viselkedés** által leírva — nem a kód által. Az implementáció a konkrét szerkezet (array, linked list, tree), amely ezt a viselkedést megvalósítja.

## Ugyanez az ADT, különböző implementációk

```text
ADT "Queue":  enqueue, dequeue, peek  (FIFO contract)

Implementation A: array + two indices (ring buffer)
Implementation B: doubly linked list with head/tail pointers
Both honor the SAME contract; cost profiles differ.
```

## Miért érdemes szétválasztani őket

```python
# Callers depend on the CONTRACT, not the internals
class Stack:
    def push(self, x): ...
    def pop(self): ...
    def peek(self): ...
# Swap a list for a linked list internally — callers never change.
```

## Közös ADT-k és tipikus implementációk

| ADT | Tipikus implementációk |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Miért fontos

Az ADT-ra (egy felületre) alapuló kódírás rugalmassá teszi a kódot: később optimalizálhatja az implementációt anélkül, hogy megtörné a hívókat.

Ezenkívül élesíti a gondolkodást — először eldöntöd, milyen *viselkedésre* van szükséged, majd kiválasztod a legolcsóbb struktúrát, amely azt biztosítja.

ADT	Tipikus implementációk
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap