3.12. Implementación de una cola en Python

Es de nuevo apropiado crear una nueva clase para la implementación del tipo abstracto de datos Cola. Como antes, vamos a utilizar la potencia y la simplicidad de las listas para construir la representación interna de la cola.

Tenemos que decidir qué extremo de la lista utilizar como el final y cuál utilizar como el frente. La implementación mostrada en el Programa 1 supone que el final está en la posición 0 en la lista. Esto nos permite usar la función insert en las listas para agregar nuevos elementos al final de la cola. La operación pop puede utilizarse para eliminar el elemento del frente (el último elemento de la lista). Recuerde que esto también significa que agregar será O(n) y avanzar será O(1).

Programa 1

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

    def estaVacia(self):
        return self.items == []

    def agregar(self, item):
        self.items.insert(0,item)

    def avanzar(self):
        return self.items.pop()

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

El CodeLens 1 muestra la clase Cola en acción a medida que realizamos la secuencia de operaciones de la Tabla 1.

Activity: CodeLens Ejemplo de operaciones de Cola (ququeuetest)

Una manipulación adicional de esta cola daría los siguientes resultados:

>>> c.tamano()
3
>>> c.estaVacia()
False
>>> c.agregar(8.4)
>>> c.avanzar()
4
>>> c.avanzar()
'perro'
>>> c.tamano()
2

Autoevaluación

You have attempted of activities on this page