¿Qué es un tipo de dato abstracto (ADT) y por qué separarlo de su implementación?

Question

Accepted Answer

Un **tipo de dato abstracto** define un conjunto de valores y las **operaciones** permitidas en ellos, descritas puramente por **comportamiento** — no por código. La implementación es la estructura concreta (array, linked list, tree) que realiza ese comportamiento.

## El mismo ADT, diferentes implementaciones

```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 qué separarlos

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

## ADT comunes e implementaciones típicas

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

## Por qué es importante

Programar contra un ADT (una interfaz) mantiene el código flexible: puedes optimizar la implementación más tarde sin romper los llamadores.

También agudiza el razonamiento — primero decides *qué comportamiento* necesitas, luego eliges la estructura más barata que lo proporciona.

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