INTRODUCCIÓN

Una Cola es otro tipo especial de lista en el cual los elementos se insertan por un extremo(el posterior) y se suprimen por el otro(el anterior o frente). Las colas se conocen también como listas FIFO(primero en entrar, primero en salir). Las operaciones para las colas son análogas a las de las pilas. Las diferencias sustanciales consisten en que las inserciones se hacen al final de la lista, y no al principio, y en que la terminología tradicional para colas y listas no es la misma.

Las primitivas que vamos a considerar para el tipo abstracto cola son las siguientes:

· Constructor Primitivo

· Constructor de copia

· Destructor

· Cabecera

· Poner_en_cola

· Quitar_de_cola

· Vacia

IMPLEMENTACIÓN DE LAS COLAS USANDO PRIMITIVAS DE LAS LISTAS

Igual que en el caso de las pilas, cualquier implementación de listas es válida para las colas. No obstante, para aumentar la eficiencia de PONER_EN_COLA es posible aprovechar el hecho de que las inserciones se efectúan sólo en el extremo posterior de forma que en lugar de recorrer la lista de principio a fin cada vez que desea hacer una inserción se puede mantener un apuntador al último elemento. Como en las listas de cualquier clase, también se mantiene un puntero al frente de la lista. En las colas ese puntero es útil para ejecutar mandatos del tipo FRENTE o QUITA_DE_COLA. Utilizaremos al igual que para las listas, una celda cabecera con el puntero frontal apuntándola con lo que nos permitirá un manejo más cómodo. Gráficamente, la estructura de la cola es tal y como muestra la figura:

Una cola es pues un puntero a una estructura compuesta por dos punteros, uno al extremo anterior de la cola y otro al extremo posterior. La primera celda es una celda cabecera cuyo campo elemento se ignora.

ESPECIFICACIÓN SEMÁNTICA Y SINTÁCTICA DE LAS PRIMITIVAS

· Cola() // CONSTRUCTOR PRIMITIVO

Efecto: Crea una cola vacia preparada para ser usada.

· Cola(const Cola<T> & c) // CONSTRUCTOR DE COPIA

Argumento: Una cola c.

Efecto: Crea una cola que es copa de c.

· ~Cola() // DESTRUCTOR
Efecto: Destruye el objeto receptor, Cola, liberando los recursos que empleaba. Para volver a usarlo habrá que crearlo de nuevo. Postcondición: el receptor es modificado.

· T& cabecera ();
Efecto: Acceso al elemento al principio dela cola. Devuelve referencia al elemento en la cabecera de la cola.

· void poner_en_cola (const T & elem);
Argumentos: elem: Elemento que queremos insertar en la cola.

Efecto: Inserta el elemento al final de la cola.

· void quitar_de_cola ()
Precondción: El receptor no puede estar vacío.

Efecto: Suprime el primer elemento(la cabecera) de la cola.

· bool vacia() const;

Efecto: Devuelve true si el receptor, la cola C, es una cola vacía, false en otro caso.

· int num_elementos() const;

Efecto: Devuelve el numero de elementos de recetor, la cola.

FUNCIÓN DE ABSTRACCIÓN

Dado el objeto del tipo rep r, el objeto abstracto al que representa es:

c = l, con la cabecera de la cola en la posición l.primero() y el final en la posición l.final().

Invariante de Representación:

- true

CLASE ABSTRACTA

template <class T>

class Cola {

public:

Cola();

/**

Constructor primitivo.

@doc

Crea una cola vacía. */

Cola(const Cola<T> & c);

/**

Constructor de copia.

@param c: Cola que se copia.

@doc

Crea una cola que es copia de c. */

bool vacia() const;

/**

Informa si la cola está vacía.

@return true, si la cola está vacía.

false, en otro caso. */

T& cabecera ();

/**

Acceso al elemento al principio de la cola.

@return Referencia al elemento en la cabecera de la cola. */

void poner_en_cola(const T & elem);

/**

Añade un elemento en la cola.

@param elem: Elemento que se inserta.

@doc

Inserta un nuevo elemento al final de la cola. */

void quitar_de_cola();

/**

Quita un elemento de la cola.

@precondition El receptor no puede estar vacío.

@doc

Elimina el elemento en la cabecera de la cola. */

int num_elementos() const;

/**

Obtiene el número de elementos en la cola.

@return número de elementos incluidos en la cola. */

~Cola();

/**

Destructor.

@postcondition El receptor es MODIFICADO.

@doc

El receptor es destruido liberando todos los recursos que usaba. */

private:

Lista<T> cola;

};

IMPLEMENTACIÓN

