Ir al contenido

Tipos Abstractos de Datos (TAD) - Guía Completa

Publicado: a las  02:11 a. m.

Tipos Abstractos de Datos (TAD) - Guía Completa

Tipos abstractos de datos

🎯 ¿Qué son los Tipos Abstractos de Datos?

Imaginate que estás diseñando un sistema de control para una planta industrial. Tenés que gestionar:

Para cada uno de estos problemas, necesitás una estructura de datos diferente. Eso es exactamente lo que son los Tipos Abstractos de Datos (TAD).

Definición formal

Un TAD es una especificación matemática de un conjunto de datos y las operaciones que se pueden realizar sobre ellos, sin importar cómo se implementen internamente.

Analogía: Es como un control remoto. Sabés que tiene botones para encender, cambiar canal y ajustar volumen, pero no necesitás saber cómo funciona el circuito interno. Solo te importa qué hace, no cómo lo hace.

Los dos niveles de un TAD

  1. Nivel abstracto (interfaz): ¿Qué operaciones puedo hacer?
  2. Nivel concreto (implementación): ¿Cómo se hacen esas operaciones?

📚 Los TAD más importantes

Vamos a estudiar los 5 TAD fundamentales que todo programador debe conocer:

TADCaracterísticaEjemplo del mundo real
Pila (Stack)LIFO - Último en entrar, primero en salirPila de platos
Cola (Queue)FIFO - Primero en entrar, primero en salirCola del banco
Lista (List)Secuencia ordenada con acceso por índiceLista de reproducción
Conjunto (Set)Elementos únicos sin ordenNúmeros de DNI
Diccionario (Dictionary)Pares clave-valorAgenda telefónica

📦 1. Pila (Stack) - LIFO

¿Qué es una pila?

Una pila es como una pila de platos: solo podés agregar o quitar platos desde arriba. El último que pusiste es el primero que sacás (LIFO: Last In, First Out).

Operaciones básicas

Visualización

        ┌─────────┐
push →  │ Elem 3  │  ← pop (último en entrar, primero en salir)
        ├─────────┤
        │ Elem 2  │
        ├─────────┤
        │ Elem 1  │
        └─────────┘

Implementación desde cero

class Pila:
    """
    Implementación de una Pila (Stack) usando lista de Python
    """

    def __init__(self):
        """Inicializa una pila vacía"""
        self._items = []

    def push(self, elemento):
        """Apila un elemento en el tope"""
        self._items.append(elemento)

    def pop(self):
        """Desapila y retorna el elemento del tope"""
        if self.is_empty():
            raise IndexError("No se puede desapilar de una pila vacía")
        return self._items.pop()

    def peek(self):
        """Retorna el elemento del tope sin quitarlo"""
        if self.is_empty():
            raise IndexError("La pila está vacía")
        return self._items[-1]

    def is_empty(self):
        """Verifica si la pila está vacía"""
        return len(self._items) == 0

    def size(self):
        """Retorna la cantidad de elementos"""
        return len(self._items)

    def __str__(self):
        """Representación en string de la pila"""
        return f"Pila({self._items})"

# Ejemplo de uso
pila = Pila()
pila.push("Producto A")
pila.push("Producto B")
pila.push("Producto C")

print(pila)                    # Pila(['Producto A', 'Producto B', 'Producto C'])
print(f"Tope: {pila.peek()}")  # Tope: Producto C
print(f"Desapilado: {pila.pop()}")  # Desapilado: Producto C
print(f"Tamaño: {pila.size()}")     # Tamaño: 2

Ejemplo industrial: Control de historial de estados

