ROCÍO PRIETO GONZÁLEZ2º MATEMÁTICAS

ÍNDICE

......................................................................................................1ROCÍO PRIETO GONZÁLEZ.......................................................................................1

ÍNDICE...................................................................................................................................2INTRODUCCIÓN .................................................................................................................3ESTRUCTURA DE DATOS..................................................................................................3INSERCIÓN DE DATOS.......................................................................................................3ELIMINACIÓN DE ELEMENTOS.......................................................................................3ACCESO A ELEMENTOS....................................................................................................3Listas enlazadas.......................................................................................................................3En cualquier posición de la estructura....................................................................................3En cualquier posición de la estructura...................................................................................3Todos los elementos son accesibles........................................................................................3Pilas.........................................................................................................................................3Por el extremo Cima...............................................................................................................3Por el extremo Cima...............................................................................................................3Solo se accede al elemento que ocupe el extremo Cima.........................................................3Colas........................................................................................................................................3Por el extremo Final................................................................................................................3Por el extremo Frente..............................................................................................................3Solo se accede al elemento que ocupe el extremo Frente.......................................................3DEFINICIÓN DEL TDA COLA............................................................................................4APLICACIONES DE LAS COLAS.......................................................................................4OPERACIONES CON EL TDA COLA.................................................................................5IMPLEMENTACIÓN CON VECTORES (Estructura circular):...........................................6IMPLEMENTACIÓN CON LISTAS ENLAZADAS............................................................9DEFINICIÓN DE BICOLAS...............................................................................................10DEFINICIÓN DE COLAS DE PRIORIDADES..................................................................11BIBLIOGRAFÍA..................................................................................................................12

2

INTRODUCCIÓN

Las colas, al igual que las pilas son un tipo especial de listas. Se puede formular una primera definición del TDA cola como estructura de datos lineales que, al igual que las pilas, van a presentar restricciones en cuanto a la posición por la cual pueden realizarse la inserción y eliminación de elementos.

En el siguiente cuadro podemos ver sus diferencias:

ESTRUCTURA DE DATOS

INSERCIÓN DE DATOS

ELIMINACIÓN DE ELEMENTOS

ACCESO A ELEMENTOS

Listas enlazadas En cualquier posición de la estructura

En cualquier posición de la estructura

Todos los elementos son accesibles

Pilas Por el extremo Cima Por el extremo Cima Solo se accede al elemento que ocupe el extremo Cima

Colas Por el extremo Final Por el extremo Frente Solo se accede al elemento que ocupe el extremo Frente

3

DEFINICIÓN DEL TDA COLA

Para definir la estructura de datos cola se va a recurrir a la imagen que se tiene de una cola de espera. Supóngase una cola de personas que están esperando frente a la taquilla del cine. Toda persona que pretenda una entrada se irá incorporando a la cola por el final de la misma, y no saldrá de ella hasta que haya obtenido su entrada, qué será cuando se encuentre al principio de la cola.

Se ve, por tanto, que cualquier elemento, en este caso personas, que quieran formar parte de la cola lo harán por el final, mientras que para abandonar la estructura de datos es necesario que alcance el principio.

El TDA COLA es una secuencia de elementos, e1,e2,e3,...,eN con n mayor o igual que 0, en la que la adicción de nuevos elementos se realiza por un extremo que se denota por final y las extracciones de elementos ya existentes, se realiza por el otro extremo al que llamaremos frente. Hay que tener en cuenta que si N = 0, se dice que la cola está vacía.

Esta definición de cola implica que el primer elemento que sea extraído para su procesamiento será el primero que se haya introducido en la estructura, esta característica hace que se la conozca también como:

- listas “FIFO”, que se corresponde con las iniciales de First In, First Out ( o listas “primero en entrar, primero en salir”)

Para procesar los elementos que se encuentran en una cola, es necesario que dicho elemento sea accesible, por lo que deberá de ocupar la posición que haga referencia al extremo frente.

Frente Final

