Tipos Abstractos de Datos

Objetivos observables¶

• Identificás el problema que modela el capítulo y el TAD/estructura más adecuada.

• Justificás decisiones de diseño con costo temporal/espacial y contrato de operaciones.

• Aplicás el contenido en Java sin romper invariantes ni contrato público.

Esta página introduce el tema con un lenguaje más intuitivo. Antes de discutir la definición formal, conviene fijar qué se considera un tipo abstracto de datos y por qué la representación no debería confundirse con la interfaz.

Viniendo de C, la intuición desarrollada nos lleva a pensar primero en la estructura concreta: struct, campos, punteros, arreglos, nodos. Aquí, invertiremos ese orden. Primero importa qué problema modela la estructura y qué operaciones promete. Recién después conviene decidir cómo se la representa en memoria.

Del problema a la interfaz¶

Un Tipo Abstracto de Datos (TAD) es un modelo matemático o lógico que describe:

1. un conjunto de valores posibles,

2. un conjunto de operaciones válidas sobre esos valores,

3. las reglas o axiomas que esas operaciones deben respetar.

Lo que no define es una única representación interna obligatoria en la memoria de la computadora.

Para entender esta diferencia, conviene pensar en una máquina expendedora. Como cliente, conocés su interfaz y su comportamiento observable: insertás dinero, presionás un botón con un código (B4) y obtenés un producto. Ese es el TAD. No necesitás saber si adentro hay un sistema de espirales metálicas, un brazo robótico o rieles inclinados. Esa mecánica interna es la estructura de datos concreta.

Una pila en programación puede modelarse de la misma manera:

• tiene un estado interno con cero o más elementos,

• permite apilar, desapilar y consultar el tope,

• respeta una política LIFO (Last In, First Out): lo último que entra es lo primero que sale.

Nada de ese modelo abstracto obliga todavía a usar:

• un arreglo de memoria contigua,

• una lista de nodos enlazados por punteros,

• o cualquier otra representación física.

Interfaz, representación y cliente¶

Conviene distinguir tres planos y cómo se relacionan a través de una barrera de abstracción:

En Java, esa separación suele expresarse con:

• una interfaz pública o un conjunto claro de métodos públicos,

• una clase concreta con atributos privados,

• y código cliente que trabaja contra el contrato, no contra detalles internos.

/**
 * TAD Pila (Stack).
 * @param <T> el tipo de elementos en la pila.
 */
public interface Pila<T> {
    /**
     * Agrega un elemento al tope de la pila.
     * @param elemento el elemento a apilar.
     */
    void apilar(T elemento);

    /**
     * Quita y devuelve el elemento en el tope de la pila.
     * @return el elemento desapilado.
     * @throws IllegalStateException si la pila está vacía.
     */
    T desapilar();

    /**
     * Devuelve el elemento en el tope de la pila sin quitarlo.
     * @return el elemento en el tope.
     * @throws IllegalStateException si la pila está vacía.
     */
    T verTope();

    /**
     * @return true si la pila no contiene elementos, false en caso contrario.
     */
    boolean estaVacia();
}

public class PilaArreglo<T> implements Pila<T> {
    // detalles internos ocultos protegidos por el encapsulamiento
}

public class PilaEnlazada<T> implements Pila<T> {
    // detalles internos ocultos protegidos por el encapsulamiento
}

Desde el punto de vista del cliente, ambas clases son válidas si respetan el mismo contrato.

El contrato de un TAD¶

Definir un TAD no es solo listar nombres de métodos. Como se vio en Diseño por Contratos, hace falta definir formalmente las obligaciones y garantías:

• qué hace cada operación (Postcondiciones),

• cuándo puede usarse (Precondiciones),

• qué devuelve o qué modifica (Efectos colaterales),

• qué errores o casos borde existen (Excepciones lanzadas si el cliente viola el contrato).

Por ejemplo, para la pila anterior:

Ese contrato ya alcanza para testear comportamiento (ver OOP 8: Testing en Programación Orientada a Objetos), incluso si no se sabe si la pila usa:

• un arreglo redimensionable,

• una lista enlazada,

• o una estructura híbrida.

Invariantes y representación¶

El contrato visible no alcanza para implementar bien una estructura. También hace falta sostener reglas internas que el cliente no ve, pero la implementación sí debe respetar rigurosamente. Esas reglas son las invariantes de representación (ver Diseño por Contratos).