class ControladorProceso:
    """
    Controlador que mantiene un historial de estados usando una pila
    Permite deshacer cambios (como Ctrl+Z)
    """

    def __init__(self):
        self.estado_actual = "DETENIDO"
        self.historial = Pila()

    def cambiar_estado(self, nuevo_estado):
        """Cambia el estado guardando el anterior en el historial"""
        # Guardar estado actual en la pila
        self.historial.push(self.estado_actual)
        self.estado_actual = nuevo_estado
        print(f"✅ Estado cambiado a: {nuevo_estado}")

    def deshacer(self):
        """Deshace el último cambio de estado"""
        if not self.historial.is_empty():
            self.estado_actual = self.historial.pop()
            print(f"↩️ Estado restaurado a: {self.estado_actual}")
        else:
            print("❌ No hay cambios para deshacer")

    def mostrar_estado(self):
        print(f"📊 Estado actual: {self.estado_actual}")
        print(f"📜 Historial: {self.historial}")

# Uso
controlador = ControladorProceso()
controlador.mostrar_estado()

controlador.cambiar_estado("INICIANDO")
controlador.cambiar_estado("EN_MARCHA")
controlador.cambiar_estado("PAUSA")
controlador.mostrar_estado()

controlador.deshacer()  # Vuelve a EN_MARCHA
controlador.deshacer()  # Vuelve a INICIANDO
controlador.mostrar_estado()

Aplicaciones reales de pilas

  1. Historial del navegador (botón “atrás”)
  2. Ctrl+Z / Deshacer en editores
  3. Evaluación de expresiones matemáticas
  4. Llamadas a funciones (call stack)
  5. Navegación entre pantallas en apps

🚶 2. Cola (Queue) - FIFO

¿Qué es una cola?

Una cola es como la fila del supermercado: el primero que llega es el primero que se atiende (FIFO: First In, First Out).

Operaciones básicas

Visualización

dequeue ←  [Elem 1] [Elem 2] [Elem 3]  ← enqueue
           (frente)           (final)

           Primero en entrar, primero en salir

Implementación desde cero

class Cola:
    """
    Implementación de una Cola (Queue) usando lista de Python
    """

    def __init__(self):
        """Inicializa una cola vacía"""
        self._items = []

    def enqueue(self, elemento):
        """Encola un elemento al final"""
        self._items.append(elemento)

    def dequeue(self):
        """Desencola y retorna el elemento del frente"""
        if self.is_empty():
            raise IndexError("No se puede desencolar de una cola vacía")
        return self._items.pop(0)

    def front(self):
        """Retorna el elemento del frente sin quitarlo"""
        if self.is_empty():
            raise IndexError("La cola está vacía")
        return self._items[0]

    def is_empty(self):
        """Verifica si la cola está vacía"""
        return len(self._items) == 0

    def size(self):
        """Retorna la cantidad de elementos"""
        return len(self._items)

    def __str__(self):
        """Representación en string de la cola"""
        return f"Cola({self._items})"

# Ejemplo de uso
cola = Cola()
cola.enqueue("Tarea 1")
cola.enqueue("Tarea 2")
cola.enqueue("Tarea 3")

print(cola)                      # Cola(['Tarea 1', 'Tarea 2', 'Tarea 3'])
print(f"Frente: {cola.front()}")  # Frente: Tarea 1
print(f"Desencolado: {cola.dequeue()}")  # Desencolado: Tarea 1
print(f"Tamaño: {cola.size()}")          # Tamaño: 2

Implementación eficiente con deque

from collections import deque

class ColaEficiente:
    """
    Cola implementada con deque (más eficiente para operaciones en ambos extremos)
    """

    def __init__(self):
        self._items = deque()

    def enqueue(self, elemento):
        self._items.append(elemento)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Cola vacía")
        return self._items.popleft()  # O(1) en vez de O(n)

    def front(self):
        if self.is_empty():
            raise IndexError("Cola vacía")
        return self._items[0]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

    def __str__(self):
        return f"Cola({list(self._items)})"

Ejemplo industrial: Sistema de tareas para robots

