3.2 COLAS

3.2.1 Definición de una Cola.

Una cola constituye una estructura lineal de datos en la que los nuevos elementos se introducen por un extremo y los ya existentes se eliminan por el otro. Es importante señalar que los componentes de la cola se eliminan en el mismo orden en el cual se insertaron. Es decir, el primer elemento que se introduce en la estructura será el que se eliminara en primer orden. Debido a esta característica, las colas también reciben el nombre de estructuras FIFO (First-In, First-Out: el primero en entrar es el primero en salir).

3.2.2 Representación de Colas.

Las colas, al igual que las pilas, no existen como estructuras de datos estándar en lenguajes de programación. Este tipo de estructura de datos se puede representar mediante el uso de:

·         Arreglos

·         Listas

Cuando se implementan con arreglos unidimensionales, es importante definir tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que almacene la posición del primer elemento de la cola  FRENTE y otra para que gua la posición del último elemento de la cola FINAL.

En las figuras 3.3a y 3.3b, podemos observar que por el frente siempre eliminaremos, ya sea este al lado izquierdo o derecho e igual siempre añadiremos por el lado del final.

Fig. 3.3a

  

Fig. 3.3b

3.2.3 Operaciones con colas.

La definición de la estructura de datos tipo cola queda completa al incluir las operaciones que se pueden realizar en ella. Las operaciones básicas que pueden efectuarse son:

·         Insertar un elemento en la cola

·         Eliminar un elemento de la cola

Y también existen operaciones auxiliares para las colas, la cuales son:

·         Cola llena

·         Cola vacía
 

3.2.3.1 Cola vacía.

Este algoritmo determina si una estructura de datos tipo cola está vacía, asignando a BAN. el valor de verdad correspondiente.

Si (FRENTE = 0)
        entonces
              Hacer BAND  VERDADERO
        si no
              Hacer BAND  FALSO
Fin si

3.2.3.2 Cola Llena.

Este algoritmo determina si una estructura de datos tipo cola está llena, asignando a BAND el valor de verdad correspondiente. MAX es el número máximo de elementos que puede almacenar COLA.

Si (FINAL = MAX)
        entonces
              Hacer BAND  VERDADERO
        si no
              Hacer BAND FALSO

Fin Si

3.2.3.3 Insertar Cola.

Este algoritmo inserta el elemento DATO al final de una estructura tipo cola. FRENTE y FINAL son los punteros que indican, respectivamente, el inicio y fin de COLA. La primera vez FRENTE y FINAL tienen el valor  0, ya que la cola está vacía. MAX es el máximo número de elementos que puede almacenar la cola.

Si (FINAL < MAX) Verifica que hay espacio libre
           entonces
                      Hacer FINAL <- FINAL + 1 Actualiza FINAL} y COLA[FINAL] DATO
                      Si (FINAL = 1)  entonces Se insertó el primer elemento de COLA
                                 Hacer FRENTE <- 1
                       Fin Si
             si no
                      Escribir "Desbordamiento  Cola llena"

Fin Si

3.2.3.4 Eliminar Cola.

Este algoritmo elimina el primer elemento de una estructura tipo cola y lo almacena en DATO. FRENTE y FINAL son los punteros que indican, respectivamente, el inicio y fin de la cola

Si (FRENTE ≠ 0) Verifica que la cola no este vacía
     entonces
             Hacer DATO  COLA [FRENTE]
              Si (FRENTE = FINAL) {Si hay un solo elemento}
                            entonces
                                   Hacer FRENTE  0 y FINAL  0 Indica COLA vacía                 
                            si no
                                   Hacer FRENTE FRENTE + 1

        Fin si

     Si no
             Escribir "Subdesbordamiento Cola vacía"

Fin Si

 
Video-Ejemplo de Colas en Java:

 Baja mas información en:

https://dl.dropbox.com/u/90414787/Metodos_de_Progra_I/2-sld-colas_es.pdf