Što je apstraktni tip podataka (ADT) i zašto ga odvojiti od njegove implementacije?

Question

Accepted Answer

**Apstraktni tip podataka** definira skup vrijednosti i **operacije** dozvoljene na njima, opisane čisto kroz **ponašanje** — ne kroz kod. Implementacija je konkretna struktura (array, linked list, tree) koja ostvaruje to ponašanje.

## Isti ADT, različite 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.
```

## Zašto ih odvojiti

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

## Uobičajeni ADTs i tipične implementacije

| ADT | Uobičajene implementacije |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Zašto je to važno

Programiranje prema ADT-u (sučelju) čini kod fleksibilnim: kasnije možete optimizirati implementaciju bez prekidanja pozivača.

Također pojašnjava zaključivanje — prvo odlučite kakvo *ponašanje* trebate, zatim odaberite najjeftiniju strukturu koja ga pruža.

ADT	Uobičajene implementacije
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap