Teoria De Colas

olas: 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".

La diferencia con las pilas es en el modo de entrada / salida de datos; en las colas se realizan las inserciones al final de la lista, no al principio.

Por eso, se usan para almacenar datos que necesitan ser procesados según el orden de llegada.

C= C (1), C(2), ......., C(N)

Las eliminaciones se realizan al principio de la lista frente (front), y las inserciones se realizan en el otro extremo final (rear).

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Aplicaciones de las Colas

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).

Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".

Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

Representación de las Colas

Se las puede representar por listas enlazadas o por arrays

C= Q(1), Q(2)......., Q(n).

En cualquier caso se necesitan dos punteros

frente (f)

final (r)

y la lista o array de n elementos (LONGMAX)

parte no utilizada de la lista Cola parte no utilizada de la lista

Para ver el gráfico seleccione la opción "Descargar" del menú superior

Representación de una Cola, mediante un array.

100

264

119

48

frente final

Representación de una Cola mediante una lista enlazada

1 2 3 4

100

264

119

48

frente final

Las operaciones que se pueden realizar con una cola son:

Acceder al primer elemento de la Cola

Añadir un elemento al final de la Cola

Eliminar el primer elemento de la Cola

Vaciar una Cola

Verificar el estado de la Cola: vacía, Llena.

Operaciones:

LimpiarPila (Cola)

Función: Inicializa Cola al estado vacío

Entrada: Cola a inicializar

Precondiciones: Ninguna

Salida: Cola (inicializada)

Postcondiciones: Cola está vacía

ColaVacía (Cola)

Función: Indica si la Cola esta vacía

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola Vacía (indicador Booleano)

Postcondiciones: ColaVacía= (cola está vacía)

ColaLlena (Cola)

Función: Indica si esta llena

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola llena (indicador Booleano)

Postcondiciones: ColaLlena

...