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)
Before you keep reading...
Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.
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
- 'hola', 'perro'
- Recuerde que lo primero que se agrega a la cola es lo primero que se elimina. FIFO
- 'perro', 3
- Sí, first-in-first-out significa que hola se ha eliminado
- 'hola', 3
- Colas y pilas son estructuras de datos en las que sólo se puede acceder al primero y al último ítem.
- 'hola', 'perro', 3
- Tal vez usted pasó por alto el llamado a avanzar al final
Q-2: 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?