template <class T>

inline Cola<T>::Cola() //constructor primitivo

{};

template <class T>

inline Cola<T>::Cola(const Cola<T> & c) //constructor de copia

: cola(c.cola)

{};

template <class T>

inline bool Cola<T>::vacia() const //detecta si la cola esta vacía

{

return cola.vacia();

}

template <class T>

inline T& Cola<T>::cabecera() //devuelve la cabecera de la cola

{

return cola.elemento(cola.primero());

}

template <class T>

inline void Cola<T>::poner_en_cola(const T & elem) //inserta un elemento al final

{

cola.insertar(cola.final(), elem);

}

template <class T>

inline void Cola<T>::quitar_de_cola() //suprime el primer elemento

{

cola.borrar(cola.primero());

}

template <class T>

inline int Cola<T>::num_elementos() const //devuelve el numero

//de elementos de la cola

{

return cola.num_elementos();

}

template <class T>

inline Cola<T>::~Cola() //destructor

{

}

IMPLEMENTACIÓN DE LAS COLAS USANDO MATRICES CIRCULARES

La implementación matricial de las listas no es muy eficiente para las colas, puesto que si bien con el uso de un apuntador al último elemento es posible ejecutar PONER_EN_COLA en un tiempo constante, QUITAR_DE_COLA, que suprime le primer elemento, requiere que la cola completa ascienda una posición en la matriz con lo que tiene un orden de eficiencia lineal proporcional al tamaño de la cola. Para evitarlo se puede adoptar un criterio diferente. Imaginemos a la matriz como un círculo en el que la primera posición sigue a la última, en la forma en la que se ve en la figura siguiente. La cola se encuentra en alguna parte de ese círculo ocupando posiciones consecutivas. Para insertar un elemento en la cola se mueve el apuntador post una posición en el sentido de las agujas del reloj y se escribe el elemento en esa posición. Para suprimir un elemento simplemente se mueve ant una posición en el sentido de las agujas del reloj. De esta forma, la cola se mueve en ese sentido conforme se insertan y suprimen elementos. Obsérvese que utilizando este modelo los procedimientos PONER_EN_COLA y QUITAR_DE_COLA se pueden implementar de manera que su ejecución se realice en tiempo constante.

Existe un problema que aparece en la representación de la figura anterior y en cualquier variación menor de esta estrategia (p.e. que post apunte a la última posición en el sentido de las agujas del reloj). El problema es que no hay forma de distinguir una cola vacía de una que llene el círculo completo salvo que mantengamos un bit que sea verdad si y solo si la cola está vacía. Si no deseamos mantener este bit debemos prevenir que la cola llene alguna vez la matriz. Para ver por qué puede pasar esto, supongamos que la cola de la figura anterior tuviera MAX_LONG elementos. Entonces, post apuntaría a la posición anterior en el sentido de las agujas del reloj de ant. ¿Qué pasaría si la cola estuviese vacía?. Para ver como se representa una cola vacía, consideramos primero una cola de un elemento. Entonces post y ant apuntarían a la misma posición. Si extraemos un elemento, ant se mueve una posición en el sentido de las agujas del reloj, formando una cola vacía. Por tanto una cola vacía tiene post a una posición de ant en el sentido de las agujas del reloj, que es exactamente la misma posición relativa que cuando la cola tenia MAX_LONG elementos. Por tanto vemos que aún cuando la matriz tenga MAX_LONG casillas, no podemos hacer crecer la cola más allá de MAX_LONG-1 casillas, a menos que introduzcamos un mecanismo para distinguir si la cola está vacía o llena.

ESPECIFICACIÓN SEMANTICA Y SINTACTICA DE LAS PRIMITIVAS USANDO MATRICES CIRCULARES.

· Cola(int LongMax ) // CONSTRUCTOR PRIMITIVO

Argumentos: LongMax tamaño maximo de la cola.

Efecto: Crea una cola con capacidad máxima LongMax (Cambio con respecto a la especificación general).

· Cola(const Cola<T> & c) // CONSTRUCTOR DE COPIA

Argumento: Una cola c que se copia.

Efecto: Crea una cola que es copa de c.

· bool vacia() const;

Efecto: Devuelve true si el receptor, la cola C, es una cola vacía, false en otro caso.

· T& cabecera ();
Efecto: Acceso al elemento al principio dela cola. Devuelve referencia al elemento en la cabecera de la cola.

· void poner_en_cola (const T & elem);
Argumentos: elem: Elemento que queremos insertar en la cola.

Efecto: Inserta el elemento al final de la cola.