Ejemplo: una cola implementada con arreglo circular podría exigir:

• que 0 <= cantidad <= capacidad,

• que frente siempre apunte al primer elemento lógico si la cola no está vacía,

• que fondo se actualice usando aritmética modular,

• que no existan “agujeros” lógicos entre frente y fondo.

El cliente no necesita conocer esos detalles. Sí necesita que las operaciones se comporten como cola FIFO.

El peligro de romper invariantes¶

Si una implementación no encapsula correctamente su estado interno, las invariantes pueden romperse. Imaginá una pila basada en un arreglo donde se expone (por error de diseño) el índice tope:

public class PilaRota<T> {
    public Object[] elementos = new Object[10];
    public int tope = -1; // ❌ ESTO ES UN PELIGRO
    
    public void apilar(T elemento) {
        tope++;
        elementos[tope] = elemento;
    }
}

Si el código cliente hace pila.tope = 5; sin haber apilado elementos reales, la invariante se rompe. A partir de ese momento, la estructura de datos es inconsistente y cualquier llamada a desapilar() probablemente lance excepciones internas no esperadas (como NullPointerException) o, peor aún, devuelva datos basura silenciosamente, incumpliendo el contrato del TAD.

Un mismo TAD, varias implementaciones¶

La separación entre TAD e implementación permite comparar alternativas de forma limpia.

Ejemplo: pila con arreglo vs pila enlazada¶

Las dos implementaciones sirven para el mismo TAD. Lo que cambia no es la definición del problema, sino:

• el costo de ciertas operaciones,

• el uso de memoria,

• la complejidad de implementación,

• y la conveniencia según el contexto.

Por qué esta separación mejora el diseño¶

Separar TAD de implementación da varias ventajas:

1. Permite reemplazar estructuras sin reescribir todo el cliente.

2. Obliga a pensar operaciones antes que campos.

3. Facilita testear comportamiento en lugar de detalles internos.

4. Hace comparables varias implementaciones del mismo problema.

5. Reduce acoplamiento entre el código que usa una estructura y el código que la implementa.

En términos de cursada, esto tiene una consecuencia importante: cuando se compare una estructura con otra en esta parte, no conviene mezclar dos preguntas distintas:

• “¿Qué TAD conviene para este problema?”

• “¿Qué implementación conviene para este TAD?”

No siempre tienen la misma respuesta.

TAD, clases e interfaces¶

En Java, un TAD no coincide automáticamente con una interface, pero esa suele ser una buena forma de expresarlo.

Conviene pensar así:

• el TAD es la idea abstracta,

• la interfaz o la API pública es su traducción al código,

• la clase concreta resuelve la representación,

• y los tests deberían verificar el contrato observable.

public class Navegador {
    private final Pila<String> historial;

    public Navegador(Pila<String> historial) {
        this.historial = historial;
    }

    public void visitar(String url) {
        this.historial.apilar(url);
    }

    public String volver() {
        return this.historial.desapilar();
    }
}

Navegador no necesita saber si historial usa nodos o arreglo. Necesita solamente que el comportamiento de pila sea correcto.

Qué errores conviene evitar¶

En esta parte conviene vigilar varios errores frecuentes:

1. Confundir el TAD con la representación. “Una pila es un arreglo” es falso; una pila puede implementarse con arreglo.

2. Diseñar desde campos en lugar de operaciones. Eso suele producir APIs pobres y muy acopladas.

3. Exponer detalles internos. Si el cliente depende del tope, del arreglo interno o de nodos concretos, el reemplazo de implementación se vuelve caro.

4. Comparar implementaciones sin fijar el contrato. Si no está claro qué operaciones importan, la comparación queda vacía.

Resumen¶

Un TAD nombra un problema y una interfaz, no una estructura física única. Esa diferencia permite:

• discutir comportamiento sin casarse con una representación,

• comparar varias implementaciones del mismo TAD,

• proteger invariantes internos,

• y diseñar código cliente menos acoplado.

En esta parte, cada familia de estructuras conviene leer así: primero el problema abstracto, después las variantes concretas que lo resuelven.

Ejercicios¶

Próximo paso¶

Para seguir, conviene pasar a Análisis de algoritmos, donde aparece el criterio de comparación que después se reutiliza en toda la parte.