Colas java

4
Colas En Java Una cola es simplemente un lugar para almacenar cosas, donde esas cosas se insertan una detrás de otra y para extraer siempre se lo hace por adelante de la cola donde se encuentra el primer elemento. Una cola funciona como una fila o cola de personas, que esperan su turno para ser atendidas, la primera persona atendida es siempre la primera de la fila y cuando llega una persona y queremos incorporarla a cola o adicionarla debemos hacerlo por detrás de la ultima persona en la cola. Con fines educativos una cola se la puede representar gráficamente así: 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, 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 arrays 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.

description

Les dejo un apunte que me sirvio mucho!

Transcript of Colas java

Page 1: Colas java

Colas En Java

Una cola es simplemente un lugar para almacenar cosas, donde esas cosas se insertan una detrás de otra y para extraer siempre se lo hace por adelante de la cola donde se encuentra el primer elemento. Una cola funciona como una fila o cola de personas, que esperan su turno para ser atendidas, la primera persona atendida es siempre la primera de la fila y cuando llega una persona y queremos incorporarla a cola o adicionarla debemos hacerlo por detrás de la ultima persona en la cola.

Con fines educativos una cola se la puede representar gráficamente así:

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, 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 arrays 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 array), 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:

Page 2: Colas java

Consideremos que nuestro array bidimensional o vector lo creamos con 10 posiciones enumeradas del 0 al 9, la variable inicio guarda una posición antes en la cual se encuentra el primer elemento y la variable fin guarda la posición en donde se encuentra justamente el ultimo elemento.

Entonces los atributos que tendrá nuestra clase Cola de números enteros serán:

?1234

private final int MAXIMO = 101;private int[] V;private int inicio;private int fin;

Ahora una vez teniendo esta estructura hay que definir los métodos principales para manejar una cola, estos métodos son:

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

esLlena() : boolean 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 MAXIMO.

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

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

tamanio() : int retorna la cantidad de elementos que tiene la cola, para realizar esto se realiza la

Page 3: Colas java

resta fin - inicio.

copiar(Cola B) copia tal cual la cola B a la cola destino, al finalizar cola B queda totalmente vacía. Este método es muy útil al momento de hacer operaciones con colas.

Con todos estos métodos básicos  se puede realizar cualquier operación que necesitemos, ahora puedes descargarte la clase Cola de números enteros y otra clase cola para objetos Persona, tu puedes crear tu propia clase Cola que almacene lo que quieras ya solo hay que cambiar cierta parte del código.

Las clases son completamente funcionales y también debemos notar que una vez que llegamos al final de nuestro vector regresamos a la posición inicial de nuestro vector, es por eso que veras en el código varios operadores modulo.

Nota: Se suele implementar a veces una cola llamada cola circular, en realidad no existe una cola circular pues es la misma que se implementa en todas partes suelen llamarla así porque su implementación simula que los elementos van rotando en nuestro vector o array, sin embargo da lo mismo que cualquier cola, es por eso que solo existe o debería existir una clase Cola