· void quitar_de_cola ();
Precondción: El receptor no puede estar vacío.

Efecto: Suprime el primer elemento(la cabecera) de la cola.

· int num_elementos() const;

Efecto: Obtiene el numero de elementos de recetor, la cola.

· ~Cola() // DESTRUCTOR
Efecto: Destruye el objeto receptor, Cola, liberando los recursos que empleaba. Para volver a usarlo habrá que crearlo de nuevo.

Postcondición: el receptor es modificado.

· bool llena() const;

Efecto: Devuelve true si el receptor, la cola C, esta llena y false en otro caso.

Función de Abstracción

Dado el objeto del tipo rep r, r = {elementos, Lmax, ant, post}, el objeto abstracto al que representa es:

Si r.ant == (r.post + 1) % r.Lmax, entonces c = <>

En otro caso:

c = < r.elementos[r.ant],

r.elementos[(r.ant + 1) % r.Lmax],

...,

r.elem[r.post] >

Invariante de Representación

- 0 < r.Lmax

- 0 <= r.ant < r.Lmax

- 0 <= r.post < r.Lmax

- r.post != r.ant

- r.elmentos apunta a una zona de memoria con espacio reservado

para al menos r.Lmax componentes del tipo T

CLASE ABSTRACTA

template <class T>

class Cola {

public:

Cola(int LongMax = 100);

/**

Constructor primitivo.

@param LongMax: Tamaño máximo de la cola.

@doc

Crea una cola vacía con una capacidad máxima de 100.

Importante: ¡¡Cambio con respecto a la especificación general!! */

Cola(const Cola<T> & c);

/**

Constructor de copia.

@param c: Cola que se copia.

@doc

Crea una cola que es copia de c. */

bool vacia() const;

/**

Informa si la cola está vacía.

@return true, si la cola está vacía.

false, en otro caso.*/

T& cabecera ();

/**

Acceso al elemento al principio de la cola.

@return Referencia al elemento en la cabecera de la cola. */

void poner(const T & elem);

/**

Añade un elemento en la cola.

@param elem: Elemento que se inserta.

@doc

Inserta un nuevo elemento al final de la cola. */

void quitar();

/**

Quita un elemento de la cola.

@precondition El receptor no puede estar vacío.

@doc

Elimina el elemento en la cabecera de la cola. */

int num_elementos() const;

/**

Obtiene el número de elementos en la cola.

@return número de elementos incluidos en la cola. */

~Cola();

/**

Destructor.

@postcondition El receptor es MODIFICADO.

@doc

El receptor es destruido liberando todos los recursos que usaba. */

private:

T * elementos;

const int Lmax;

int ant;

int post;

bool llena() const;

/**

Informa si la cola está llena.

@return true, si la cola está llena.

false, en otro caso. */

};

IMPLEMENTACIÓN

template <class T>

inline Cola<T>::Cola(int LongMax):Lmax(LongMax+1) //Constructor primitivo

elementos = new T [LongMax];
  assert(elementos!= 0);

ant = 0;

post = Lmax -1;

};

template <class T>

inline Cola<T>::Cola(const Cola<T> & c) //Constructor de Copia

: Lmax(c.Lmax)

{

ant = c.ant;

post = c.post;

elementos = new T [Lmax];

assert(elementos != 0);

for (int i = ant; i != post; i = (i + 1) % Lmax)

   elementos[i] = c.elementos[i];

elementos [post] = c.elementos[post];

};

template <class T>

inline bool Cola<T>::vacia() const //detecta si la cola esta vacía

{

return ((post + 1) % Lmax) == ant;

}

template <class T>

inline bool Cola<T>::llena() const //detecta si la cola esta llena

{

return ((post + 2) % Lmax) == ant;

}

template <class T>

inline T& Cola<T>::cabecera() //devuelve la cabecera de la cola

{

return elementos[ant];

}

template <class T>

inline void Cola<T>::poner_en_cola(const T & elem) //inserta un elemento al final

{

assert(!llena());

post = (post + 1) % Lmax;

elementos[post] = elem;

}

template <class T>

inline void Cola<T>::quitar_de_cola() //suprime el primer elemento

{

assert(!vacia());

ant = (ant + 1 ) % Lmax;

}

template <class T>

inline int Cola<T>::num_elementos() const //devuelve el numero de elementos

{

if (vacia())

return 0;

if (post > ant)

return post - ant + 1;

else

return (Lmax - ant + 1) + (post + 1);

}

template <class T>

inline Cola<T>::~Cola() //destructor

{

delete [] elementos;

}

EJEMPLOS

