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.

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

    Q-6: Suponga que usted tiene la siguiente serie de operaciones para colas.

    c = Cola()
    c.agregar('hola')
    c.agregar('perro')
    c.agregar(3)
    c.avanzar()
    

    ¿Qué ítems quedan en la cola?

  • (A) 'hola', 'perro'
  • Recuerde que lo primero que se agrega a la cola es lo primero que se elimina. FIFO
  • (B) 'perro', 3
  • Sí, first-in-first-out significa que hola se ha eliminado
  • (C) 'hola', 3
  • Colas y pilas son estructuras de datos en las que sólo se puede acceder al primero y al último ítem.
  • (D) 'hola', 'perro', 3
  • Tal vez usted pasó por alto el llamado a avanzar al final
Next Section - 3.13. Simulación: la patata caliente