Co je to abstraktní datový typ (ADT) a proč jej oddělit od jeho implementace?

Question

Accepted Answer

**Abstraktní datový typ** definuje sadu hodnot a **operace** na nich povolené, popsané čistě **chováním** – nikoli kódem. Implementace je konkrétní struktura (array, linked list, tree), která toto chování realizuje.

## Stejný ADT, různé implementace

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

## Proč je oddělit

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

## Běžné ADT a typické implementace

| ADT | Běžné implementace |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Proč je to důležité

Programování vůči ADT (rozhraní) udržuje kód flexibilní: implementaci si později můžete optimalizovat bez narušení volajících.

Zároveň zpřesňuje uvažování – nejdřív se rozhodnete, *jaké chování* potřebujete, a pak si vyberete nejlevnější strukturu, která je poskytuje.

ADT	Běžné implementace
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap