O que é um tipo de dado abstrato (ADT) e por que separá-lo de sua implementação?

Question

Accepted Answer

Um **tipo de dado abstrato** define um conjunto de valores e as **operações** permitidas sobre eles, descritos puramente pelo **comportamento** — não pelo código. A implementação é a estrutura concreta (array, lista encadeada, árvore) que realiza esse comportamento.

## O mesmo ADT, diferentes implementações

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

## Por que separá-los

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

## ADTs comuns e implementações típicas

| ADT | Implementações comuns |
|---|---|
| List | dynamic array, linked list |
| Stack | array, linked list |
| Queue | ring buffer, linked list |
| Map | hash table, balanced tree |
| Priority Queue | binary heap |

## Por que isso importa

Programar para um ADT (uma interface) mantém o código flexível: você pode otimizar a implementação depois sem quebrar os chamadores.

Também aguça seu raciocínio — você decide primeiro *qual comportamento* precisa, depois escolhe a estrutura mais barata que o fornece.

ADT	Implementações comuns
List	dynamic array, linked list
Stack	array, linked list
Queue	ring buffer, linked list
Map	hash table, balanced tree
Priority Queue	binary heap