Es decir, los elementos e1, e2, e3 se han ido insertando por el extremo final y en este instante el único elemento accesible es el e1. Para acceder al resto de elementos de la cola será necesario que tanto e2, como e3, ocupen la posición frente. El elemento e2 pasará a estar al principio de la cola cuando e1 haya sido eliminado. De igual forma para que e3 sea accesible se deberá de eliminar e2 y así sucesivamente.

APLICACIONES DE LAS COLAS

Hay varios algoritmos que se valen de colas para dar tiempos de ejecución eficientes, por ejemplo en la teoría de grafos. Las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de Entrada / Salida (E/S), impresoras, discos, cintas... Veamos algunos ejemplos sencillos sobre el uso de las colas.

Cuando se envían trabajos a una impresora, se quedan en orden de llegada, así, en esencia, los trabajos enviados a una impresora, se ponen en una cola.

Prácticamente toda fila real es (supuestamente) una cola. Por ejemplo las colas en las taquillas son colas porque se atiende primero a quien llega primero.

Otro ejemplo se refiere a las redes de computadores. Hay muchas redes de computadores personales en las que el disco está conectado a una máquina, conocida como servidor de archivos.

4

Los usuarios en otras máquinas obtienen acceso a los archivos sobre la base de que el primero en llegar es le primero atendido, así que la estructura de datos es una cola.

Entre otros ejemplos podemos mencionar:- Por lo general, las llamadas telefónicas a compañías grandes se colocan en una cola,

cuando todas las operadoras están ocupadas.- En universidades grandes, cuando los recursos son limitados, los estudiantes deben

firmar una lista de espera si todas las terminales están ocupadas. Aquel estudiante que haya estado más tiempo en una terminal es le primero que debe desocuparla, y el que haya estado esperando más tiempo será el que tenga acceso primero.

- En un supermercado, intentar simulas el funcionamiento de una cola para saber cuantas cajas son necesarias dependiendo de varias condiciones, el número de clientes, y el tiempo medio de clientes.

Una rama completa de las matemáticas, denominada teoría de colas, se ocupa de hacer cálculos probabilísticos, de cuanto tiempo debe esperar los usuarios en una fila, cuanto más larga sea y oras cuestiones similares. La respuesta depende de la frecuencia con que llegan los usuarios a la fila y cuánto le lleva procesar a un usuario una vez que ha sido atendido. Ambos parámetros se dan como funciones de distribución de probabilidad. En casos sencillos se puede calcular una respuesta analíticamente. Un caso fácil sería una línea telefónica con un operador. Si el operador está ocupado, los usuarios se colocan en una cola de espera (hasta llegar a un límite máximo). Este problema es importante para los negocios, porque hay estudios que han demostrado que la gente cuelga rápido el teléfono.

Si hay k operadores, entonces es mucho más difícil resolver este problema. Los problemas cuya solución es analítica es difícil de obtener a menudo se resuelve con simulaciones. En este caso podríamos necesitar una cola para efectuar la simulación. Si k es grande, también necesitaremos otras estructuras de datos para hacer esto con eficiencia.

Como hemos visto, las colas son ampliamente utilizadas para gestionar recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento), cuando se trabaja en un sistema multiusuario y se ejecuta un programa, el sistema operativo añade la petición a la “cola de trabajo”. Son muy abundantes los usos de las colas, es sorprendente que, como las pilas, sea tan importante una estructura de datos tan sencilla.

OPERACIONES CON EL TDA COLA

Asociadas a esta estructura, existen una serie de operaciones fundamentales que permiten su manipulación de cara a su utilización en una aplicación.

La primera operación que se va a ver, es la primera operación que se debe ejecutar; la creación de la estructura, Crear_cola se emplea tanto para crear la cola como para eliminar todos los elementos que contenga, operación que llamaremos Borrar_cola.

Crear_cola (C: cola, resp: lógico)Es necesario que se pase por referencia una variable que represente a la estructura cola para su creación. Si la cola ha sido creada, devuelve el valor TRUE, mientras que si no se pudo crear FALSE. (Aunque haya sido creada, devuelve la cola vacía y si la creamos ya teniendo un contenido anterior, ese contenido se pierde.)