Vamos a definir la clase Persona que se usarán durante la implementación de la clase Cola. La clase Persona utiliza a su vez la clase Fecha y la clase Cadena.

CLASE PERSONA

CONSTRUCTOR CON PARÁMETROS (Clase Persona)

CLASE COLA

CONSTRUCTOR POR DEFECTO (Clase Cola)

CONSTRUCTOR CON PARÁMETROS (Clase Cola)

CONSTRUCTOR COPIA

QUITAR_DE_COLA

fifo.primero( );

fifo.borrar( );

assert (!esVacia( ));

CABEZA

COLAS DE PRIORIDAD

Una cola de prioridad es una estructura de datos que se utiliza en determinados problemas es los que de forma continua es necesario buscar y suprimir el menor elemento de una colección de valores. Por ejemplo, problemas en los que se mantiene una lista de tareas organizada por prioridades (sistemas operativos, procesos de simulación, etc.).

Se requiere que los elementos de la colección se puedan ordenar mediante algún criterio (su prioridad), aunque no es necesario que los elementos pertenezcan a una colección ordenada. Para determinar la prioridad de los elementos se establecerá una función, la función de prioridad.

CLASE ABSTRACTA

template <class T>

class priorityQueue {

public:

// constructores

priorityQueue (unsigned int (*f) (const T &));

/* Necesita: la dirección de la función de prioridad. */

priorityQueue (const priorityQueue<T> & source);

virtual void add (const T & value) = 0;

/* Necesita: un valor de tipo T.

Modifica: la cola receptora añadiendo el valor dado.

La posición de inserción depende de la

prioridad del valor proporcionado. */

T deleteMin ();

/* Produce: el elemento de la cola con menor prioridad.

Modifica: la cola receptora eliminando el elemento de

menor prioridad. */

virtual bool isEmpty () const = 0;

/* Produce: cierto si la cola receptora es vacía.

Coste t.: O(1) */

virtual T min () const = 0;

/* Produce: el elemento de la cola receptora con

menor prioridad.

Coste t.: O(1) */

virtual void removeMin () = 0;

/* Modifica: la cola receptora eliminando el elemento

de menor prioridad. */

protected:

// área de datos

unsigned int (*prFunction) (const T &);

// operación interna

unsigned int priority (const T & value);

/* Necesita: un valor de tipo T.

Produce: la prioridad del valor dado. */

};

template <class T>

priorityQueue<T>::priorityQueue (unsigned int (*f) (const T &))

: prFunction(f)

{}

template <class T>

T priorityQueue<T>::deleteMin ()

{

T result = min();

removeMin();

return result;

}

template <class T>

unsigned int priorityQueue<T>::priority (const T & value)

{

return (*prFunction) (value);

}

POSIBLES REPRESENTACIONES

MEDIANTE LISTAS ORDENADAS

Está representación tiene el inconveniente de que la inserción de un elemento es una operación de O(n), aunque la obtención y supresión del menor elemento se realiza en tiempo constante.

MEDIANTE ÁRBOLES AVL

En este caso todas las operaciones serían de O(log n). Sin embargo, ésta no es la forma usual de representar colas de prioridad por medio de árboles. La razón es que hay una forma más simple de hacerlo con el mismo coste asintótico: representarlas mediante

árboles parcialmente ordenados.

CON ÁRBOLES PARCIALMENTE ORDENADOS

Un árbol parcialmente ordenado es un árbol binario completo en el que el valor (o etiqueta) de cada nodo es menor o igual que el de cada uno de sus hijos. En nuestro caso, la comparación de los valores de los nodos se establece con respecto a la prioridad.

Dado que el árbol parcialmente ordenado es un árbol binario completo, éste se puede representar de forma eficiente mediante un vector.

Aunque en este caso las operaciones de la cola de prioridad también son de O(log n), la sencillez de la representación de los árboles parcialmente ordenados y el ahorro de la operación de equilibrado, hacen que en la práctica ésta sea la forma más eficiente de representar colas de prioridad.

REPRESENTACIÓN MEDIANTE LISTAS ORDENADAS

template <class T>

class priorityQueueList : public priorityQueue<T> {

friend bool operator < (const T & left, const T & right);

friend bool operator <= (const T & left, const T & right);

friend bool operator > (const T & left, const T & right);

friend bool operator >= (const T & left, const T & right);

friend bool operator == (const T & left, const T & right);

friend bool operator != (const T & left, const T & right);

public:

// constructores

priorityQueueList (unsigned int (*f) (const T &));

priorityQueueList (const priorityQueueList<T> & source);

// operaciones para colas de prioridad

virtual void add (const T & value);

/* Coste t.: O(n) */

virtual bool isEmpty () const;

virtual T min () const;

virtual void removeMin ();

/* Coste t.: O(1) */

virtual void deleteAllValues ();

/* Modifica: la cola receptora haciéndola vacía.

Coste t.: O(n). */

// asignación

priorityQueueList<T> & operator =

(const priorityQueueList<T> & source);

protected:

// área de datos

orderedList<T> lst;

};