class SistemaTareas:
    """
    Sistema de gestión de tareas para robots industriales
    Las tareas se ejecutan en orden de llegada (FIFO)
    """

    def __init__(self, nombre_robot):
        self.nombre_robot = nombre_robot
        self.cola_tareas = ColaEficiente()
        self.tareas_completadas = []

    def agregar_tarea(self, tarea):
        """Agrega una tarea a la cola"""
        self.cola_tareas.enqueue(tarea)
        print(f"➕ Tarea agregada: {tarea}")

    def ejecutar_siguiente_tarea(self):
        """Ejecuta la siguiente tarea en la cola"""
        if not self.cola_tareas.is_empty():
            tarea = self.cola_tareas.dequeue()
            print(f"⚙️ {self.nombre_robot} ejecutando: {tarea}")
            self.tareas_completadas.append(tarea)
            return tarea
        else:
            print("✅ No hay más tareas pendientes")
            return None

    def ver_pendientes(self):
        """Muestra las tareas pendientes"""
        print(f"\n📋 Tareas pendientes ({self.cola_tareas.size()}):")
        print(self.cola_tareas)

    def ver_completadas(self):
        """Muestra las tareas completadas"""
        print(f"\n✅ Tareas completadas ({len(self.tareas_completadas)}):")
        print(self.tareas_completadas)

# Uso
robot = SistemaTareas("Robot-001")

# Agregar tareas
robot.agregar_tarea("Verificar sensores")
robot.agregar_tarea("Mover producto A a zona 2")
robot.agregar_tarea("Apilar cajas en pallet 3")
robot.agregar_tarea("Calibrar brazo robótico")

robot.ver_pendientes()

# Ejecutar tareas
robot.ejecutar_siguiente_tarea()
robot.ejecutar_siguiente_tarea()

robot.ver_pendientes()
robot.ver_completadas()

Aplicaciones reales de colas

  1. Impresoras (cola de impresión)
  2. Sistemas operativos (cola de procesos)
  3. Atención al cliente (call center)
  4. Streaming de video (buffer)
  5. Robots industriales (cola de tareas)

📋 3. Lista (List)

¿Qué es una lista?

Una lista es una secuencia ordenada de elementos donde podés acceder a cualquier posición por su índice.

Operaciones básicas

Ejemplo industrial: Lista de sensores

class SistemaMonitoreo:
    """
    Sistema de monitoreo con lista de sensores
    """

    def __init__(self):
        self.sensores = []

    def agregar_sensor(self, id_sensor, tipo, ubicacion):
        """Agrega un sensor al sistema"""
        sensor = {
            'id': id_sensor,
            'tipo': tipo,
            'ubicacion': ubicacion,
            'activo': True,
            'valor': 0
        }
        self.sensores.append(sensor)
        print(f"✅ Sensor {id_sensor} agregado")

    def actualizar_lectura(self, id_sensor, valor):
        """Actualiza la lectura de un sensor"""
        for sensor in self.sensores:
            if sensor['id'] == id_sensor:
                sensor['valor'] = valor
                print(f"📊 {id_sensor}: {valor}")
                return
        print(f"❌ Sensor {id_sensor} no encontrado")

    def listar_sensores(self):
        """Lista todos los sensores"""
        print("\n📡 SENSORES REGISTRADOS")
        print("=" * 60)
        for i, sensor in enumerate(self.sensores):
            estado = "🟢" if sensor['activo'] else "🔴"
            print(f"{i+1}. {estado} {sensor['id']} - {sensor['tipo']} "
                  f"({sensor['ubicacion']}) = {sensor['valor']}")

    def obtener_sensor(self, indice):
        """Obtiene un sensor por su índice"""
        if 0 <= indice < len(self.sensores):
            return self.sensores[indice]
        return None

    def eliminar_sensor(self, id_sensor):
        """Elimina un sensor del sistema"""
        for i, sensor in enumerate(self.sensores):
            if sensor['id'] == id_sensor:
                self.sensores.pop(i)
                print(f"🗑️ Sensor {id_sensor} eliminado")
                return
        print(f"❌ Sensor {id_sensor} no encontrado")

# Uso
sistema = SistemaMonitoreo()

# Agregar sensores
sistema.agregar_sensor("TEMP-001", "Temperatura", "Caldera")
sistema.agregar_sensor("PRES-001", "Presión", "Línea A")
sistema.agregar_sensor("NIV-001", "Nivel", "Tanque 1")

