17.2. Colas

Todos sabemos lo que es una cola. Más aún, ¡estamos hartos de hacer colas!

El TAD cola modela precisamente ese comportamiento: el primero que llega es el primero en ser atendido, los demás se van encolando hasta que les toque su turno.

Sus operaciones son:

• __init__: inicializa una cola nueva, vacía.
• encolar: agrega un nuevo elemento al final de la cola.
• desencolar: elimina el primero de la cola y lo devuelve.
• es_vacia: devuelve True o False según si la cola está vacía o no.

17.2.1. Colas implementadas sobre listas

Al momento de realizar una implementación de una Cola, deberemos preguntarnos ¿C6mo representamos a las colas? Veamos, en primer lugar, si podemos implementar colas usando listas de Python, como hicimos con la Pila.

Definiremos una clase Cola con un atributo, items, de tipo lista, que contendrá los elementos de la cola. El primero de la cola se encontrará en la primera posición de la lista, y cada vez que encole un nuevo elemento, se lo agregará al final.

El método __init__ no recibirá parámetros adicionales, ya que deberá crear una cola vacía (que representaremos por una lista vacía):

class Cola:
    """ Representa a una cola, con operaciones de encolar y desencolar.
        El primero en ser encolado es también el primero en ser desencolado.
    """

    def __init__(self):
        """ Crea una cola vacía. """
        # La cola vacía se representa por una lista vacía
        self.items=[]

El método encolar se implementará agregando el nuevo elemento al final de la lista:

def encolar(self, x):
    """ Agrega el elemento x como último de la cola. """
    self.items.append(x)

Para implementar desencolar, se eliminará el primer elemento de la lista y se devolverá el valor del elemento eliminado, utilizaremos nuevamente el método pop, pero en este caso le pasaremos la posición 0, para que elimine el primer elemento, no el último. Si la cola está vacía se levantará una excepción.

def desencolar(self):
    """ Elimina el primer elemento de la cola y devuelve su
        valor. Si la cola está vacía, levanta ValueError. """
    try:
        return self.items.pop(0)
    except:
        raise ValueError("La cola está vacía")

Por último, el método es_vacia, que indicará si la cola está o no vacía.

def es_vacia(self):
    """ Devuelve True si la cola esta vacía, False si no."""
    return self.items == []

Veamos una ejecución de este código:

>>> from claseCola import Cola
>>> q = Cola()
>>> q.es_vacia()
True
>>> q.encolar(1)
>>> q.encolar(2)
>>> q.encolar(5)
>>> q.es_vacia()
False
>>> q.desencolar()
1
>>> q.desencolar()
2
>>> q.encolar(8)
>>> q.desencolar()
5
>>> q.desencolar()
8
>>> q.es_vacia()
True
>>> q.desencolar()
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    File "claseCola.py", line 24, in desencolar
        raise ValueError("La cola está vacía")
ValueError: La cola está vacía

¿Cuánto cuesta esta implementación? Dijimos en la sección anterior que usar listas comunes para borrar elementos al principio da muy malos resultados. Como en este caso necesitamos agregar elementos por un extremo y quitar por el otro extremo, esta implementación será una buena alternativa sólo si nuestras listas son pequeñas, ya que e medida que la cola crece, el método desencolar tardará cada vez más.

Pero si queremos hacer que tanto el encolar como el desencolar se ejecuten en tiempo constante, debemos apelar a otra implementación.

17.2.2. Colas y listas enlazadas

En la unidad anterior vimos la clase ListaEnlazada. La clase presentada ejecutaba la inserción en la primera posición en tiempo constante, pero el append se había convertido en líneal.

Sin embargo, como ejercicio, se propuso mejorar el append, agregando un nuevo atributo que apunte al último nodo, de modo de poder agregar elementos en tiempo constante.

Si esas mejoras estuvieran hechas, cambiar nuestra clase Cola para que utilice la ListaEnlazada sería tan simple como cambiar el constructor, para que en lugar de construir una lista de Python construyera una lista enlazada.

class Cola:
    """ Cola implementada sobre lista enlazada"""
    def __init__(self):
        """ Crea una cola vacía. """
        # La cola se representa por una lista enlazada vacía.
        self.items = claseListaEnlazadaConUlt.ListaEnlazada()

