Estructuras de datos en Python: Colas (queues)

Las colas o queues te permiten organizar los datos según el principio FIFO (primero en entrar, primero en salir). Son esenciales en la gestión de tareas y recursos.

En este artículo, aprenderás cómo implementar una cola en Python, incluyendo sus operaciones y características principales.

¿Qué es una cola o queue?

Una cola es una colección de elementos que permite añadir elementos por un extremo y retirarlos por el extremo opuesto.

Esta estructura de datos es ampliamente utilizada en la gestión de tareas, la programación de procesos, la simulación de eventos y los algoritmos.

Las características fundamentales de una cola incluyen las siguientes:

• FIFO (First In, First Out): El primer elemento que entró es el primero que sale.
• Dos extremos: Los elementos se añaden por la parte trasera (enqueue) y se retiran por la parte delantera (dequeue).
• Tamaño dinámico: La cola crece o decrece conforme añades o eliminas elementos.

Operaciones comunes en una cola

A continuación, un resumen de las operaciones que soportará tu cola:

Implementación de una cola en Python

Para implementar tu propia cola en Python, utilizarás la clase Queue que encapsula la funcionalidad descrita anteriormente con el soporte de collections.deque para almacenar los elementos de la cola.

A continuación, la implementación completa de la clase Queue:

from collections import deque
from typing import Any, Iterable, Iterator, Optional

class Queue:
    """Implement a Queue (FIFO) abstract data type."""

    def __init__(
        self,
        data: Optional[Iterable[Any]] = None,
        /
        ) -> None:
        self._data: deque = deque()
        if data is not None:
            self._data.extend(data)

    def enqueue(self, item: Any) -> None:
        """Add items to the right end of the queue."""
        self._data.append(item)

    def dequeue(self) -> Any:
        """Remove and return an item from the front of the queue."""
        try:
            return self._data.popleft()
        except IndexError:
            raise IndexError("dequeue from an empty queue") from None

    def front(self) -> Any:
        """Return the item at the beginning of the queue."""
        try:
            return self._data[0]
        except IndexError:
            raise IndexError("front from an empty queue") from None

    def remove(self, item: Any) -> None:
        """Remove the first occurrence of item."""
        try:
            self._data.remove(item)
        except ValueError:
            raise ValueError(
                f"{self.__class__.__name__}.remove(x): x not found"
            ) from None

    def is_empty(self) -> bool:
        """Return True if the queue is empty, False otherwise."""
        return len(self._data) == 0

    def __len__(self) -> int:
        return len(self._data)

    def __contains__(self, item: Any) -> bool:
        return item in self._data

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({list(self._data)})"

    __str__ = __repr__

    def __iter__(self) -> Iterator:
        yield from self._data

    def __reversed__(self) -> Iterator:
        yield from reversed(self._data)

El atributo ._data es un objeto deque que almacena los elementos de la cola. La clase deque proporciona operaciones de inserción y eliminación en tiempo constante O(1) en ambos extremos, lo que la hace apropiada para implementar colas.

Los métodos principales te permiten ofrecer las siguientes funcionalidades:

• .enqueue(): añade un elemento al final de la cola usando .append().
• .dequeue(): devuelve y elimina el elemento del frente de la cola usando .popleft() y lanza IndexError si la cola está vacía.
• .front(): devuelve el elemento del frente sin eliminarlo y lanza IndexError si la cola está vacía.
• .remove(): elimina la primera aparición de un elemento. Lanza ValueError si el elemento no existe.
• .is_empty(): comprueba si la cola está vacía.

Los métodos especiales te permiten ofrecer las siguientes funcionalidades:

• .__len__(): devuelve el número de elementos en la cola.
• .__contains__(): comprueba si un elemento está en la cola y devuelve True o False según corresponda.
• .__iter__() y .__reversed__(): permiten iterar sobre los elementos de la cola en orden normal o inverso.
• .__repr__() y .__str__(): devuelven representaciones de cadena de la cola.

Ejemplo de uso de la cola

En esta sección verás ejemplos prácticos de cómo crear y manipular instancias de tu clase Queue.

Inicialización

Para crear una Queue, puedes hacerlo sin argumentos o pasando un iterable como una lista:

>>> queue = Queue()
>>> queue
Queue([])

>>> queue = Queue([1, 2, 3])
>>> queue
Queue([1, 2, 3])

Encolar y desencolar elementos

Puedes añadir elementos al final de la cola y extraerlos del frente, siguiendo el orden FIFO:

>>> queue = Queue()
>>> queue.enqueue(1)
>>> queue.enqueue(2)
>>> queue.enqueue(3)
>>> queue
Queue([1, 2, 3])

>>> queue.dequeue()
1
>>> queue.dequeue()
2
>>> queue
Queue([3])

Si intentas extraer un elemento de una cola vacía, obtendrás un error:

>>> queue = Queue()
>>> queue.dequeue()
Traceback (most recent call last):
    ...
IndexError: dequeue from an empty queue

Consultar el frente

El método .front() te permite ver el elemento del frente sin eliminarlo:

>>> queue = Queue([1, 2, 3])
>>> queue.front()
1
>>> queue
Queue([1, 2, 3])

Eliminar un elemento específico

El método .remove() elimina la primera aparición de un elemento de la cola y lanza un ValueError si el elemento no se encuentra:

>>> queue = Queue([1, 2, 3])
>>> queue.remove(2)
>>> queue
Queue([1, 3])

>>> queue.remove(10)
Traceback (most recent call last):
    ...
ValueError: Queue.remove(x): x not found

Longitud y pertenencia

Puedes consultar la longitud de la cola con len() y verificar si un elemento está contenido en ella con el operador in:

>>> queue = Queue([10, 20, 30])

>>> len(queue)
3
>>> queue.is_empty()
False

>>> 20 in queue
True
>>> 99 in queue
False

Iteración

Los métodos .__iter__() y .__reversed__() permiten iterar sobre la cola tanto hacia adelante como hacia atrás:

>>> queue = Queue([1, 2, 3])

>>> for item in queue:
...     print(item)
...
1
2
3

>>> for item in reversed(queue):
...     print(item)
...
3
2
1

Conclusión

Has aprendido cómo implementar una cola (queue) que proporciona operaciones esenciales como añadir y eliminar elementos siguiendo el principio FIFO, consultar el primer elemento, eliminar elementos específicos y verificar si un elemento pertenece a la cola.

Este conocimiento te sirve de base para entender algoritmos que dependen de colas, como la búsqueda en anchura, la gestión de tareas en sistemas operativos y los buffers de datos.