19.2. Cola Enlazada

La primera implementación del TAD Cola al que vamos a echar un vistazo se llama cola enlazada porque esta hecha de objetos Nodo enlazados. He aquí

 

la definición de la clase:

   1: class Cola:
   2:     def __init__(self):
   3:         self.longitud = 0
   4:         self.cabeza = None
   5:     def estaVacia(self):
   6:         return (self.longitud == 0)
   7:     def inserta(self, carga):
   8:         nodo = Nodo(carga)
   9:         nodo.siguiente = None
  10:         if self.cabeza == None:
  11:             # si la lista esta vac³a el nuevo nodo va el primero
  12:             self.cabeza = nodo
  13:         else:
  14:             # encuentra el ultimo nodo de la lista
  15:             ultimo = self.cabeza
  16:         
  17:         while ultimo.siguiente: ultimo = ultimo.siguiente
  18:             # añadir el nuevo nodo
  19:             ultimo.siguiente = nodo
  20:             self.longitud = self.longitud + 1
  21:     def quita(self):
  22:         carga = self.cabeza.carga
  23:         self.cabeza = self.cabeza.siguiente
  24:         self.longitud = self.longitud - 1
  25:         return carga

 

Los métodos estaVacia y quita son idénticos a los métodos estaVacia y a quitaPrimero de ListaEnlazada. El metodo inserta es nuevo y un poco mas complicado.


Queremos insertar nuevos elementos al final de la lista. Si la cola esta vacía, simplemente hacemos que cabeza se refiera al nuevo nodo.


En caso contrario, recorremos la lista hasta el ultimo nodo y lo fijamos al final.


Podemos reconocer el ultimo nodo porque su atributo siguiente es None.


En un objeto Cola correctamente construido hay dos invariantes. El valor de longitud debería ser el numero de nodos en la cola, y el ultimo nodo debería tener siguiente igual a None. Crease que este metodo cumple con ambas invariantes.

0