Sin embargo, una Cola es bastante más sencilla que una ListaEnlazadaConUlt, por lo que también podemos implementar una clase Cola utilizando las técnicas de referencias, que se vieron en las listas enlazadas.

Planteamos otra solución posible para obtener una cola que sea eficiente tanto al encolar como al desencolar, utilizando los nodos de las listas enlazadas, y solamente implementaremos insertar al final y remover al principio.

Para ello, la cola deberá tener dos atributos, self.primero y self.ultimo, que en todo momento deberán apuntar al primer y último nodo de la cola, es decir que serán los invariantes de esta cola.

En primer lugar los crearemos vacíos, ambos referenciando a None.

def __init__(self):
    """ Crea una cola vacía. """
    # En el primer momento, tanto el primero como el último son None
    self.primero = None
    self.ultimo = None

Al momento de encolar, hay dos situaciones a tener en cuenta.

Si la cola está vacía (es decir, self.ultimo es None), tanto self.primero como self.ultimo deben pasar a referenciar al nuevo nodo, ya que este nodo será a la vez el primero y el último.

Si ya había nodos en la cola, simplemente hay que agregar el nuevo a continuación del último y actualizar la referencia de self.ultimo.

El código resultante es el siguiente.

def encolar(self, x):
    """ Agrega el elemento x como último de la cola. """
    nuevo = Nodo(x)
    # Si ya hay un último, agrega el nuevo y cambia la referencia.
    if self.ultimo:
        self.ultimo.prox = nuevo
        self.ultimo = nuevo
    # Si la cola estaba vacía, el primero es también el último.
    else:
        self.primero = nuevo
        self.ultimo = nuevo

Al momento de desencolar, será necesario verificar que la cola no esté vacía, y de ser así levantar una excepción. Si la cola no está vacía, se almacena el valor del primer nodo de la cola y luego se avanza la referencia self.primero al siguiente elemento.

Nuevamente hay un caso particular a tener en cuenta y es el que sucede cuando luego de eliminar el primer nodo de la cola, la cola queda vacía. En este caso, además de actualizar la referencia de self.primero, también hay que actualizar la referencia de self.ultimo.

def desencolar(self):
    """ Elimina el primer elemento de la cola y devuelve su
        valor. Si la cola está vacía, levanta ValueError. """
    # Si hay un nodo para desencolar
    if self.primero:
        valor = self.primero.dato
        self.primero = self.primero.prox
        # Si después de avanzar no quedó nada, también hay que
        # eliminar la referencia del último.
        if not self.primero:
            self.ultimo = None
            return valor
        else:
            raise ValueError("La cola está vacía")

Finalmente, para saber si la cola está vacía, es posible verificar tanto si self.primero o self.ultimo referencian a None.

def es_vacia(self):
    """ Devuelve True si la cola esta vacía, False si no."""
    return self.items == []

Una vez implementada toda la interfaz de la cola, podemos probar el TAD resultante:

>>> from claseColaEnlazada import Cola
>>> q = Cola()
>>> q.es_vacia()
True
>>> q.encolar("Manzanas")
>>> q.encolar("Peras")
>>> q.encolar("Bananas")
>>> q.es_vacia()
False
>>> q.desencolar()
'Manzanas'
>>> q.desencolar()
'Peras'
>>> q.encolar("Guaraná")
>>> q.desencolar()
'Bananas'
>>> q.desencolar()
'Guaraná'
>>> q.desencolar()
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    File "claseColaEnlazada.py", line 42, in desencolar
        raise ValueError("La cola está vacía")
ValueError: La cola está vacía

Ejercicio 17.4. Este ejercicio surgió (y lo hicieron ya muchas generaciones de alumnos), haciendo cola:

Hace un montón de años había una viejísma sucursal del correo en la vereda impar de Av. de Mayo al 800 que tenía un cartel que decía "No se recibirán más de 5 cartas por persona". O sea que la gente entregaba sus cartas (hasta la cantidad permitida) y luego tenía que volver a hacer la cola si tenía más cartas para despachar.

Modelar una cola de correo generalizada, donde en la inicialización se indica la cantidad (no necesariamente 5) de cartas que se reciben por persona.