Estructuras de datos: Colas en Java
Las colas es un tema que se maneja en las estructuras de datos.
Las colas son de tipo FIFO es decir el primero que entra es el primero que se va diferente como se maneja en una pila o stack.
Las acciones permitidas en una cola son:
Adicional mente tengo que validar si silo hay un elemento en la cola por que si es asi pues restablezco los valores del frente y del final.
y ahora viene el algoritmo que me coso hacer el de mostrar la cola, se debe mostrar solo los elemento que están en cola, no voy hacer el pseudocodigo :(
Primero para poder mostrar tenemos que saber que solo se van a mostrar los datos que esta en cola y tenemos que mirar como hacemos para no salirnos del rango y saltar de la ultima posision a la primera.
Entonces vamos a manejar una variable local que tenga como valor el frente
esa variable va a ir cambiando (i+1)%tamaño es decir va a ir recorriéndose toda la cola y termina cuando la variable sea igual a su valor inicia que es el frente.
entonces si tenemos este caso:
Solución caso 1:
entonces decimos que i sea igual al frente es 0 como el do-while se ejecuta almenos una vez entonces imprime el valor del 5 y la variable i se convierte ahora en 2, y asi sucesivamente.
Pero cuando esta en el indice 3 imprime 10 y la i se convierte en 0 y ahora hace la validación de i!=frente pero como es falsa sale del ciclo.
ay lo tienen.
Ahora por que utilice el do-while como la condición tiene que se i!=frente en la primera iteracion esto no se cumple utilizando cualquier otro ciclo, pero con el do-while nos saltamos esa validación en la primera iteracion
Solución caso 2 y 3:
Si lo dejamos asi impi!=rimirla asi
6 51
No imprimiría el 10 por que es lo que estamos diciendo con i!=final. Entonces lo que queremos que haga es lo mismo que hace hasta ahora pero que si imprima el 10, y para ellos es necesario agregar una condición dentro del cliclo
Las colas son de tipo FIFO es decir el primero que entra es el primero que se va diferente como se maneja en una pila o stack.
Las acciones permitidas en una cola son:
- Crear cola vacía
- Verificar que la cola este vacía
- Añadir un dato al final de la cola
- Eliminar de los datos la cabeza de la cola
Me han puesto el reto de crear una cola con array de tipo circular. Pero antes de comenzar a crearlo se tiene que tener en cuenta lo siguiente.
Una cola tiene los siguiente atributos:
- Frente: Primer dato de la cola o indice del primer elemento de la cola
- Final: el es el ultimo dato de la cola o el indice del ultimo dato de la cola
- Tamaño: es el tamaño de la cola
Aunque revisando en un libro el final lo identifica como la siguiente posición del ultimo elemento.
Una cola circular se veria de la siguiente forma.
Para tener en cuenta:
- En una cola se elimina de aun solo elemento
- En una cola no existe campo vacía entre el frente y el final
- Se elimina por el frente y se inserta por el final
En una cola se debe poder hacer:
- Insertar
- Eliminar
- Mostrar
- Vaciar la cola
Como saber si una cola esta llena:
Una cola circular se sabe que esta llena si el indice siguiente al del final es el de frente.
si (final+1)%tamaño==frente retornar true; si no retornar false;
Se estarán preguntando que es (final+1)%tamaño==frente
Primero tenemos que ya ver la cola como no como una linea o como un vector, se tiene que imaginar como un circulo para poder entender.
Por ejemplo digamos que tenemos una cola circular de tamaño 4 se tiene que ver asi:
Por ejemplo digamos que tenemos una cola circular de tamaño 4 se tiene que ver asi:
Si se llena de datos quedaría así
vemos en la posicion 0 con valor 5 la posicion 1 con valor 6 la posicion 2 con valor 51 y la posicion 3 con valor 10.
El puntero frente esta en el 0 y el final esta en 3.
A simple vista se ve que la cola esta llena pero como hacemos saberle al software que asi es.
SI fuera un vector lineal para saber si esta lleno simplemente verifico que el punto final este en la ultima posición posible que sabe con (tamaño-1) .
Y es mas en este caso aplica pero que pasa si ahora las cosas estan asi.
Sigue estando lleno pero si aplico lo anterior, que:
(tamaño-1) == final
esto me retornaría false por que el final esta en la posición 0. En este momento es cuando tu cerebro estalla.
Como es posible que el final este en la posición 0 y el frente en la posición Jaja pues por eso es una cola circular por que las posiciones se van corriendo.
entones hay es cuando entra (final+1)%tamaño==frente.
que significa: el residuo de posición del final mas uno y tamaño es igual al frente
Si lo aplico a este caso daría asi (0+1)%4=1. Esto devolvería true entonces si esta llena la cola
Ahora (final+1)%tamaño==frente hay que tenerlo muy en cuenta por que sera lo que le dara la magia a todo el código
Como saber si una cola esta vacia:
esto si es mas sencillo la misma lógica se puede utilizar tanto para una cola no circula como para una circular.
si frente == -1 retornar vacia si no retornar noVacia FinSi
por que menos uno, el menos uno se utiliza por que como la cola es de vectores el vector comienza desde 0 entonces antes de eso no hay nada. Ahora si se desea comenzar la cola desde 1 se cambia el -1 por un 0.
Como Eliminar:
Para elminar un elemento de una cola simplemente se corre el frente, pero antes que eso se tiene que validar que la cola no este vacia.
Entonces digamos que tenemos la cola asi.
Y para eliminar el elemento se correo la posición del puntero frente y queda asi
Entonces tenemos que entender que no es literalmente eliminar el elemento de la posición por que en ese posición puede seguir estando el numero 5 pero a la hora de mostrar en la cola no se va tener en cuenta luego cuando se inserta ese 5 va hacer reemplazado por el nuevo dato que se inserte.
Adicional mente tengo que validar si silo hay un elemento en la cola por que si es asi pues restablezco los valores del frente y del final.
Como Insertar:
Para insertar en la cola primero tengo que validar que la cola no este llena.
SI no esta llena pero si esta vacía aumento el frente en uno pero para eso se utiliza la magia
frente=(frente+1)%tamaño
ademas decimos que el final de la cola también aumenta entonces final=(final+1)%tamaño
y se inserta el dato en la posición del final que antes de que nosotros insertamos algo no tenia nada.
asi quedaría el pseudocodigo
Como Mostrar la Cola
Primero para poder mostrar tenemos que saber que solo se van a mostrar los datos que esta en cola y tenemos que mirar como hacemos para no salirnos del rango y saltar de la ultima posision a la primera.
Entonces vamos a manejar una variable local que tenga como valor el frente
esa variable va a ir cambiando (i+1)%tamaño es decir va a ir recorriéndose toda la cola y termina cuando la variable sea igual a su valor inicia que es el frente.
entonces si tenemos este caso:
Tiene que imprimir: 5 6 51 10
Pero si ya tenemos este caso.
tiene que imprimir: 6 51 10
y si tenemos esto
tiene que imprimir 6 51 10 5
Entonces se puede identificar que pueden haber 3 casos.
Comencemos solucionando el primer caso. Donde la cola esta llena y el frente se encuentra en el primer indice y el final en el ultimo indice.
Solución caso 1:
entonces sabemos que termina cuando la variable i es igual a puntero final o que es lo mismo a que la variable i tiene que ser diferente al punto frente. Suena algo raro pero asi es y para poder hacerlo nos valemos de un ciclo do-while
i = frente;
do {
imprimir vector[i]);
i = (i+1)%tamaño;
}mientras que (i!=frente);
entonces decimos que i sea igual al frente es 0 como el do-while se ejecuta almenos una vez entonces imprime el valor del 5 y la variable i se convierte ahora en 2, y asi sucesivamente.
Pero cuando esta en el indice 3 imprime 10 y la i se convierte en 0 y ahora hace la validación de i!=frente pero como es falsa sale del ciclo.
ay lo tienen.
Ahora por que utilice el do-while como la condición tiene que se i!=frente en la primera iteracion esto no se cumple utilizando cualquier otro ciclo, pero con el do-while nos saltamos esa validación en la primera iteracion
Solución caso 2 y 3:
Teniendo en cuenta el codigo anterior ahora como hacemos para que no imprima el 5 que esta fuera de la cola. Por que si se deja como esta antes entonces imprimiria asi:
6 51 10 5 y el 5 no debe imprimirlo ya que esta fuera de la cola entonces el ciclo debe terminar en 10. Entones lo que se debe hacer es estar pendiente de que si i es igual al final no entrar al cliclo, pero si no entramos al ciclo no se imprimira el valor entonces para dar solucion a esto el codigo quedaria asi:
i = frente;
do {
imprimir vector[i]);
i = (i+1)%tamaño;
}mientras que (i!=frente&& i!=final) ;
Si lo dejamos asi impi!=rimirla asi
6 51
No imprimiría el 10 por que es lo que estamos diciendo con i!=final. Entonces lo que queremos que haga es lo mismo que hace hasta ahora pero que si imprima el 10, y para ellos es necesario agregar una condición dentro del cliclo
i = frente;
do {
imprimir vector[i]);
i = (i+1)%tamaño;
si(i==final)
imrpimir vector[i]
FinSi
}mientras que (i!=frente&& i!=final) ;
entonces como yo en todo momento se cual va a hacer la siguiente posicion esto revisando a cada momento si la siguiente va hacer la final para que la imprimima antes de que se salga del ciclo.
y ahora si imprimiria 6 51 10