3. Colas

3.1 Introducción

Colas: Es una estructura lineal de datos. Una cola es un grupo ordenado de elementos homogéneos en el que los nuevos elementos se añaden por un extremo (el final) y se quitan por el otro extremo (el frente). En las colas el elemento que entró primero sale también primero, por ello se las llama como listas FIFO (first – in, first – out) "primero en entrar, primero en salir".

3.2 Colas dobles

La bi-cola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.

Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.

En este caso, se puede añadir o extraer elementos por cualquier extremo. Ver figura 6.8. Puede implementarse en un arreglo como cola circular. En este caso se cumpliría que Bicola[Der] va detrás de Bicola[Izq].

3.3 Una cola de prioridad: el montículo binario

Presentes en multitud de situaciones: Colas de impresión, servicios de urgencias de un hospital, para las tortillas etc…

Optimización de dos operaciones:

•  Insertar el elemento M con prioridad P

•  Sacar el elemento M (teniendo ese elemento la máxima prioridad)

Otra operación importante es:

•  Buscar elemento M

 

3.3.1 Propiedad estructural

3.3.2 Propiedad de ordenación de los montículos

3.3.3 Operaciones permitidas

Las operaciones de las colas de prioridad son las mismas que las de las colas genéricas:

• Crear: se crea la cola vacía.
• Encolar: se añade un elemento a la cola, con su correspondiente prioridad.
• Desencolar: se elimina el elemento frontal de la cola.
• Frente: se devuelve el elemento frontal de la cola.
• Destruye: elimina la cola de memoria.

Operación de Insertar  Situar el elemento a insertar en la última posición disponible del vector (garantizamos el árbol completo. Comparar el elemento insertado con su padre             Padre en (i-1)/2, siendo i la posición del nodo insertado. Si la clave a insertar es mayor que su padre, proceso termina. Si la clave es menor:           Se intercambia con su padre.              Se repite el proceso hasta que el padre sea menor o haya alcanzado la raiz.           Este proceso se denomina criba o filtrado ascendente. 3.4. Colas de prioridad con mezcla

Existen dos tipos de mezcla de colas, la mezcla multiaria y la mezcla multifase. En la siguiente entrada se definirán los dos.

Mezcla multiaria.

En este caso mezclar dos colas requiere de recorrer cada cinta de entrada hasta el principio de las colas a mezclar. Entonces se toma el elemento más pequeño de los dos (aquellos sobre los que nos encontramos en cada una de las cintas) y se coloca en una cinta de salida avanzando la correspondiente cinta de entrada. Si hubiese N cintas de entrada la estrategia funciona de la misma manera la única diferencia radica en que es ligeramente más complicado encontrar el elemento más  pequeño entre N colas pero para facilitar este proceso se utiliza una cola de prioridad para escribir el siguiente elemento a escribir en la cinta de salida utilizando la operación “eliminarMin” se repite ese procedimiento para seguir encontrando los siguientes elementos a ingresar en la cinta de salida.

Mezcla Multifase

La estrategia de la mezcla multiaria desarrollada anteriormente requiere el uso de 2N (numero par de cintas) cintas. Esto podría ser prohibitivo  en algunas aplicaciones. Es posible solo hacerlo con N+1 cintas, a esto se le llama mezcla multifase un ejemplo de ello sería utilizar una mezcla multiaria usando solamente tres cintas.

3.5 Ejemplos