Co to jest abstrakcyjny typ danych (ADT) i dlaczego oddzielać go od jego implementacji?

Question

Accepted Answer

**Abstrakcyjny typ danych** definiuje zbiór wartości i **operacje** dozwolone na nich, opisane wyłącznie przez **zachowanie** — nie przez kod. Implementacja to konkretna struktura (tablica, lista wiązana, drzewo), która realizuje to zachowanie.

## Ten sam ADT, różne implementacje

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

## Dlaczego to rozdzielić

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

## Wspólne ADT-y i typowe implementacje

| ADT | Typowe implementacje |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Dlaczego to ważne

Programowanie względem ADT-u (interfejsu) utrzymuje kod elastycznym: możesz później zoptymalizować implementację bez łamania wywoływaczy.

Ostrzeje to także twoje rozumowanie — najpierw decydujesz, *jakie zachowanie* jest potrzebne, a następnie wybierasz najtańszą strukturę, która je zapewnia.

ADT	Typowe implementacje
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap