Deque (Double-Ended Queue)

 Deque (Double-Ended Queue) es una estructura de datos de la biblioteca collections que permite agregar y eliminar elementos por ambos extremos de manera eficiente.

python
from collections import deque

¿Por qué usar deque en lugar de una lista?

  • Listas: eficientes para operaciones al final, pero lentas al principio

  • Deque: eficiente en ambos extremos (O(1) para agregar/eliminar)

Creación de un deque

python
# Diferentes formas de crear un deque
d1 = deque()                    # deque vacío
d2 = deque([1, 2, 3, 4])       # desde una lista
d3 = deque("hola")             # desde un string → deque(['h', 'o', 'l', 'a'])
d4 = deque(range(5))           # desde un range

Operaciones principales

Agregar elementos

python
d = deque([1, 2, 3])

# Agregar al final (derecha)
d.append(4)           # deque([1, 2, 3, 4])
d.extend([5, 6])      # deque([1, 2, 3, 4, 5, 6])

# Agregar al principio (izquierda)
d.appendleft(0)       # deque([0, 1, 2, 3, 4, 5, 6])
d.extendleft([-2, -1]) # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

Eliminar elementos

python
d = deque([1, 2, 3, 4, 5])

# Eliminar del final
ultimo = d.pop()      # elimina 5, d = deque([1, 2, 3, 4])

# Eliminar del principio
primero = d.popleft() # elimina 1, d = deque([2, 3, 4])

# Eliminar todos los elementos
d.clear()             # deque vacío

Otras operaciones útiles

python
d = deque([1, 2, 3, 4, 5])

# Rotación
d.rotate(1)           # deque([5, 1, 2, 3, 4]) - rota a la derecha
d.rotate(-1)          # deque([1, 2, 3, 4, 5]) - rota a la izquierda

# Acceso por índice
print(d[0])           # 1 - primer elemento
print(d[-1])          # 5 - último elemento

# Longitud
print(len(d))         # 5

# Búsqueda
print(3 in d)         # True

Ejemplos prácticos

1. Cola (Queue) FIFO

python
from collections import deque

cola = deque()

# Encolar
cola.append("cliente1")
cola.append("cliente2")
cola.append("cliente3")

# Desencolar
while cola:
    siguiente = cola.popleft()
    print(f"Atendiendo: {siguiente}")
# Output: Atendiendo: cliente1, cliente2, cliente3

2. Pila (Stack) LIFO

python
pila = deque()

# Apilar
pila.append("tarea1")
pila.append("tarea2")
pila.append("tarea3")

# Desapilar
while pila:
    tarea = pila.pop()
    print(f"Procesando: {tarea}")
# Output: Procesando: tarea3, tarea2, tarea1

3. Ventana deslizante

python
def ventana_deslizante(lista, k):
    """Encuentra el máximo en cada ventana de tamaño k"""
    dq = deque()
    resultado = []
    
    for i, num in enumerate(lista):
        # Eliminar elementos fuera de la ventana
        if dq and dq[0] == i - k:
            dq.popleft()
        
        # Mantener deque decreciente
        while dq and lista[dq[-1]] <= num:
            dq.pop()
        
        dq.append(i)
        
        # Agregar máximo a resultado
        if i >= k - 1:
            resultado.append(lista[dq[0]])
    
    return resultado

print(ventana_deslizante([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [3, 3, 5, 5, 6, 7]

Ventajas del deque

  • Eficiencia: O(1) para operaciones en ambos extremos

  • Flexibilidad: Puede usarse como cola, pila o deque

  • Optimizado: Implementado en C para mejor rendimiento

  • Thread-safe: Operaciones atómicas para programación concurrente

Cuándo usar deque vs list

Usa deque cuando:

  • Necesitas operaciones frecuentes en ambos extremos

  • Implementas colas o pilas

  • Trabajas con ventanas deslizantes

Usa list cuando:

  • Necesitas acceso aleatorio frecuente

  • Realizas muchas operaciones de slicing

  • El código ya usa listas y no hay problemas de rendimiento

Comentarios

Publicar un comentario

Entradas populares de este blog

¿Qué es un Closure?

CÓDIGO SIMPLIFICADO python def contador_llamadas ( funcion_original ) : contador = 0 def funcion_envoltura ( ) : nonlocal contador contador += 1 print ( f"Llamada número: { contador } " ) return funcion_original ( ) # ← Ejecuta saludar() return funcion_envoltura # Definimos UNA sola función-funcion_original ) def saludar ( ) : return "¡Hola!" # Aplicamos el contador saludar_contador = contador_llamadas ( saludar ) # Usamos la función print ( saludar_contador ( ) ) # Llamada 1 print ( saludar_contador ( ) ) # Llamada 2 print ( saludar_contador ( ) ) # Llamada 3 🎯   SALIDA: text Llamada número: 1 ¡Hola! Llamada número: 2 ¡Hola! Llamada número: 3 ¡Hola! LA CLAVE ESTÁ EN ESTA LÍNEA: python return funcion_envoltura # ← ¡NO lleva paréntesis! 🔍  ¿QUÉ PASA PASO A PASO? PASO 1:  Cuando haces: python saludar_contador = contador_llamadas ( saludar ) contador_llamadas  crea  c...
Leer más

4 tipos de colecciones de datos más

  Te explico los 4 tipos de colecciones de datos más comunes en programación: 📋 Listas (Arrays)["",""] Características: Ordenadas  - Mantienen el orden de inserción Mutables  - Se pueden modificar después de crearlas Permiten duplicados  - Pueden tener elementos repetidos Indexadas  - Se accede por posición numérica (0, 1, 2...) Ejemplo (Python): python frutas = [ "manzana" , "banana" , "cereza" ] frutas . append ( "naranja" ) # Agregar elemento print ( frutas [ 1 ] ) # Output: "banana" 🔄 Conjuntos (Sets){} Características: No ordenados  - No mantienen un orden específico No permiten duplicados  - Elementos únicos Mutables  - Se pueden agregar/eliminar elementos No indexados  - No se puede acceder por posición Ejemplo (Python): python colores = { "rojo" , "verde" , "azul" } colores . add ( "amarillo" ) print ( "rojo" in colores ) # Output: True 📖 ...
Leer más

Funciones en Python: con y sin paréntesis

  Funciones en Python: con y sin paréntesis Te explico la diferencia fundamental entre usar funciones con y sin paréntesis en Python: 1. Función CON paréntesis:  Ejecución Cuando usas paréntesis después del nombre de una función,  estás ejecutando o llamando  esa función: python def saludar ( ) : return "¡Hola!" # Con paréntesis - EJECUTA la función mensaje = saludar ( ) print ( mensaje ) # Output: ¡Hola! 2. Función SIN paréntesis:  Referencia Cuando usas el nombre sin paréntesis,  estás haciendo referencia  a la función como objeto: python def saludar ( ) : return "¡Hola!" # Sin paréntesis - REFERENCIA a la función mi_funcion = saludar print ( mi_funcion ) # Output: <function saludar at 0x...> # Ahora puedes ejecutarla usando la referencia print ( mi_funcion ( ) ) # Output: ¡Hola! Ejemplos prácticos Ejemplo 1: Funciones como objetos de primera clase python def sumar ( a , b ) : return a + b def multipli...
Leer más