Kas yra abstraktusis duomenų tipas (ADT) ir kodėl jį reikia atskirti nuo jo implementacijos?

Question

Accepted Answer

**Abstraktusis duomenų tipas** apibrėžia reikšmių rinkinį ir **operacijas**, kurias galima atlikti su jais, aprašomus grynai pagal **elgesį** — ne pagal kodą. Implementacija yra konkreti struktūra (masyvas, susietas sąrašas, medis), kuri realizuoja tą elgesį.

## Tas pats ADT, skirtingos implementacijos

```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.
```

## Kodėl juos atskirti

```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.
```

## Dažni ADT ir tipinės implementacijos

| ADT | Dažnos implementacijos |
|---|---|
| List | dinaminis masyvas, susietas sąrašas |
| Stack | masyvas, susietas sąrašas |
| Queue | žiedinė buferinė atmintis, susietas sąrašas |
| Map | maišos lentelė, balansuotas medis |
| Priority Queue | dvejetainis krūvis |

## Kodėl tai svarbu

Programavimas pagal ADT (sąsają) daro kodą lanksčiu: vėliau galite optimizuoti implementaciją netrukdydami iškviečiančiajam kodui.

Tai taip pat paaiškina samprotavimą — pirmiausia nusprendžiate, kokio *elgesio* jums reikia, o tada pasirenkate pigiausią struktūrą, kuri jį suteikia.

ADT	Dažnos implementacijos
List	dinaminis masyvas, susietas sąrašas
Stack	masyvas, susietas sąrašas
Queue	žiedinė buferinė atmintis, susietas sąrašas
Map	maišos lentelė, balansuotas medis
Priority Queue	dvejetainis krūvis