Listas Deque en Python: Colas de Doble Extremo Eficientes ↔️

Descubre las `deque`, una estructura de datos optimizada para añadir y quitar elementos rápidamente por ambos extremos.

1. ¿Qué es una `deque` y por qué usarla?

En Python, además de las listas estándar [], existe una estructura de datos especializada muy útil llamada deque (pronunciada como "deck", la abreviatura de "double-ended queue" o "cola de doble extremo"). Las deques están disponibles en el módulo incorporado collections.

Una deque es una secuencia similar a una lista, pero con una gran ventaja: está altamente optimizada para realizar operaciones de añadir (append) y quitar (pop) elementos desde ambos extremos (izquierda y derecha) de manera muy rápida y eficiente.

Principales Ventajas de deque sobre las Listas Estándar:

• Eficiencia en los Extremos: Mientras que en una lista normal, operaciones como lista.insert(0, valor) (añadir al principio) o lista.pop(0) (quitar del principio) son lentas (complejidad $O(N)$, donde N es el tamaño de la lista, porque todos los demás elementos deben desplazarse), en una deque, las operaciones equivalentes (appendleft(), popleft()) son muy rápidas (complejidad $O(1)$, tiempo constante).
• Implementación de Pilas y Colas: Son perfectas para implementar eficientemente estructuras de datos como pilas (LIFO - Last In, First Out) usando append() y pop(), y colas (FIFO - First In, First Out) usando append() y popleft().
• Historial Limitado: Se pueden crear deques con una longitud máxima fija. Si se añaden elementos a una deque llena, los elementos del extremo opuesto se descartan automáticamente, lo cual es ideal para mantener un historial de los últimos N ítems.

Para usar una deque, primero debes importarla desde el módulo collections.

from collections import deque

# Crear una deque vacía
cola_de_tareas = deque()

# Crear una deque a partir de una lista existente
datos_sensor_iniciales = [10.1, 10.3, 10.2]
buffer_sensor = deque(datos_sensor_iniciales)
print(f"Deque inicial: {buffer_sensor}")

# Crear una deque con una longitud máxima (maxlen)
# Útil para historiales o buffers circulares
ultimas_lecturas = deque(maxlen=5) 
print(f"Deque con longitud máxima (vacía): {ultimas_lecturas}")

2. Métodos Principales de las Deques

Las deques comparten muchos métodos con las listas, pero tienen algunos específicos para operaciones eficientes en ambos extremos.

📋 Tabla Resumen de Métodos Clave de deque:

Exploremos algunos de estos métodos con ejemplos:

from collections import deque
# Simulación de llegada de tareas a un procesador
tareas_pendientes = deque(["TareaC"])
tareas_pendientes.append("TareaD")     # Añade al final (derecha)
tareas_pendientes.appendleft("TareaB") # Añade al inicio (izquierda)
tareas_pendientes.appendleft("TareaA")
print(f"Cola de tareas: {tareas_pendientes}")
# Salida: deque(['TareaA', 'TareaB', 'TareaC', 'TareaD'])

# Procesando la cola de tareas (FIFO - First In, First Out)
primera_tarea = tareas_pendientes.popleft()
print(f"Procesando: {primera_tarea}") # Sale 'TareaA'
print(f"Tareas restantes: {tareas_pendientes}")

# Si fuera una pila (LIFO - Last In, First Out)
# ultima_tarea_anadida = tareas_pendientes.pop() 
# print(f"Procesando (LIFO): {ultima_tarea_anadida}")

# Física: Simular un cifrado César o un carrusel
secuencia_original = deque(['A', 'B', 'C', 'D', 'E'])
secuencia_original.rotate(2)  # Rota 2 posiciones a la derecha
print(f"Rotada +2: {secuencia_original}") 
# Salida: deque(['D', 'E', 'A', 'B', 'C'])

secuencia_original.rotate(-1) # Rota 1 posición a la izquierda
print(f"Rotada -1: {secuencia_original}")
# Salida: deque(['E', 'A', 'B', 'C', 'D'])

# Biología: Últimas N mediciones de pH en un cultivo celular
ultimos_ph = deque(maxlen=3)
ultimos_ph.append(7.4)
ultimos_ph.append(7.3)
ultimos_ph.append(7.5)
print(f"Últimos pH: {ultimos_ph}") # deque([7.4, 7.3, 7.5], maxlen=3)

ultimos_ph.append(7.2) # Añade 7.2, y 7.4 (el más antiguo) se va
print(f"Después de añadir 7.2: {ultimos_ph}") 
# Salida: deque([7.3, 7.5, 7.2], maxlen=3)

3. Aplicaciones Prácticas de las Deques

La eficiencia de las deques en operaciones de extremo las hace ideales para varios escenarios:

# Matemáticas: Evaluar expresiones con paréntesis
pila_operaciones = deque()
pila_operaciones.append("Operación1") # Push
pila_operaciones.append("Operación2") # Push
print(f"Pila: {pila_operaciones}")
elemento_sacado = pila_operaciones.pop() # Pop "Operación2"
print(f"Sacado: {elemento_sacado}, Pila ahora: {pila_operaciones}")

# Simulación de cola de impresión (Informática)
cola_impresion = deque()
cola_impresion.append("DocumentoA.pdf")
cola_impresion.append("ImagenB.jpg")
print(f"Cola: {cola_impresion}")
trabajo_actual = cola_impresion.popleft() # Sale "DocumentoA.pdf"
print(f"Imprimiendo: {trabajo_actual}, Cola ahora: {cola_impresion}")

# Editor de texto simple
historial_acciones = deque(maxlen=5)
def realizar_accion(accion):
    historial_acciones.append(accion)
    print(f"Acción: {accion}, Historial: {list(historial_acciones)}")

realizar_accion("Escribir 'Hola'")
realizar_accion("Cambiar fuente")
realizar_accion("Guardar")
realizar_accion("Insertar imagen")
realizar_accion("Añadir tabla")
realizar_accion("Borrar párrafo") # "Escribir 'Hola'" se descarta

# Ejemplo conceptual de BFS
# grafo = { 'A': ['B', 'C'], 'B': ['D'], ... }
# por_visitar = deque(['NodoInicial'])
# while por_visitar:
#     nodo_actual = por_visitar.popleft()
#     # procesar nodo_actual
#     # añadir vecinos no visitados a por_visitar.append()
print("BFS usa deque para la cola de nodos por visitar.")

# Simulación de datos de un sensor de temperatura
datos_ventana = deque(maxlen=4)
nuevas_mediciones = [20.1, 20.3, 20.5, 20.4, 20.6, 20.7]
for medicion in nuevas_mediciones:
    datos_ventana.append(medicion)
    if len(datos_ventana) == datos_ventana.maxlen:
        promedio_ventana = sum(datos_ventana) / len(datos_ventana)
        print(f"Ventana: {list(datos_ventana)}, Promedio: {promedio_ventana:.2f}°C")

Conclusión: Deques para Eficiencia en los Extremos

Has aprendido sobre las deques del módulo collections, una alternativa especializada y eficiente a las listas de Python cuando necesitas realizar operaciones frecuentes en ambos extremos de una secuencia.

Recuerda sus puntos fuertes:

• Operaciones appendleft() y popleft() con rendimiento $O(1)$.
• Excelentes para implementar pilas (LIFO) y colas (FIFO).
• Capacidad de tener una longitud máxima (maxlen) para historiales o buffers.
• Métodos útiles como rotate() para manipulación de secuencias.

Si bien las listas son la estructura de secuencia de propósito general en Python, conocer y saber cuándo usar una deque puede optimizar significativamente tus algoritmos y estructuras de datos.