diferencias

 UNIDAD: COLAS.

Objetivos:
Implementar la estructura de datos no lineal cola
Conocer las aplicaciones de las colas en el ambiente informático.
Implementar estructuras de datos que simulen el comportamiento de una cola, haciendo uso de la definición correspondiente.
Utilizar los algoritmos correspondientes para implementar las operaciones fundamentales con colas.


Contenidos:

1.Introducción
2. Definición
3. Ejemplificación
4. Representación de una cola
5. Operaciones con colas
6. Algoritmos de insertar y eliminar
7. Colas circulares
8. Ejercicio


1. Introducción

Las colas ("Queues") son sucesiones de registros contiguos dispuestos de forma que es fácil añadir un nuevo elemento (que se coloca después del último) y/o acceder o eliminar el primero.  Es decir,la forma en que están construidas las hace parecerse a una tubería, el primer agua que entra es la primera que sale.  Esta forma de acceder a la información se denomina FIFO ("First In First Out") primero en entrar primero en salir.
Estas entidades corresponden a lo que en matemáticas se conoce como líneas de espera, y su estudio teórico, conocido como teoría de colas, es muy importante entransporte y telecomunicación (una modalidad de transporte).  A título de curiosidad podemos citar que incluso existe un lenguaje de programación denominado Oroogu, cuyo único tipo de datos es una cola.

Sus características básicas pueden sintetizarse cuatro palabras:  datos contiguos, ordenación FIFO.



2. Definición

Una cola es una lista de elementos en la que éstos se introducen por unextremo y se eliminan por otro. Los elementos se eliminan en el mismo orden en el que se insertaron. Por lo tanto el primer elemento que entra a la cola será el primero en salir. Debido a esta característica, las colas también reciben el nombre de estructuras FIFO ( First – In, First – Out : primero en entrar, primero en salir ).

3. Ejemplificación

Existen numerosos casos de colas en la vidareal: las personas esperando para usar un teléfono público ( la primera persona de la cola será la primeras que use el teléfono ), las personas que esperan para ser atendidas en la caja de un banco ( la primera persona de la cola será la primera en ser atendida ); podríamos seguir nombrando otros casos como los autos que esperan el cambio de luz de un semáforo en rojo, o los niños que esperanpara subir a un juego mecánico. El servicio de atención al cliente en un almacén es un ejemplo típico de cola. La acción de gestión de memoria intermedia (buffering) de trabajos o tareas de impresora en un distribuidor de impresoras (spooler) es otro ejemplo típico de cola. Dado que la impresión es una tarea ( un trabajo ) que requiere más tiempo que el proceso de la transmisión real de los datosdesde la computadora a la impresora, se organiza una cola de trabajos de modo que los trabajos se imprimen en el mismo orden en que se recibieron por la impresora. Este sistema tiene el gran inconveniente de que si su trabajo personal consta de una única página para imprimir y delante de su petición de impresión existe otra petición para imprimir un informe de 300 páginas, deberá esperar a laimpresión de esas 300 páginas antes de que se imprima su página.

Desde el punto de vista de estructura de datos, una cola es similar a una pila, en donde los datos se almacenan de un modo lineal y el acceso a los datos sólo está permitido en los extremos de la cola.


4. Representación de colas.

Al igual que las pilas, las colas no existen como estructuras de datos estándares en loslenguajes de programación. Las colas pueden representarse mediante el uso de :

Arreglos
Listas enlazadas


Como en el caso de las pilas, utilizaremos arreglos para implementar colas. Para esto debe definirse un tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que guarde la posición del primer elemento de la cola ( FRENTE ) y la otra para que guarde la posición del...