Definición de clase
cola y arreglos
class ColaArreglo
{
private Object[] arreglo;
private int primero, ultimo, numElem;
private int MAX_ELEM=100; // maximo numero
de elementos en la cola
public ColaArreglo()
{
arreglo=new Object[MAX_ELEM];
primero=0;
ultimo=MAX_ELEM-1;
numElem=0;
}
public void encolar(Object x)
{
if (numElem<MAX_ELEM) // si esta llena
se produce OVERFLOW
{
ultimo=(ultimo+1)%MAX_ELEM;
arreglo[ultimo]=x;
numElem++;
}
}
public Object sacar()
{
if (!estaVacia()) // si esta vacia se
produce UNDERFLOW
{
Object x=arreglo[primero];
primero=(primero+1)%MAX_ELEM;
numElem--;
return x;
}
}
public boolean estaVacia()
{
return numElem==0;
}
}
Nuevamente en este caso, dependiendo de
la aplicación, se debe definir qué hacer en caso de producirse OVERFLOW o
UNDERFLOW.
Con esta implementación, todas las
operaciones del TDA cola tienen costo O(1).
Una cola de prioridad es un tipo de datos abstracto que almacena un
conjunto de datos que poseen una llave perteneciente a algún conjunto ordenado,
y permite insertar nuevos
elementos y extraer el máximo
(o el mínimo, en caso de que la estructura se organice con un criterio de orden
inverso).
Es frecuente interpretar los valores de
las llaves como prioridades, con lo cual la estructura permite insertar
elementos de prioridad cualquiera, y extraer el de mejor prioridad.
Dos formas simples de implementar colas
de prioridad son: