Programacion de colas

 

UNIVERSIDAD DE EL SALVADOR  FACULTAD MULTIDISCIPLINARIA PARACENTRAL  DEPARTAMENTO DE INFORMATICA  INGENIERIA DE SISTEMAS INFORMATICOS       CATEDRA:                    PROGRAMACION II       CATEDRATICO:           INGA. YANCY ELIZABETH MARTINEZ DE MOLINA        GRUPO TEORICO:  01 y 02        MATERIAL  DE LECTURA DE LA  UNIDAD VI ESTRUCTURAS DE TIPO COLAS 

Estructuras de Tipo Colas
Unacola es un conjunto ordenado de elementos del que pueden suprimirse elementos de un extremo (llamado la parte delantera de la cola) y en el que pueden insertarse elementos del otro extremo (llamado la parte posterior de la cola).

Parte delantera

Parte posterior
En la figura anterior se ilustra una cola que contiene tres elementos A, B, y C. A esta en la parte delantera de la cola y C está enla posterior. Una cola es un tipo especial de lista abierta en la que sólo se puede insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído. Este tipo de lista es conocido como lista FIFO (First In First Out), el primero enentrar es el primero en salir. OPERACIONES PRIMITIVAS: Se aplican tres operaciones primitivas a una cola. a. La operación insert( q, x ) inserta el elemento x en la parte posterior de la cola q. b. La operación x = remove( q ), suprime el elemento delantero de la cola q y establece su contenido en x. c. La operación empty( q ), retorna false o true, dependiendo si la cola contiene elementos o no.La operación insert( q, x ) puede ejecutarse siempre, pues no hay límite en la cantidad de elementos que puede contener una cola. Sin embargo, la operación remove ( q ) sólo puede

PRN 275 Programación II – Ciclo I/2010

aplicarse si la cola no está vacía; no hay forma de remover un elemento de una cola que no contiene elementos. El resultado de un intento no válido de remover un elemento deuna cola vacía se denomina subdesbordamiento. Estructura de tipo cola implementada con array (memoria estática). La definición de una cola ha de contener un array para almacenar los elementos de la cola y dos marcadores o apuntadores para mantener las posiciones frente y final de la cola, un marcador apunta a la posición de la cabeza de la cola, y el otro al primer espacio vacío que sigue al finalde la cola. Cuando un elemento se añade a la cola, se verifica si el marcador final apunta a una posición válida entonces se añade un elemento a la cola y se incrementa el marcador final en 1. Cuando un elemento se elimina de la cola se hace una prueba para ver si la cola está vacía, y si no es así se recupera el elemento de la posición apuntada por el marcador de cabeza y este se incrementa en1.

En la implementación se usa un arreglo para contener los elementos de la cola y dos variables, cabeza (parte delantera) y final ( parte posterior) para contener las posiciones dentro del arreglo de los elementos primero y último de la cola. Al principio se establece q.final en –1 y q.cabeza en 0. La cola está vacía cada vez que q.final < q.cabeza. Ejemplo gráfico 1. q 0 A 0 1 B 1 2 C 2 3 4 56 7

La cola q está vacía q. final=-1; q.cabeza=0; Se insertan los elementos A B y C a la cola q. final=2; q.cabeza=0;

3

4

5

6

7

B 0

C 1

2

3

4

5

6

7

Se suprime el elemento A de la cola q. final=1; q.cabeza=0;

En este ejemplo la operación remove, cuando se suprime un elemento, toda la cola se cambie al principio del arreglo. Por lo que cabeza siempreestá en la posición 0 del arreglo que es la parte delantera de la cola. Este método no es eficiente. Cada supresión de un elemento significa mover cada uno de los elementos restantes en la cola. Ejemplo gráfico 2. Considerar que el arreglo que contiene la cola es un círculo. Imaginamos que el primer elemento del arreglo esta inmediatamente después de su último elemento. Esto implica que incluso...