martes, 8 de octubre de 2013

Colas

"¿Por que estas bloqueado?  - Por que tienes un solo cerebro y mientras estas pensando en muchas cosas dejaste la pregunta que te hice al final, es decir, en una COLA"


Definicion:  Es una regla que se aplica a una estructura lineal (arreglos y listas enlazadas) para que tengan un comportamieno FIFO( First in- First out) Primero en entrar - primero en salir, es decir primer elemento en almacenarse, primero en procesarse.

Una cola puede almacenar lo que nosotros queramos, números, personas, documentos, cualquier cosa. Esta estructura de datos tiene muchas aplicaciones en la informática al igual que la pila, por ejemplo cuando mandan a imprimir varios documentos a una impresora (Ejemplo puesto por el mismo profesor Juan Jose Puello), manda uno en word, manda otro en excel, manda otro en power point, para esto, existe una cola de impresión que sigue la filosofía, se imprimen los primeros documentos y si quiero imprimir un nuevo documento se adiciona al final de todos los documentos que están esperando a imprimirse.


Una vez comprendido en concepto ahora veamos como se implementa esto en un lenguaje de programación, por ahora lo implementaremos en Java. Java en sus librerías ya tiene la forma de implementar Colas (queue), nosotros ahora haremos como si no existiera, es decir crearemos nuestra versión, que es lo que generalmente se hace cuando se aprende colas en la universidad. Pues bien existen dos formas de implementar para que la cola sea o bien estática (reservamos un espacio fijo en memoria) o bien dinámica (el tamaño en memoria va creciendo según se requiere), se implementa con vectores o con listas enlazadas respectivamente. Nosotros implementaremos haciendo de un array bidimensional es decir de modo estático y al decir estático estamos diciendo que tendrá un limite para almacenar datos en la cola.

Para manipular elementos en el vector de la cola son necesarias variables que me digan en donde empiezan los elementos y otra en donde terminan, como tal vez estés pensando ¿porque no solo una? (una que me diga en donde termina asumiendo que siempre se empieza desde la posición 0 del vector), pues se puede implementar con solo una de estas variables pero presenta muchas desventajas pues si eliminamos un elemento de nuestra cola, (el primero justamente) tendríamos que recorrer todos los siguientes elementos una posición adelante y esta manera seria muy lenta de implementar pues que pasa si son 1000 elementos, eso es mucho tiempo perdido, entonces es por eso que usamos dos variables que me digan donde empieza y donde terminan los elementos de la cola, dos variables enteras que llamaremos inicio y fin, estas variables funcionan de la siguiente manera:

Colocar por un extremo, quitar por el otro

Por donde entra se colocaria la variable (Inicio) y por donde sale la variable( Fin), ahora, si consideramos que nuestro vector tiene 5 posiciones y deseamos ingresar un dato o, algo, primero debemos comprobar si esta llena la pila, o si esta vacia, ¿como lo hacemos? creando un metodo PUBLICO llamado "vacia" y otro llamado "llena", de la siguiente manera.

public boolean vacia() {retorna verdadero si la cola esta vacía es decir no tiene ningún elemento, para esto solo se pregunta si inicio es igual a fin.

public boolean llena(){ retorna verdad si es que la cola esta llena, pasa cuando se ha llenado todo el vector, la cantidad de elemento que permite la cola lo determina la variable Max.

poner() {adiciona un nuevo elemento a la cola, para esto solo se incrementa la variable fin y se coloca el elemento en esa posición.

quitar(){ extrae el primer elemento de la cola, para esto se retorna la posición inicio + 1 del vector y se incrementa inicio en 1.


Con todos estos métodos básicos se puede realizar cualquier operación que necesitemos

UTILIDAD: SIEMPRE QUE LOS RECURSOS DE PROCESAMIENTO SEAN MENORES A LAS DEMANDAS DE SU USO.

APLICACIONES: COLA DE PROCESOS, COLA DE IMPRESIÓN, SIMULACION

OPERACIONES: PONER Y QUITAR.

IMPLEMENTACION: VECTORES, LISTAS ENLAZADAS

coloquemos como ejemplo una variable que trabaje como un semáforo y los procesos como los carros. Los procesos pueden ser cooperativos o independientes. Dos o más procesos pueden cooperar mediante señales de forma que uno obliga a detenerse a los otros hasta que reciban una señal para continuar.
Se usa una variable de tipo semáforo, es decir,  para sincronizar los procesos.
Si un proceso está esperando una señal, se suspende hasta que la señal se envíe.
Se mantiene una cola de procesos en espera en el semáforo.
La forma de elegir los procesos de la cola en espera es mediante una política first in first out.
Asi como los procesos que hacemos que realice el sistema operativo de nuestro pc. igual.


0 comentarios :

Publicar un comentario