Colas (FIFO)

La Cola es una estructura de datos donde la inserción de ítem se hace en un final (el fin de la cola) y la recuperación/borrado de elementos se hace en el otro final (el inicio de la cola). Como el primer elemento insertado es el primero en ser recuperado, los desarrolladores se refieren a estas colas como estructuras FIFO (first-in, first-

).

Las colas son muy útiles en varios escenarios de programación, entre los que se encuentran:

• Temporización de Threads: 
  Una JVM o un sistema operativo subyacente podrían establecer varias colas para coincidir con diferentes prioridades de los threads. La información del thread se bloquea porque todos los threads con una prioridad dada se almacenan en una cola asociada.
• Trabajos de impresión: 
  Como una impresora normalmente es más lenta que un ordenador, un sistema operativo maneja los trabajos de impresión en un subsistema de impresión, que inserta esos trabajos de impresión en una cola. El primer trabajo en esa cola se imprime primero, y así sucesivamente.

• Operaciones Básicas
• Crear: se crea la cola vacía.
• Encolar: (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar: (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente: (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Tipos de colas

• Colas circulares (anillos): en las que el último elemento y el primero están unidos.

• Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

• Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.
• 
• Ejemplo:

public class Cola 
{
    private Object[] cola;
    private int frente;
    private int fin;
    
    public Cola(int tamanio)
    {
        cola = new Object[tamanio];
        frente = fin = -1;
    }
    
    public boolean isEmpty()
    {
        return frente == fin;
    }
    
    public boolean isFull()
    {
        return fin == cola.length-1;
    }
    
    
    public void insert(Object elemento)
    {
        if(isFull())
            System.out.println("La cola esta llena, elimine datos!");
        else
            cola[++fin] = elemento;
    }
    
    public Object remove()
    {
        if(isEmpty())
        {
            System.out.println("La cola esta vacia, inserte datos!");
            return "Cola vacia";
        }
        else
            return cola[++frente];
    }
    
    
    public void print()
    {
        if(isEmpty())
            System.out.println("La cola esta vacia!");
        else if(frente == -1)
        {
            for(int i = 0; i <= fin; i++)
            {
                System.out.println(cola[i]);
            }
        }
        else
        {
            for(int j = frente; j <= fin; j++)
            {
                System.out.println(cola[j]);
            }
        }
    }
}

• Principal:

public static void main(String[] args)
    {
        Cola cola = new Cola(4);
        cola.print();
        cola.remove();
        cola.insert("Hola");
        cola.insert(3);
        cola.insert("java");
        cola.insert(5);
        cola.insert(8);
        cola.remove();
        cola.remove();
        cola.remove();
        cola.remove();
        cola.remove();
        
    }
}