sábado, 19 de marzo de 2011

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.
larga fila de personas
Con fines educativos una cola se la puede representar gráficamente así:

colas
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:

vector colas

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:

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 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.

62 comentarios:

  1. y segun tu cuales son las caracteristicas y podrian llegar a diferenciar la cola circular de la normal .. x k imagino k x algo se la usa no??

    ResponderEliminar
  2. la única diferencia entre una cola normal y una circular es su manera de implementacion, no tiene ninguna diferencia en comportamiento, es por eso que casi en ninguna parte implementan este tipo de cola circular, excepto algunos docentes la UMSA en la carrera de informática, con lo cual no estoy de acuerdo. Mira como la diferencia es solo la implementación yo podria crear mi propia versión de código utilizando otras cosas y le llamaria cola danielistica, pero no seria lo correcto que le ponga otro nombre pues si tiene el mismo comportamiento. Al final de todo una cola es una cola.
    Muchas racias por visitar mi blog, tu blog y nuestro blog, y por comentar.

    ResponderEliminar
  3. seria posible que hagas un tema explicando las listas?? como k no estubo tan claro en mi clase...jeje XD

    ResponderEliminar
  4. claro muy pronto entonces publicare Listas Enlazadas simples y dobles, y se vienen mas novedades, y gracias por el comentario y sugerencia.

    ResponderEliminar
  5. esteee pero para cuando lo vas a hacer... mira k mi examen es este sabado y me gustaria revisar full esto de listas asi k x fa subi algo de listas vale?? grax

    ResponderEliminar
  6. muchas gracias por dar la molestia e subir informacion util para personas que realmente quieren aprender

    ResponderEliminar
  7. Puedes publica algo sobre Bi colas y sus aplicaciones en codigo C#

    ResponderEliminar
  8. amigo si fueras tan amable vuelvelo a subir por favor...ya no da el link

    ResponderEliminar
  9. Los enlaces ya están corregidos, muchas gracias por el aviso, todo se debe a la reorganización que hubo por aquí, avisen si algún otro enlace no funciona, gracias

    ResponderEliminar
  10. Excelente blog recorrí varios post y me gusto mucho el poner un ejemplo descargable para un mejor entendimiento.

    Gracias.

    ResponderEliminar
  11. hola disculpa y no podrias poner un codigo ya completo sobre colas, es decir que ya esten con el main ? :D este blog esta muy interesante, estoy iniciando en java =P

    ResponderEliminar
  12. Este blog me ha parecido de los mejor explicados q he visto, pocas veces comento pero este blog se lo merece. esta muy bien el trabajo de las persona que suben sus explicaciones y ejemplos. muy claros.

    ResponderEliminar
  13. Esta muy bien explicado, me queda mas claro de aqui que de la explicacin de la maestra, Gracias.

    ResponderEliminar
  14. Biiieenn COol..ttodo estto estta Geeniiaall C:
    me gustta la informeiishon qe biene aqqii..viivan los Hipiies!!♥&& el ROck xD

    ResponderEliminar
  15. esto es dediiqado para el 3BPS!♥ del CECYTE Floriido! los AMOdoro..I like!! C:

    ResponderEliminar
  16. Anahi ,Lupita,Cruz ,Genesis Y YO (Sonia) andamos copiando todo lo que dice esta pag. O;
    POSDATA:
    El cholo(jorge)se siente mosca en leche haha xD Okno.?._.

    ResponderEliminar
  17. Tu que chino xD Okno ._.

    ResponderEliminar
  18. SE PASAN STE BLOG S PARA AYUDAR A PROGRAMAR Y EXPLICAR LOS TMAS, YA CASI LO HACEN UN CHAT

    PD:Gene te pasas usaste mi url ia bras ehhhhhhhh

    ResponderEliminar
  19. lo que esta arriba del comen del chino↑↑↑ somos del grupo BPS CECYTE(Programadoras :}
    wahahaha 3;)

    ResponderEliminar
  20. Recordatorio mi cumple el viernes 4de nov :$ (18) :$ atte:Sooniia'C;

    ResponderEliminar
  21. Ahhhhhhh sonia y yo no copie todo l9o que dice la pagina ehhhhhhhhhhhh,
    solamente lo que se me hizo mas facil de entender, (osea nada jajajajaja)
    NTK

    ResponderEliminar
  22. ehehhheeiii..YO empece estta cura! xD
    IceGreenMonoXiiremoLovePeace♥ILY'JJ;;FOrever
    &&&& AMO amiis qompas de 3BPS CECYTE Florido!TM..son SUPER Geniialees&&& Grandiiosos!! C:
    'lllOS SUPER-mega AMOhh Okeeeeei♥

    ResponderEliminar
  23. las clases no funcionan!! el enlace a dropbox no funciona

    ResponderEliminar
  24. olap oie esta super bien lo que explicas pero no puedo descargar la clase cola me manda un error como le hago la vdd esque si lo necesito muxo

    ResponderEliminar
  25. Enlaces corregidos, gracias por la visita.

    ResponderEliminar
  26. oie mil gracias ya chekre la estructura para terminar mi programa gracias

    ResponderEliminar
  27. necesito el metodo que permite recuperar un elemento de la cola. gracias

    ResponderEliminar
  28. ola no se si sepas como resolver en java
    una matriz de 3x3 que multiplique a otra matriz de 3x3 y mande el resultado plis si se pudiera me ayudarias muxo si no no te preocupes gracias
    esque lo intente y nisiquiera me imprime la matriz asi
    123
    456
    789
    mas bien la imprime asi
    1
    2
    3
    4
    5
    6
    7
    8
    9

    ResponderEliminar
  29. ola oie no se si me puedas ayudar vdd lo que pasa es que necesito saber como hacer el metodo de insercion en java y la vdd es que no se que onda si me pudieras ayudar te lo agradeceria muxo plis bye espero tu respuesta

    ResponderEliminar
    Respuestas
    1. ola creo que yo tengo una respuesta para ese método que buscas mira si entras a este blog vas a encontrar lo que buscas y por cierto daniel felicidades tu blog esta genial

      http://javalagartos.blogspot.mx/2012/03/metodo-de-insercion.html

      Eliminar
  30. Que tal Daniel, tu explicación me parece muy buena. Revise el código que tienes de la clase Cola (Cola.java) y en la linea 71 hay una instanciación dela clase ColaCircular sin embargo esa clase no la estas compartiendo, la podrías compartir para ver el ejemplo completo.

    Gracias.

    ResponderEliminar
  31. ¿Qué ventajas tiene la cola lineal ante la circular?

    ResponderEliminar
  32. BUEN APORTE...GRACIAS

    ResponderEliminar
  33. Bueno, en mi humilde opinion creo que una cola circular, se podria decir que mejoraria el tiempo de ejecucion xk ahora no existiria el corrimiento de los datos, sino se irian actualizando los identificadores punteros de cada una de las casillas en la cola.

    ResponderEliminar
  34. Marca error dentro de la clase cola defines esto:
    private void copiar(ColaCircular B) {
    while (!B.esVacia()) {
    adicionar(B.eliminar());
    }
    }

    Pero no das un link para descargar la clase ColaCircular

    ResponderEliminar
  35. Hola que tal buena información, aunque seria mejor si incluyeras el método main, bueno ojala y puedas.

    ResponderEliminar
  36. compañeros, no es tan difícil hacer el método main, es solo cuestión de ponerse a leer los métodos y marca error porque no existe el método o la clase ColaCircular() ...

    ResponderEliminar
  37. pues si me sirvio la informacion pero todavia me confundo un poco jaja

    ResponderEliminar
  38. esta bien pero me confundió un poco publica mas por favor amigo eh es una orden

    ResponderEliminar
  39. publica mas informacion para todos lo que queremos aprender mas, ya a que mi maestro no le entiendo, bueno muy poco,en estas paginas aprendo lo que no se aprende en clase

    ResponderEliminar
  40. sii mejor ponganc a estudiar y pongan atencion por de jajaja

    ResponderEliminar
  41. enroces si existe la clase ColaCircular o no me confunden solo aclarenme eso es importante grasias

    ResponderEliminar
  42. mmmm es vdd esta pagina ayuda demasiado pero creo que seria de mucha ayuda que explicaran un poco mas detallado sobre el tema

    ResponderEliminar
  43. podrias explicar las colas circulares y las colas dinamicas

    ResponderEliminar
  44. Muy buen blog que acabo de descubrir y agregar a favoritos. Aprovecho para proponer una pequeña mejora a la clase:

    Tal y como está ahora implementado, cuando extraemos un objeto de la cola movemos los índices, pero dejamos la referencia en el Array (Hasta que se inserten otra vez MAXIMO elementos y se sobreescriba).

    De esta forma puede pasar que aunque el código que utiliza la cola ya haya procesado y desechado el objeto después de extraerlo, el recolector de basura no pueda marcarlo para su eliminación porque su referencia sigue viva. Si la cola es larga y los objetos son grandes puede ocasionar problemas o ralentizar el programa...

    Por suerte la solución es tan fácil como poner a null su posición en el array después de la extración.

    Saludos

    ResponderEliminar
  45. dfjdfvnjk gr1tgrtgt2g1005103600+540+43205202gbfbbbhgbnhg+bbggbb1vb5b56h mhfghfhhhhnnnn

    ResponderEliminar
  46. no corre el programa en java eclipse

    ResponderEliminar
  47. Al autor:
    La diferencia entre cola y colaCircular es que la cola circular tiene un tamaño máximo de almacenaje y cuando se pasa este tamaño sobreescribe los elementos más antíguous.
    La cola 'normal' o 'simple' también puede tener longitud máxima pero está no permitira la entrada de más elementos cuando llegue a su máximo.

    ResponderEliminar
  48. MUCHAS GRACIA POR LA INFORMACIÓN ME SIRBIO DE MUCHO PARA PODER REALIZAR MIS ANTOLOGIAS DE LA UNI Y PODER ACLARAR ALGUNAS DUDAS RESECTO AL TEMA

    ResponderEliminar
  49. Buenisimo Gracias mano...

    ResponderEliminar
  50. podrian pasarme el metodo modificar una cola de personas

    ResponderEliminar

Deja tu comentario, agradecimiento, sugerencia o critica.