Borrar_cola (C: cola, resp: lógico)En esta operación también es necesario que se pase por referencia una variable para el vaciado de la cola. Si la cola ha sido borrada, devuelve el valor TRUE, mientras que si no se pudo borrar devuelve el valor FALSE. Lo que realiza es una llamada a crear_cola de tal manera que todos los elementos son nulos y lo interpreta como si estuviera vacía cada posición..

5

Una vez ya creada la estructura se va a poder trabajar con el resto de operaciones fundamentales asociadas a una cola: Vacía?, Llena?, Tamaño, Primero, Queue (Encolar) y Dequeue (Desencolar).

Vacía? (C: cola, resp: lógico)Es una operación de tipo lógico o booleano que recibe como argumento la variable que representa la cola, si está vacía, es decir sin elementos, devuelve el valor TRUE y si por el contrario la cola presenta algún elemento devuelve FALSE.

Llena? (C: cola, resp: lógico)Es la operación inversa a vacia? Luego si devuelve TRUE es que la cola está llena, es decir, todas las posiciones están ocupadas, incluida la última, por el contrario si devuelve FALSE es que todavía quedan posiciones por ocupar.

Tamaño (C: cola, n: numérico)La variable numérica n devuelve el tamaño de la cola.

Queue (C: cola, E: elto, resp: lógico)Queue, en inglés significa encolar, con esta operación se procede a insertar elementos en la cola. Es necesario que se pase por referencia la variable que representa a la cola, el paso del elemento que se quiere insertar no es necesario que se realice por referencia, sino que se realizará por valor. En esta operación lo que hacemos es incrementar tamaño y final y poner en la posición final el elemento.

Dequeue (C: cola, E: elto, resp: lógico)Cuyo significado es desencolar, proceder al a eliminación de elementos de la cola, luego es necesario que la cola presente al menos un elemento. Por tanto se debe comprobar que la cola no esté vacía, si estuviese vacía resp devolvería el valor FALSE. Una vez observada la presencia de elementos, se realiza la extracción por el extremo frente y se decrementa la longitud de la cola y se incrementa el frente. En este caso se pasa por referencia la variable cola, y el valor del elemento a desencolar.

IMPLEMENTACIÓN CON VECTORES (Estructura circular):

Como el TDA COLA, no es un tipo de dato preestablecido, será necesario la definición de la estructura para una posterior utilización.

La cola vendrá representada como un registro formado por los siguientes campos:

1. Un campo longitud que almacena el tamaño de la cola, indica cuántos elementos posee la cola. Definiendo MAX como el tamaño máximo del vector, y por lo tanto de la cola, entonces la cola esta vacía si longitud == 0 y está llena si longitud == MAX.

2. Un campo principio que almacena el índice que del primer elemento que esté dentro de la cola.

3. Un campo último que almacena el índice del último elemento que se haya insertado en la cola.

4. Un campo datos que almacena físicamente los elementos a través de un vector.

En algorítmico:

{Declaración de tipos}ELEMENTO = T; {genérico}

6

POSICIÓN = numérico;COLA = registro de

Longitud, prim, ult : numérico;INFO : vector[1..MAX] de ELEMENTO;

Fin registro;

Dado que el almacenamiento de los elementos se efectúa en un vector, es necesario que se declare con anterioridad el tamaño máximo del mismo, que será el que imponga la capacidad máxima de la estructura de datos, este puede ser un problema potencial, pero con frecuencia, las colas se mantienen pequeñas aun en presencia de una gran cantidad de operaciones.

La representación de listas por medio de vectores, también llamado arreglos, puede usarse para las colas, pero no es muy eficiente. Es cierto que con un puntero al último elemento es posible ejecutar queue en un número fijo de pasos, pero dequeue, que suprime el primer elemento, requiere que la cola completa ascienda una posición en el vector. Por lo cual, dequeue lleva un tiempo Ω(n) si la cola tiene longitud n.

