COLAS

 

Colas. Fundamentos

   Las colas son secuencias de elementos caracterizadas porque las operaciones de inserción y borrado se realizan sobre extremos opuestos de la secuencia. La inserción se produce en el "final" de la secuencia, mientras que el borrado se realiza en el otro extremo, el "inicio" de la secuencia.

   Las restricciones definidas para una cola hacen que el primer elemento que se inserta en ella sea, igualmente, el primero en ser extraído de la estructura. Si una serie de elementos A, B, C, D, E se insertan en una cola en ese mismo orden, entonces los elementos irán saliendo de la cola en el orden en que entraron. Por esa razón, en ocasiones, las colas se conocen con el nombre de listas FIFO (First In First Out, el primero que entra es el primero que sale).

   Las colas, al igual que las pilas, resultan de aplicación habitual en muchos problemas informáticos. Quizás la aplicación más común de las colas es la organización de tareas de un ordenador. En general, los trabajos enviados a un ordenador son "encolados" por éste, para ir procesando secuencialmente todos los trabajos en el mismo orden en que se reciben. Cuando el ordenador recibe el encargo de realizar una tarea, ésta es almacenada al final de la cola de trabajos. En el momento que la tarea que estaba realizando el procesador acaba, éste selecciona la tarea situada al principio de la cola para ser ejecutada a continuación. Todo esto suponiendo la ausencia de prioridades en los trabajos. En caso contrario, existirá una cola para cada prioridad. Del mismo modo, es necesaria una cola, por ejemplo, a la hora de gestionar eficientemente los trabajos que deben ser enviados a una impresora (o a casi cualquier dispositivo conectado a un ordenador). De esta manera, el ordenador controla el envio de trabajos al dispositivo, no enviando un trabajo hasta que la impresora no termine con el anterior.

   Análogamente a las pilas, es necesario definir el conjunto de operaciones básicas para especificar adecuadamente una estructura cola. Estas operaciones serían:

  • Crear una cola vacía.
  • Determinar si la cola está vacía, en cuyo caso no es posible eliminar elementos.
  • Acceder al elemento inicial de la cola.
  • Insertar elementos al final de la cola.
  • Eliminar elementos al inicio de la cola.

   Para determinar correctamente cada una de estas operaciones, es necesario especificar un tipo de representación para las colas.

Representacion de las colas

   La representación de una cola finita en forma de vector es una tarea algo más compleja que la realizada para el caso de las pilas. Además de un array unidimensional, son necesarias un par de variables que indiquen dónde está el inicio de la cola y dónde el final.

   Hay diferentes formas de implementar las operaciones relacionadas con colas pero una de las más eficientes es representar el array Cola[1..n] como si fuese circular, es decir, cuando se dé la condición de cola llena se podrá continuar por el principio de la misma si esas posiciones no están ocupadas.

   Con este esquema de representación, se puede pasar a especificar el conjunto de operaciones necesarias para definir una cola circular.

Crear cola:

   Esta operación consistirá en definir la variable de tipo array que permitirá almacenar la información y las variables que apuntarán a los extremos de la estructura. Además, hay que indicar explícitamente que la cola, trás la creación, está vacía.

(1) Declaraciones: 

   Cola : array [1..n] de T 
   inicio, fin: 1..n 
 
(2)Cola vacía:
 
   inicio <-- 1
   fin    <-- 1

Comprobar si la cola está vacía:

Con las condiciones establecidas, basta comprobar si inicio = fin:

 

 si Cola.inicio = Cola.fin entonces devolver(cierto)
 sino devolver(falso)

Función siguiente:

   Con esta función obtenemos el índice del siguiente elemento a i, se trata de calcular el resto de ese i entre el máximo índice de la cola, algo así: (Siguiente := i MOD n + 1).

   Todo esto es necesario porque como hemos dicho antes Cola.inicio y Cola.fin son 1 cuando la Cola está vacia, por tanto el primer elemento nunca estará en el valor de Cola.inicio sino en el de Siguiente(Cola.inicio).

Acceder al elemento inicial de la cola:

Es importante poder acceder fácilmente al inicio de la cola; para ello se puede crear una función para tal propósito.

 

 si Vacia(Cola) entonces "Error. Cola vacía."
 sino devolver (Cola.info[Siguiente(Cola.inicio)])

Insertar un elemento en la cola:

   Debido a la implementación estática de la estructura cola es necesario determinar si existen huecos libres donde poder insertar antes de hacerlo. Esto puede hacerse de varias formas:

 

 
si Cola.inicio = Siguiente(Cola.fin) entonces "Error. Cola llena."
sino
   incrementar(Cola.fin)
   Cola.info[Cola.fin] <-- x