template <class T>

priorityQueueList<T>::priorityQueueList

(unsigned int (*f) (const T &)) : lst(), priorityQueue<T>(f)

{}

template <class T>

void priorityQueueList<T>::add (const T & value)

{

lst.add(value);

}

template <class T>

T priorityQueueList<T>::min () const

{

return lst.firstElement();

}

template <class T>

bool operator < (const T & left, const T & right)

{

return priority(left) < priority(right);

}

REPRESENTACIÓN MEDIANTE ÁRBOLES

template <class T>

class heap : public priorityQueue<T> {

public:

// constructores

heap (unsigned int maxsize, unsigned int (*f) (const T &));

heap (const heap<T> & source);

// operaciones para colas de prioridad

virtual void add (const T & value);

/* Coste t.: O(log n) */

virtual bool isEmpty () const;

virtual T min () const;

virtual void removeMin ();

/* Coste t.: O(log n) */

virtual void deleteAllValues ();

/* Modifica: la cola receptora haciéndola vacía.

Coste t.: O(n). */

// asignación

heap<T> & operator = (const heap<T> & source);

protected:

// área de datos

vector<T> data;

unsigned int heapsize; // número de elementos

unsigned int heapmax; // espacio reservado para elementos

};

Para codificar las operaciones, debemos recordar como se representaba un árbol binario mediante un vector: los nodos del árbol se enumeraban de la forma siguiente:

A la raíz le corresponde el índice 0.

Si a un nodo le corresponde el índice k, a sus hijos izquierdo y derecho, si los tiene, les corresponden los índices 2*(k+1)-1 y 2*(k+1), respectivamente.

OPERACIÓN DE INSERCIÓN (add)

El nuevo elemento se inserta en el último nivel, lo más a la izquierda posible. Posteriormente se desplaza hacia arriba en el árbol hasta que se sitúa en la posición que le corresponde de acuerdo a su prioridad.

El elemento insertado, x, se desplaza hacia arriba intercambiándolo con su padre hasta que prioridad(padre_de_x) <= prioridad(x) o hasta que se alcanza la raíz del árbol.

template <class T>

void heap<T>::add (const T & value)

{

// si es necesario aumentar el espacio

if (heapsize + 1 >= heapmax) {

data.setSize(data.length() + 5);

heapmax += 5;

}

// posición inicial de inserción heapsize

unsigned int position = heapsize++;

// invariante: (position <= 0) (position < heapmax)

// buscar la posición de inserción

while (position > 0 &&

priority(value) < priority(data[(position-1)/2])) {

data[position] = data[(position-1)/2];

position = (position - 1) / 2; // ir al padre

}

// insertar el nuevo elemento

data[position] = value;

}

OPERACIÓN DE BORRADO (removeMin)

Para borrar el mínimo, que está situado en la raíz del árbol, se pasa el último elemento de la cola a la raíz. De esta forma se conserva la estructura de árbol binario completo.

Posteriormente, se desplaza la raíz hacia abajo hasta que se sitúa en el lugar que le corresponde de acuerdo a su prioridad.

El elemento de la raíz se desplaza hacia abajo, intercambiándolo con el hijo de menor prioridad, hasta que ambos hijos tengan mayor o igual prioridad o se llegue a una hoja.

template <class T> void heap<T>::removeMin () {

unsigned int position = 0; // posición inicial la de la

// raíz, 0

heapsize--;

while (position < heapsize) { // bajar hasta el lugar

// adecuado

// poner en la posicion el menor de sus hijo

unsigned int childpos = 2 * position + 1; // hijo

// izquierdo

if (childpos < heapsize) {

if ((childpos + 1 < heapsize) &&

priority(data[childpos+1]) < priority(data[childpos]))

childpos++; // hijo derecho

if (priority(data[heapsize]) <

priority(data[childpos])) {

// encontramos la posición buscada

data[position] = data[heapsize];

return;

}

// subir el hijo a la posición actual

data[position] = data[childpos];

position = childpos;

}

else { // se ha alcanzado una hoja

data[position] = data[heapsize];

return;

}

}

// la posición buscada es la de la raíz

data[position] = data[heapsize];

}