Para evitar ese gasto se debe adoptar un punto de vista diferente. Imaginémonos un vector como un círculo en el que la primera posición sigue a la última (es decir, que siempre que el frente y el final lleguen al final del vector, regresen al principio) La cola se encuentra en alguna parte de ese círculo, ocupando posiciones consecutivas, con el extremo posterior en algún lugar a la izquierda del extremo anterior.

Para insertar un elemento en la cola se mueve el puntero c.ult una posición en el sentido de las manecillas del reloj, y se escribe el elemento en esa posición. Para suprimir, simplemente se mueve c.prim una posición en el sentido de las agujas del reloj. De esta manera, la cola se mueve en ese mismo sentido conforme se insertan y suprimen elementos. Utilizando este modelo, los procedimientos queue y dequeue se pueden escribir de tal manera que su ejecución se realice en un número constante de pasos.

Hay una sutileza que surge en esta representación, es decir si c.ult apunta a una posición adelantada con respecto al último elemento (en el sentido de las agujas del reloj) y no a ese mismo elemento.

7

El problema reside en que no hay manera de distinguir entre una cola vacía y una que ocupa el círculo completo, a menos que se mantenga un bit de verificación, que sea verdadero si y sólo si, la cola está vacía, sino se debe evitar que la cola llegue a llenar todo el vector.

Veamos la razón de esto, supongamos que la cola tiene MAX elementos. Entonces c.ult debería apuntar una posición delante de c.prim en el sentido contrario de las manecillas del reloj.

Pero fijémonos en como se representa una cola vacía. Consideremos primero, que en la cola hay un solo elemento, entonces c.prim y c.ulrt apuntan a la misma posición. Si en estas condiciones se suprime ese elemento, c.prim avanza una posición en el sentido de las manecillas del reloj, formando una cola vacía. Así en una cola vacía, c.ult está a una posición de c.prim en sentido contrario al de las agujas del reloj, es decir, está exactamente en la misma posición que ocuparía si la cola tuviera MAX elementos.

En consecuencia, resulta evidente que cuando el vector tenga MAX lugares, no se puede permitir que la cola crezca más que MAX –1 (ya que sólo se puede distinguir MAX diferentes tamaños y uno de ellos es el cero, luego la cola está llena cuando hay MAX –1 elementos), a menos que se introduzca el mecanismo antes comentado, para distinguir las colas vacías.

8

Hay que tener en cuenta que algunos programadores, no usan una variable para hacer el seguimiento del tamaño, ya que se calcula implícitamente comparando c.ult y c.prim, pero existen casos especiales, que nos exigen ser muy cuidadosos al modificar el código escrito de esta forma.

/* IMPLEMENTACIÓN DEL TDA COLA USANDO VECTORES */

IMPLEMENTACIÓN CON LISTAS ENLAZADAS

Como ya hemos dicho, las colas son un tipo de lista luego su definición es recursiva. Hay dos opciones para implementar el TDA Cola (al igual que vimos con las listas):

a) Utilizando listas sin cabecera, donde la estructura esta formada por variables dinámicas.b) Utilizando listas con cabeceras, en la que el contenido siguen siendo variables

dinámicas pero la cabecera es una variable estática.

a)

b)

En algorítmico:

{Declaración de tipos}ELEMENTO = T; {genérico}NODO = registro de

info : ELEMENTO;sgte : puntero a NODO;

Fin registro;POSICIÓN = puntero a NODO;COLA = registro de

Longitud : numérico;prim, ult : POSICION;

Fin registro;

/* IMPLEMENTACIÓN DEL TDA COLA USANDO LISTAS ENLAZADAS */

9

DEFINICIÓN DE BICOLAS

Una bicola también es conocida como una cola doble, ya que las bicolas no dejan de ser una variante de la estructura de datos cola simple.

La variante comentada consiste en que ahora los elementos van a poder ser insertados o eliminados por cualquiera de los dos extremos de la cola.

Por tanto, se observa que la entrada o salida de elementos podrá efectuarse tanto por el principio como por el final de la misma, aunque la estructura seguirá comportándose como una cola en cuanto al procesamiento de elementos.

La representación gráfica de una bicola o cola doble en una representación estática es la siguiente:

