ALGORITMOS PYTHON-páginas-21

Vista previa del material en texto

[89]
Arranquemos con el diseño del TDA cola, el cual estará compuesto básicamente de dos elementos 
que llamaremos frente y final. Estos son punteros que se encargan de apuntar a un nodoCola, que 
su vez está compuesto de dos elementos, información y siguiente –como ya hemos vista anterior-
mente–, y las funciones que describen su comportamiento, que se enumeran a continuación –op-
cionalmente puede agregarse el elemento tamaño para determinar la cantidad de elementos en la 
cola, y evitar tener que contar los nodos con una función adicional–:
1. arribo(cola, elemento). Agrega el elemento a la final de la cola;
2. atención(cola). Elimina y devuelve el elemento almacenado en el frente de la cola;
3. cola_vacia(cola). Devuelve verdadero (true) si la cola no contiene elementos;
4. en_frente (cola). Devuelve el valor del elemento que está almacenado en el frente de la cola 
sin eliminarlo;
5. tamaño(cola). Devuelve la cantidad de elementos en la cola;
6. mover_al_final(cola). Elimina el elemento en el frente de la cola y lo inserta en el final de la misma;
Para continuar, es momento de implementar el TDA cola. En primer lugar se puede observar en 
la figura 3 la definición de la estructura. Para representar TDA cola volvemos a usar una clase, que 
consta de tres atributos frente y final que son punteros que apunta al nodo que está en la frente y 
final de la cola respectivamente –dichos punteros inicialmente tienen valor None– y tamaño que 
indica la cantidad de elementos que contiene la cola cuyo valor inicial es 0. Además se utiliza la 
clase nodoCola la cual está definida por los atributos información y siguiente cuyo valor inicial es 
None en ambos casos.
Figura 3. Definición de la estructura del TDA cola
[90]
Seguimos ahora con las figuras 4 y 5 en las que se puede ver la definición de las funciones menciona-
das anteriormente, estas serán los eventos que permitirán administrar el funcionamiento de la cola.
Figura 4. Interfaz o eventos del TDA cola parte 1
Figura 5. Interfaz o eventos del TDA cola parte 2
[91]
Al momento de arribar un nuevo elemento a la cola, se crea una variable de tipo nodoCola, a la cual 
en su campo información se le asigna el elemento ingresado como dato. Si el elemento ingresado es 
el primero, al frente de la cola se le debe asignar la dirección del nodo creado, caso contrario al final 
de la cola en el campo siguiente se le asigna la dirección del nodo creado. Finalmente cualquiera 
sea el caso que haya ocurrido al nodo apuntado por final se le asigna la dirección del nodo creado y 
se incrementa el valor de tamaño.
En cambio cuando se realiza una atención de un elemento de la cola, primero se obtiene la infor-
mación del nodo que está en el frente de la cola y se lo almacena en una variable auxiliar, luego a 
frente le asignamos la dirección de referencia almacenada en el campo siguiente, del nodo que está 
en el frente de la cola. Además si el elemento eliminado es el último de la cola, a final se le debe 
asignar valor None. Por último se decrementa el valor de tamaño y se retorna el valor de la variable 
auxiliar, es decir el elemento que se quitó.
Nuevamente como en toda estructura de datos seguramente en algún momento vamos a necesitar 
hacer un barrido de sus elementos, al igual que pasó con pila en el capítulo anterior esta estructura 
no permite hacer un barrido de forma natural. Pero como ustedes ya saben, este barrido puede 
hacerse pero de manera tal que respete la naturaleza del funcionamiento de la cola utilizando una 
cola auxiliar para almacenar temporalmente los elementos y luego poder reconstruir la estructura 
original para no perder los datos. Esto se muestra en la figura 6, pero es importante remarcar que 
tanto este barrido como el de pila –dado que en esencia son iguales– son muy ineficientes ya que 
son del orden de O(n2).
Figura 6. Barrido y reconstrucción de cola
Pero además la cola tiene una gran diferencia respecto de la pila, la primera utiliza dos elementos 
para administrar la inserción y eliminación de datos mientras que la segunda solo tiene uno. Esto 
implica que en la cola se pueden realizar las operaciones para agregar o quitar datos de manera 
independiente, lo que nos permitirá mejorar la eficiencia del algoritmo de barrido. Para hacer esto 
vamos a utilizar la función mover_al_final, ya que esta estructura posee dos punteros uno para la 
inserción (frente) y otro para la eliminación (final). También vamos a necesitar la función tama-
ño para determinar cuántos elementos hay en la cola y repite dicha cantidad de veces la función 
mover_al_final, esto nos permitirá atender el elemento que está en el frente de la cola, del cual 
obtendremos la información para mostrar –o resolver otra acción– y luego hacer el arribo de dicho 
elemento al final como se puede ver en la figura 7.