TIPO ABSTRACTO DE DATOS COLA

TIPO ABSTRACTO DE DATOS COLA

Las Colas son secuencias de elementos que pueden crecer y contraerse siguiendo la política : Primero en Entrar, Primero en Salir, por lo que entre los elementos de la Cola existe un orden temporal. A las colas se las suele llamar, además, Listas FIFO -First In First Out, o Listas “primero en entrar-primero en salir”.

Construiremos el TAD Cola, utilizado para resolver problemas que responden a la política mencionada. Nuevamente, las distintas aplicaciones permitirán determinar el tipo de cada elemento particular.

a) Especificación

Cola: Secuencia de cero o mas elementos de un tipo determinado que obedece a la política FIFO.

C = (a1, a2, ....., an ) , n>=0

Si la cola tiene elementos, es decir n > 0, entonces

a1 = Primer elemento

an = Ultimo elemento

Dado que esta secuencia puede crecer y contraerse, un nuevo elemento ingresa en la cola detrás de an y el elemento que mas tiempo ha permanecido en la cola, y por lo tanto el próximo a ser retirado, es a1.

Podemos suponer que C representa a una cola de clientes esperando a ser atendidos por un servidor -un cajero en un supermercado o en una entidad bancaria por ejemplo-. En este caso cada elemento ai correspondería a un cliente.

Consideramos las siguientes operaciones básicas para el TAD Cola:

- Insertar un elemento X en la cola C

Si C = (a1, a2, ....., an) , con n>=0 y X es el elemento a insertar

Entonces, luego de ejecutarse la operación:

C = (a1, a2, ....., an , X)

- Suprimir un elemento de la cola C

Si C =(a1, a2, ....., an) , con n>0

Entonces, luego de ejecutarse la operación:

C = (a2, ....., an) y X = a1

- Recorrer la cola C.

Retomamos en este caso, las consideraciones realizadas respecto a la operación recorrer cuando presentamos el TAD Pila.

Sean C una Cola y X un elemento:

NOMBRE ENCABEZADO FUNCION ENTRADA SALIDA

Insertar Insertar (C,X) Ingresa el elemento X en la cola C C y X C=(a1,a2,...,an,X)

Suprimir Suprimir(C,X) Si C no está vacía, elimina el elemento que mas tiempo ha permanecido en la cola C si n>0: C=(a2,..., an-1) y X=a1; Error en caso contrario

Recorrer Recorrer(C) Procesa todos los elementos de C siguiendo la política FIFO C Está sujeta al proceso que se realice sobre los elementos de C

Crear Crear(C) Inicializa C C C=( )

Vacía Vacía(C) Evalúa si C tiene elementos C Verdadero si C No tiene elementos, Falso en caso contrario.

Simulación

Una de las áreas en las que se aplica el TAD Cola es la Simulación, que consiste en la imitación de un proceso del mundo-real, a lo largo del tiempo.

La simulación constituye una técnica económica que nos permite, además de ofrecer varios escenarios posibles de una situación, equivocarnos sin provocar efectos sobre el mundo real (por ejemplo un simulador de vuelo o de conducción de automóviles).

Los programas de simulación reproducen el sistema físico real, por medio de variables que representan el estado de ese sistema, para analizar, predecir, o mejorar su comportamiento.

En un sistema de simulación discreto, las variables de estado cambian solo en puntos discretos o contables en el tiempo, mientras que en un sistema de simulación continuo esas variables cambian en forma continua a través del tiempo.

Ejemplos típicos de simulación discreta corresponden a sistemas de colas : colas de clientes que realizan el pago de servicios por medio de un cajero (automático o no), colas de vehículos que esperan en una estación de servicio, colas de aviones que esperan en un aeropuerto la orden para despegar, líneas de montaje dentro de una fábrica automotriz. Diversos Sistemas Operativos suelen mantener colas para regular el orden en el cual las tareas reciben procesamiento o les son asignados diferentes recursos del sistema. En general estamos hablando de un sistema de colas de espera asociadas a un servidor. En los sistemas mencionados los servidores son: el cajero, la bomba de combustible, la pista del aeropuerto, el procesador y los recursos del sistema (impresora por ejemplo).

La simulación permitirá obtener ciertos datos del comportamiento del sistema, que apoyarán cualquier instancia de toma de decisiones. En los ejemplos planteados es de interés conocer por ejemplo cual es la longitud máxima de la cola o el tiempo de espera promedio de los clientes antes de ser atendidos. Estos datos servirán al momento de establecer si el número de cajeros o de bombas de expendio de combustible es adecuado, si el espacio físico asignado es apropiado para el tamaño máximo que puede alcanzar la cola, si los recursos del sistema son suficientes, etc.

La simulación de colas involucra además de la generación de los eventos artificiales que cambian el estado del sistema, la recolección de observaciones. Por ejemplo si estamos interesados solo en conocer la longitud de una cola de espera, esta medida solo cambia cuando un cliente entra o sale del sistema; en todos los demás momentos, no ocurre nada en el sistema desde el punto de vista de la inferencia estadística. Los dos eventos principales que podemos considerar en un sistema de colas son: llegada de un cliente y realización del servicio.

La principal dificultad que surge al implementar una simulación informática consiste en salvar la distancia que existe entre el sistema físico y su implementación informática. Por ello, además de traducir lo que ocurre en el mundo real en un algoritmo, debemos establecer qué estructuras de datos es conveniente utilizar para representar a los componentes del sistema físico.

Ahora proponemos una aplicación del TAD Cola en un problema de simulación:

• Realizar la simulación informática correspondiente al comportamiento de una cola de clientes que esperan efectuar una transacción en un cajero automático. El objetivo de esta simulación es conocer el tiempo promedio de espera de los clientes en la cola.

La información obtenida servirá para realizar ajustes en el sistema que se modela; por ejemplo ayudará a decidir la adquisición de nuevos cajeros automáticos si el tiempo de espera de los clientes, calculado en la simulación, no es adecuado.

Para la ejecución de la simulación, realizamos un análisis previo del comportamiento del sistema real que se encuentra en funcionamiento y que se desea mejorar.

Los eventos principales que vamos a considerar tienen que ver con la realización

...