Códigos Colas

Cola de Prioridad

Una cola de prioridades es un tipo de dato abstracto similar a una cola en la que los elementos tienen adicionalmente, una prioridad asignada. En una cola de prioridades un elemento con mayor prioridad será desencolado antes que un elemento de menor prioridad. Si dos elementos tienen la misma prioridad, se desencolarán siguiendo el orden de cola.

Una cola de prioridad ha de soportar al menos las siguientes dos operaciones:

• Añadir con prioridad: se añade un elemento a la cola, con su correspondiente prioridad.
• Eliminar elemento de mayor prioridad: se devuelve y elimina el elemento con mayor prioridad más antiguo que no haya sido desencolado de la cola.

Además suele implementarse una función frente(que habitualmente aquí se denomina encontrar-máximo o encontrar-mínimo). Esta operación y su rendimiento en tiempo es crucial en ciertas aplicaciones de las colas de prioridades.

Ciertas implementaciones avanzadas pueden incluir operaciones más complejas para la inspección de los elementos de mayor o menor prioridad, borrar la cola o ciertos subconjuntos de la cola, realizar inserciones en masa, la fusión de dos colas en una, aumentar la prioridad de los elementos, etc.

Ejemplo:

import java.util.Scanner;
 
package colaPrioridadSimpleEnlazada;
import colaException.*;

public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
    class Celda {
        T elemento;
        int prioridad;
        Celda sig;
    }
    private Celda cola;
    public ColaPrioridad() {
        cola = new Celda();
        cola.sig = null;
    }
    public boolean vacia() {
        return (cola.sig==null);
    } 
    public  primero() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        return cola.sig.elemento;
    }
    public int primero_prioridad() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        return cola.sig.prioridad;
    }      
    public void inserta(T elemento, int prioridad) {
        Celda p,q;
        boolean encontrado = false;
        p = cola;
        while((p.sig!=null)&&(!encontrado)) {
            if (p.sig.prioridad