Implementación de colas en Python

Una cola almacena elementos en orden de primero en entrar, primero en salir (FIFO): cada elemento nuevo se añade al final y se elimina el que está al frente. Python ofrece varias formas de representar este comportamiento. En esta guía se implementa una cola con una lista y una lista enlazada, y después se muestra la opción de la biblioteca estándar collections.deque.

Comportamiento de las colas y operaciones básicas

El frente es el extremo del que saldrá el próximo elemento; el final es donde se incorpora el siguiente. Por ejemplo, si una cola contiene 1, 2, 3, 1 está al frente y 3 al final. Al añadir 4, queda 1, 2, 3, 4; una extracción devuelve 1 y deja 2, 3, 4.

A continuación se muestra una secuencia ejecutable breve que añade elementos al final y los elimina desde el frente. El paquete suministrado no incluye una observación de ejecución para este fragmento, así que no se afirma ningún resultado.

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

queue = []
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
removed = queue.pop(0)
print(removed)
print(queue)

Una interfaz de cola útil ofrece cuatro operaciones: encolar añade un elemento, desencolar elimina y devuelve el elemento del frente, una comprobación indica si queda algún elemento y la longitud informa cuántos elementos hay. Las implementaciones siguientes devuelven (False, None) si se intenta desencolar una cola vacía y (True, item) cuando la operación tiene éxito. La marca de éxito permite distinguir un elemento None real de una cola vacía.

Implementar una cola con una lista de Python

Una lista ofrece un ejemplo didáctico compacto. Añade elementos al final y elimina el primero con pop(0). El código es sencillo, pero al quitar el elemento del frente se desplazan los restantes, por lo que el coste de desencolar crece de forma lineal a medida que aumenta la cola. El ejemplo admite cualquier objeto de Python, incluido None.

Ejecuta este ejemplo. Las cadenas y las etiquetas visibles dentro del código se mantienen en inglés.

class ListQueue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.pop(0)

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

    def __len__(self):
        return len(self.items)


queue = ListQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

Una lista con un índice de inicio puede evitar los desplazamientos en cada eliminación, pero conserva las entradas eliminadas hasta que se compacta la lista. Este enfoque requiere llevar un control adicional para relacionar las posiciones lógicas de la cola con los índices de la lista y para reiniciar o compactar el almacenamiento de forma segura. Para un uso general de FIFO, collections.deque suele ser más clara.

Implementar una cola con una lista enlazada

Una cola simplemente enlazada almacena cada elemento en un nodo cuya referencia next apunta hacia el final de la cola. Mantén referencias a ambos extremos: al encolar, enlaza un nodo nuevo después de rear; al desencolar, avanza front. Cuando sale el último nodo, también hay que asignar None a rear; de lo contrario, el siguiente encolado podría intentar añadir un nodo mediante una referencia obsoleta. En esta implementación, encolar y desencolar tienen coste constante, mientras que obtener la longitud tiene coste lineal porque se cuentan los nodos.

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class LinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, item):
        node = Node(item)
        if self.rear is None:
            self.front = self.rear = node
        else:
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        if self.front is None:
            return False, None
        item = self.front.value
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return True, item

    def is_empty(self):
        return self.front is None

    def __len__(self):
        count = 0
        current = self.front
        while current is not None:
            count += 1
            current = current.next
        return count


queue = LinkedQueue()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

El invariante es que ambas referencias son None exactamente cuando la cola está vacía. Si no está vacía, front identifica el siguiente elemento que se eliminará y rear.next es None. Mantener este invariante permite gestionar tanto una cola con un solo elemento como su reutilización después de quedar vacía.

Usar collections.deque para una cola

Para el uso habitual de FIFO, collections.deque de Python es la opción práctica por defecto. Añade elementos por la derecha y elimina desde la izquierda con popleft(). Ambas operaciones en los extremos están diseñadas para ser eficientes; len() y una comprobación de verdad permiten expresar el resto de la interfaz de forma concisa. Si se llama a popleft() en un deque vacío, se produce IndexError, así que este envoltorio comprueba primero si está vacío y devuelve la misma marca de éxito que los demás ejemplos. Las cadenas y las etiquetas visibles dentro del código se mantienen en inglés.

from collections import deque


class DequeQueue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.items:
            return False, None
        return True, self.items.popleft()

    def is_empty(self):
        return not self.items

    def __len__(self):
        return len(self.items)


queue = DequeQueue()
queue.enqueue("first")
queue.enqueue("second")
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())
print(queue.is_empty(), len(queue))
print(queue.dequeue())

deque es una clase del módulo collections. Aquí importa su interfaz pública; evita basarte en suposiciones sobre la representación interna. Si necesitas capacidad limitada o coordinación entre hilos productores y consumidores, considera las clases del módulo queue de Python, diseñadas específicamente para esos casos.

Comparar las implementaciones

Los costes de la lista enlazada suponen que la cola guarda tanto front como rear; calcular su longitud sigue requiriendo recorrer cada nodo, ya que no se mantiene un contador. Un contador independiente permitiría obtener la longitud en tiempo constante, a cambio de tener que actualizar otro invariante en cada operación. Para la mayoría de los programas, elige collections.deque. Usa una lista si la cola es pequeña o si no se repiten las eliminaciones desde el frente; elige una lista enlazada para aprender cómo funciona la estructura o cuando resulte útil trabajar específicamente con su comportamiento a nivel de nodo.