fin_sino

O incrementando antes y luego comparando que 'Cola.inicio' sea igual a 'Cola.fin'.

Eliminar un elemento de la cola:

   Como podeis ver la eliminación no borra nada 'físicamente', sólo se encarga de actualizar el puntero 'Cola.inicio' en una posición y devolver el valor x como mucho, aunque esto último no sea estrictamente necesario. Aunque esa posición aun contenga datos será considerada como vacía a efectos del otro puntero 'Cola.final'.

 

 
si Vacia(Cola) entonces "Error. Cola vacía."
sino 
   x <-- Primero(Cola)
   incrementar(Cola.inicio)
   devolver(x)
fin_sino

Dicolas

Las Dicolas son casos particulares de listas y generalizaciones de colas en donde las eliminaciones e inserciones pueden realizarse en ambos extremos de la lista.
 
El conjunto de operaciones de una dicola consiste en las operaciones de una cola junto con las siguientes:
 
 public Object ultimo() throws ColaVaciaException;
 public void inserta_frente(Object elemento);
 public void suprime_post() throws ColaVaciaException;

COLAS DE PRIORIDAD

Una cola de prioridad es una cola a cuyos elementos se les
ha  asignado  una prioridad, de forma que el orden  en  que  los
elementos son procesados sigue las siguientes reglas:
   
oEl elemento con mayor prioridad es procesado primero.
oDos  elementos  con la misma prioridad  son  procesados según el orden en que fueron introducidos en la cola.
Existen  dos  métodos básicos para la representación de colas de prioridad mediante estructuras lineales:
a)Tener la cola siempre ordenada de acuerdo a las prioridades  de  sus  elementos, y  sacar  cada  vez  el  primer elemento de ésta, es decir, el de mayor prioridad. En este caso, cuando  se introduce un elemento en la cola, debe insertarse  en el lugar correspondiente de acuerdo a su prioridad.
b)Insertar los  elementos  siempre al final de la cola, y cuando  se  va  a sacar un elemento, buscar el que tiene mayor prioridad.
Nosotros  usaremos el método (a), ya que la búsqueda  de  la posición  en  la  cual  se inserta un elemento  nuevo  requiere menos operaciones  que la búsqueda del elemento que se saca para  el  caso (b).
Ya que los elementos se insertarán en cualquier posición de la cola, la representación con simple enlace es la más apropiada.
Una implementación en Java de la Cola de Prioridad mediante
simple enlace puede realizarse de la siguiente forma:
 
 
package colaPrioridadSimpleEnlazada;
import colaException.*;
 
public class ColaPrioridad implements colaPrioridadInterface.ColaPrioridad {
    class Celda {
        Object elemento;
        int prioridad;
        Celda sig;
    }
    private Celda cola;
    public ColaPrioridad() {
        cola = new Celda();
        cola.sig = null;
    }
public boolean vacia() {
        return (cola.sig==null);
    }
    public Object 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 int primero_prioridad() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        return cola.sig.prioridad;
    }     
public void inserta(Object elemento, int prioridad) {
        Celda p,q;
        boolean encontrado = false;
        p = cola;
        while((p.sig!=null)&&(!encontrado)) {
            if (p.sig.prioridad<prioridad)
                encontrado = true;
            else p = p.sig;
        }
        q = p.sig;
        p.sig = new Celda();
        p = p.sig;
        p.elemento = elemento;
        p.prioridad = prioridad;
        p.sig = q;
    }    
        public void suprime() throws ColaVaciaException {
        if (vacia()) throw new ColaVaciaException();
        cola = cola.sig;
    }
} // fin clase ColaPrioridad

Conclusión

   De todo esto puede sorprender que la condición de cola llena sea la misma que la de cola vacía. Sin embargo, en el caso de la inserción de elementos cuando Cola.inicio = Cola.fin es cierto, no es verdad que la cola esté llena, en realidad hay un espacio libre, ya que Cola.inicio apunta a una posición libre, la anterior al primer elemento real de la cola. Pero si se decide insertar un elemento en esa posición, no sería posible distinguir si Cola.inicio = Cola.fin indica que la cola está llena o vacía. Se podría definir alguna variable lógica que indicase cual de las dos situaciones se está dando en realidad. Esta modificación implicaría introducir alguna nueva operación en los métodos de inserción y borrado, lo que, en general, resultaría peor solución que no utilizar un elemento del array. Suele ser mejor solución utilizar siempre 'n-1' elementos de la cola, y no 'n', que complicar dos operaciones que se tendrán que repetir múltiples veces durante la ejecución de un programa.

 

 

                                                        

 

 

 
Hosted by www.Geocities.ws

1