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.