# Actualizar lecturas
sistema.actualizar_lectura("TEMP-001", 85.5)
sistema.actualizar_lectura("PRES-001", 7.2)
sistema.actualizar_lectura("NIV-001", 3.8)

# Listar todos
sistema.listar_sensores()

# Acceder por índice
sensor = sistema.obtener_sensor(0)
print(f"\nPrimer sensor: {sensor['id']}")

🎲 4. Conjunto (Set)

¿Qué es un conjunto?

Un conjunto es una colección de elementos únicos sin orden específico. No permite duplicados.

Operaciones básicas

Ejemplo industrial: Control de IDs únicos

class RegistroDispositivos:
    """
    Registro de dispositivos que garantiza IDs únicos
    """

    def __init__(self):
        self.ids_registrados = set()
        self.dispositivos = {}

    def registrar_dispositivo(self, id_dispositivo, tipo, ubicacion):
        """Registra un dispositivo con ID único"""
        if id_dispositivo in self.ids_registrados:
            print(f"❌ Error: El ID {id_dispositivo} ya está registrado")
            return False

        self.ids_registrados.add(id_dispositivo)
        self.dispositivos[id_dispositivo] = {
            'tipo': tipo,
            'ubicacion': ubicacion
        }
        print(f"✅ Dispositivo {id_dispositivo} registrado")
        return True

    def dar_de_baja(self, id_dispositivo):
        """Da de baja un dispositivo"""
        if id_dispositivo in self.ids_registrados:
            self.ids_registrados.remove(id_dispositivo)
            del self.dispositivos[id_dispositivo]
            print(f"🗑️ Dispositivo {id_dispositivo} dado de baja")
        else:
            print(f"❌ Dispositivo {id_dispositivo} no encontrado")

    def verificar_disponibilidad(self, id_dispositivo):
        """Verifica si un ID está disponible"""
        disponible = id_dispositivo not in self.ids_registrados
        estado = "disponible" if disponible else "en uso"
        print(f"ID {id_dispositivo}: {estado}")
        return disponible

    def listar_todos(self):
        """Lista todos los dispositivos registrados"""
        print(f"\n📋 DISPOSITIVOS REGISTRADOS ({len(self.ids_registrados)})")
        print("=" * 60)
        for id_disp in sorted(self.ids_registrados):
            info = self.dispositivos[id_disp]
            print(f"  • {id_disp} - {info['tipo']} ({info['ubicacion']})")

# Uso
registro = RegistroDispositivos()

# Registrar dispositivos
registro.registrar_dispositivo("SENS-001", "Sensor Temp", "Caldera")
registro.registrar_dispositivo("SENS-002", "Sensor Presión", "Línea A")
registro.registrar_dispositivo("SENS-001", "Sensor Nivel", "Tanque")  # ❌ Duplicado

# Verificar disponibilidad
registro.verificar_disponibilidad("SENS-003")
registro.verificar_disponibilidad("SENS-001")

# Listar todos
registro.listar_todos()

Operaciones de conjuntos

# Ejemplo: Turnos de operarios
turno_mañana = {"Juan", "María", "Pedro", "Ana"}
turno_tarde = {"María", "Carlos", "Ana", "Luis"}

# Operarios que trabajan en ambos turnos (intersección)
ambos_turnos = turno_mañana & turno_tarde
print(f"Trabajan en ambos turnos: {ambos_turnos}")  # {'María', 'Ana'}

# Todos los operarios (unión)
todos = turno_mañana | turno_tarde
print(f"Todos los operarios: {todos}")

# Solo trabajan en la mañana (diferencia)
solo_mañana = turno_mañana - turno_tarde
print(f"Solo turno mañana: {solo_mañana}")  # {'Juan', 'Pedro'}

📖 5. Diccionario (Dictionary)

¿Qué es un diccionario?

Un diccionario almacena pares clave-valor. Es como una agenda telefónica: buscás por nombre (clave) y obtenés el teléfono (valor).

Operaciones básicas

Ejemplo industrial: Configuración de planta

