Kaj je abstraktni tip podatkov (ADT) in zakaj ga ločiti od njegove implementacije?

Question

Accepted Answer

**Abstraktni tip podatkov** definira nabor vrednosti in **operacije**, ki so na njih dovoljene, opisane čisto s **vedenjem** — ne s kodo. Implementacija je konkretna struktura (polje, povezan seznam, drevo), ki to vedenje izvaja.

## Isti ADT, različne implementacije

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

## Zakaj jih ločiti

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

## Pogosti ADT-ji in tipične implementacije

| ADT | Pogoste implementacije |
|---|---|
| List | dinamično polje, povezan seznam |
| Sklad | polje, povezan seznam |
| Vrsta | ring buffer, povezan seznam |
| Preslikava | hash tabela, uravnoteženo drevo |
| Prioritetna vrsta | binarni kup |

## Zakaj je to pomembno

Programiranje v ADT (vmesnik) drži kodo fleksibilno: implementacijo lahko pozneje optimizirate brez preloma za klice.

Hkrati tudi izboljša razumevanje — najprej se odločite za *kakšno vedenje* potrebujete, nato pa izberete najcenejšo strukturo, ki jo zagotavlja.

ADT	Pogoste implementacije
List	dinamično polje, povezan seznam
Sklad	polje, povezan seznam
Vrsta	ring buffer, povezan seznam
Preslikava	hash tabela, uravnoteženo drevo
Prioritetna vrsta	binarni kup