Dentro de las colas dobles o bicolas, también podrán encontrarse otras dos variantes:

1) Bicola con entrada restringidaEn este caso se permite que la entrada de elementos se hagan sólo por un extremo, que será el extremo final al igual que ocurrirá en el TDA cola.Por su parte las extracciones o salidas de elementos podrán seguir efectuándose a través ambos extremos de la bicola, es decir tanto por el principio como por el final. La representación gráfica de esta bicola sería:

2) Bicola con salida restringidaEn este caso permite que las eliminaciones o extracciones de los elementos se hagan sólo por un extremo, que será el extremo principio al igual que ocurría en la cola simple. Por su parte las inserciones o entradas de elementos de la bicola podrán seguir efectuándose a través de cualquiera de los extremos de la bicola, es decir tanto por el principio como por el final. La representación gráfica de esta bicola sería:

10

DEFINICIÓN DE COLAS DE PRIORIDADES

Otra de las variantes que se ofrece dentro del tipo abstracto de datos cola, son las colas de prioridades.

Una cola de prioridades es un conjunto de elementos tales que cada uno de ellos se le ha asignado una prioridad de manera que el orden en que los elementos son procesados y eliminados de la cola debe seguir las siguientes reglas:

1) Un elemento de mayor prioridad se procesa con anterioridad a otro elemento de menor prioridad.

2) Cuando dos elementos presentan la misma prioridad, estos elementos se procesan de acuerdo al orden en que fueron insertados en la cola, es decir de acuerdo a su origen de llegada.

La aplicación de las colas de prioridades a actividades actuales es importantísima, ya que existen una gran capacidad de procesos de producción donde determinadas tareas presentan unos tiempos críticos de ejecución de manera que es preciso que tengan una prioridad sobre el resto de tareas.

Con respecto al mundo de la informática estas colas permiten la utilización de sistemas de tiempo compartido donde los programas con mayor prioridad se procesan con anterioridad a los programas que estén en espera de recursos con una prioridad menor. Cuando dos programas presentan la misma prioridad se procesan como si de una cola simple se tratase.

La manera de representar una cola de prioridades en memoria es variable, existiendo varias implementaciones que cumplen perfectamente esta función. Entre las más utilizadas cabe destacar dos de ellas:

1) Mediante una lista unidireccional

Donde se creará una única lista unidireccional en la cual los elementos se irán insertando, de manera ordenada, de acuerdo a su orden de prioridad y cumpliendo las reglas enunciadas anteriormente, de manera que el procesamiento de los mismos sea coherente con su orden de prioridad.

Donde se creará una única lista unidireccional en la cual los elementos se irán insertando, siempre al final de la cola y es al sacar los elementos cuando se busca al que tiene mayor prioridad.

El primer método es más eficiente porque requiere menos operaciones, buscar la posición en la cual se inserta un elemento que buscar el elemento para extraerlo.

2) Mediante múltiples colas

Donde se crearán tantas colas como ordenes de prioridad existan, de manera que cada elemento que presente un determinado orden de prioridad será insertado en la cola creada para dicho orden de prioridad.

Posteriormente el procesamiento de estas colas tendrá lugar de manera que vacíe la cola que presente los elementos de mayor prioridad, y una vez vaciada se procese la siguiente cola en orden de prioridad y así sucesivamente hasta que se procesen todos los elementos.

Cabe destacar que cuando se está procesando una cola que presenta una prioridad, supóngase intermedia, y se inserta un nuevo elemento en una cola de mayor prioridad, debe pasar a procesarse esta cola antes de finalizar con los elementos de la cola intermedia, ya que ahora si existe una cola con mayor prioridad que presenta algún elemento.

11

BIBLIOGRAFÍA

Estructura de datos y algoritmos.Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.

Estructura de datos y algoritmosWeiss.

Estructura de datos. Implementación clásica y orientada a objetos.V. Alonso Secades, R. Berjón Gallinas, M. Raboso Mateos.

Estructura de datos.Nell Dale, Susan C. Lilly.

Documentación encontrada en páginas de internet.

12