class ConfiguracionPlanta:
    """
    Sistema de configuración usando diccionarios
    """

    def __init__(self, nombre_planta):
        self.nombre_planta = nombre_planta
        self.configuracion = {
            'temperatura_maxima': 100,
            'presion_maxima': 10,
            'nivel_minimo': 0.2,
            'nivel_maximo': 0.9,
            'modo_operacion': 'AUTOMATICO'
        }
        self.sensores = {}
        self.alarmas = {}

    def configurar_parametro(self, parametro, valor):
        """Configura un parámetro del sistema"""
        self.configuracion[parametro] = valor
        print(f"⚙️ {parametro} = {valor}")

    def obtener_parametro(self, parametro):
        """Obtiene el valor de un parámetro"""
        return self.configuracion.get(parametro, "No configurado")

    def registrar_sensor(self, id_sensor, config):
        """Registra un sensor con su configuración"""
        self.sensores[id_sensor] = config
        print(f"📡 Sensor {id_sensor} registrado")

    def actualizar_sensor(self, id_sensor, clave, valor):
        """Actualiza un valor específico de un sensor"""
        if id_sensor in self.sensores:
            self.sensores[id_sensor][clave] = valor
            print(f"✅ {id_sensor}.{clave} = {valor}")
        else:
            print(f"❌ Sensor {id_sensor} no encontrado")

    def generar_alarma(self, codigo, mensaje, prioridad):
        """Genera una alarma"""
        self.alarmas[codigo] = {
            'mensaje': mensaje,
            'prioridad': prioridad,
            'activa': True
        }
        print(f"🚨 ALARMA {codigo}: {mensaje} (Prioridad: {prioridad})")

    def mostrar_configuracion(self):
        """Muestra toda la configuración"""
        print(f"\n⚙️ CONFIGURACIÓN DE {self.nombre_planta}")
        print("=" * 60)
        for param, valor in self.configuracion.items():
            print(f"  {param}: {valor}")

    def mostrar_sensores(self):
        """Muestra todos los sensores"""
        print(f"\n📡 SENSORES ({len(self.sensores)})")
        print("=" * 60)
        for id_sensor, config in self.sensores.items():
            print(f"  {id_sensor}:")
            for clave, valor in config.items():
                print(f"    - {clave}: {valor}")

    def mostrar_alarmas_activas(self):
        """Muestra alarmas activas"""
        activas = {k: v for k, v in self.alarmas.items() if v['activa']}
        print(f"\n🚨 ALARMAS ACTIVAS ({len(activas)})")
        print("=" * 60)
        for codigo, info in activas.items():
            print(f"  [{info['prioridad']}] {codigo}: {info['mensaje']}")

# Uso
planta = ConfiguracionPlanta("Planta El Calafate")

# Configurar parámetros
planta.configurar_parametro('temperatura_maxima', 95)
planta.configurar_parametro('modo_operacion', 'MANUAL')

# Registrar sensores
planta.registrar_sensor('TEMP-001', {
    'tipo': 'Temperatura',
    'ubicacion': 'Caldera',
    'unidad': '°C',
    'valor': 0,
    'activo': True
})

planta.registrar_sensor('PRES-001', {
    'tipo': 'Presión',
    'ubicacion': 'Línea A',
    'unidad': 'bar',
    'valor': 0,
    'activo': True
})

# Actualizar valores
planta.actualizar_sensor('TEMP-001', 'valor', 87.5)
planta.actualizar_sensor('PRES-001', 'valor', 8.2)

# Generar alarmas
planta.generar_alarma('ALM-001', 'Temperatura alta en caldera', 'ALTA')
planta.generar_alarma('ALM-002', 'Presión fuera de rango', 'MEDIA')

# Mostrar todo
planta.mostrar_configuracion()
planta.mostrar_sensores()
planta.mostrar_alarmas_activas()

🔄 Comparación de TADs

TADAccesoInserciónEliminaciónBúsquedaOrdenDuplicados
PilaSolo topeO(1) al topeO(1) del topeO(n)LIFO
ColaSolo frenteO(1) al finalO(1) del frenteO(n)FIFO
ListaPor índice O(1)O(1) al final, O(n) en medioO(n)O(n)
ConjuntoNo directoO(1) promedioO(1) promedioO(1) promedioNoNo
DiccionarioPor clave O(1)O(1) promedioO(1) promedioO(1) por claveNoClaves únicas

🎯 Ejercicios prácticos

🟢 Nivel Básico

Ejercicio 1: Validador de paréntesis

Usá una pila para verificar si los paréntesis están balanceados en una expresión.

# Ejemplo:
# "(())" → True
# "(()" → False
# "()()" → True

Ejercicio 2: Simulador de impresora

Implementá una cola para simular una cola de impresión.

# Funciones:
# - agregar_documento(nombre)
# - imprimir_siguiente()
# - ver_cola()

Ejercicio 3: Lista de compras

Creá una lista de compras con funciones para agregar, eliminar y marcar como comprado.

🟡 Nivel Medio

Ejercicio 4: Sistema de turnos

Implementá un sistema de turnos para un taller usando colas. Debe tener:

Ejercicio 5: Inventario sin duplicados

Usá un conjunto para mantener un inventario de piezas únicas.

Ejercicio 6: Caché de datos

Implementá un sistema de caché usando diccionarios que almacene los últimos valores leídos de sensores.

🔴 Nivel Avanzado

Ejercicio 7: Navegador web simplificado

Implementá un navegador con:

Ejercicio 8: Sistema de prioridades

Implementá una cola de prioridad donde las tareas urgentes se ejecutan primero.

Ejercicio 9: Gestor de eventos

Creá un sistema que:

Ejercicio 10: Simulador de almacén

Implementá un almacén automatizado con:


🏭 Proyecto integrador: Sistema SCADA simplificado

Diseñá un sistema completo que integre todos los TAD:

class SistemaSCADA:
    """
    Sistema SCADA que integra todos los TAD
    """

    def __init__(self, nombre):
        self.nombre = nombre

        # Diccionario: Configuración general
        self.config = {}

        # Lista: Sensores registrados
        self.sensores = []

        # Cola: Tareas pendientes
        self.cola_tareas = ColaEficiente()

        # Pila: Historial de comandos (para deshacer)
        self.historial_comandos = Pila()

        # Conjunto: IDs únicos de dispositivos
        self.ids_dispositivos = set()

        # Diccionario: Alarmas activas
        self.alarmas = {}

    # Implementá los métodos necesarios...

Requisitos:

  1. Registrar sensores (lista + conjunto para IDs únicos)
  2. Encolar tareas (cola FIFO)
  3. Guardar historial de comandos (pila para deshacer)
  4. Configuración en diccionario
  5. Gestión de alarmas

💡 Consejos y buenas prácticas

✅ Cuándo usar cada TAD

Usá Pila cuando:

Usá Cola cuando:

Usá Lista cuando:

Usá Conjunto cuando:

Usá Diccionario cuando:

❌ Errores comunes

  1. Usar lista cuando necesitás búsqueda rápida → Usá diccionario o conjunto
  2. Usar pop(0) en listas grandes → Usá deque para colas
  3. No validar si está vacío antes de desapilar/desencolar
  4. Usar diccionario cuando el orden importa → Usá OrderedDict o lista

🎓 Resumen

Pila (Stack): LIFO - Último en entrar, primero en salir

Cola (Queue): FIFO - Primero en entrar, primero en salir

Lista (List): Secuencia ordenada con acceso por índice

Conjunto (Set): Elementos únicos sin orden

Diccionario (Dict): Pares clave-valor para acceso rápido


🚀 Próximos pasos

  1. Implementá todos los ejercicios propuestos
  2. Intentá el proyecto integrador
  3. Investigá sobre estructuras de datos avanzadas (árboles, grafos)
  4. Aplicá estos TAD en tus proyectos de automatización

📚 Recursos adicionales


¿Tenés dudas? ¡Preguntá en clase! 🙋‍♂️

¡Ahora a dominar las estructuras de datos! 💪📊