- Aplicaciones de las
Colas - Representación de las
Colas - Operaciones
- Insertar
Elementos - Eliminación de
elementos - Verificar si la Cola esta
vacía - Aprovechamiento de la
memoria
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".
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.
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.
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 = (cola está
llena)
InsCola (Cola, Nuevo Elemento)
Función: Añade Nuevo Elemento al final de
la Cola
Entrada: Cola, Nuevo Elemento a ser
añadido
Precondiciones: Hay espacio en la Cola
Salida: Cola (cambiada)
Postcondiciones: Cola = Cola original con Nuevo Elemento
añadido al final
SupCola (Cola, ElemSuprimido)
Función: Quita el elemento del frente de la
Cola y devuelve su valor como
ElemSuprimido.
Entrada: Cola
Precondiciones: Cola no esta vacía
Salida: Cola (cambiada)
ElemSuprimido
Postcondiciones: Cola = Cola original con el frente
quitado
ElemSuprimido = elemento frente de la cola
original
Definimos el array.
COLA = COLA(1), COLA(2), …., COLA(n).
n = longitud máxima
f y r = punteros frente y final
x = elementos a insertar
procedimiento inserción
inicio
si r > = n
entonces escribir "desbordamiento de la pila"
sino r r + 1
si r > n
entonces r 1
finsi
COLA(r) x
finsi
{ poner el puntero f al valor 1, a fin de poder hacer
eliminaciones posteriores }
si f = 0
entonces f 1
finsi
fin
El primer elemento introducido Q(n) que es el eliminado,
se almacena en una variable auxiliar x, para eliminar se
tendrá que verificar que la cadena este
vacía.
Procedimiento eliminar
Inicio
{verificar cola vacía}
si f = 0
entonces escribir ‘cola
vacía’
sino x cola (f)
f f + 1
si f > n
entonces f 1
finsi
finsi
{ verificar si la cola se ha quedado vacía y en
ese caso dejar los puntero frontal y final en condiciones
iniciales, cero}
si f = 0 {condición de pila
vacía}
entonces f 0
r 0
finsi
fin
Verificar si la
Cola esta vacía
Una operación muy útil es ver si la cola
está vacía. Cola Vacía (Cola) devuelve True
si la Cola está vacía y False en los demás
casos. Ponemos SupCola cuando la cola no está
vacía. Teóricamente ponemos siempre InsCola, porque
en principio, una cola no tiene un tamaño limitado. Sin
embargo, sabemos de nuestra experiencia con las pilas que ciertas
implementaciones requiere que veamos si la estructura está
llena antes de añadir otro elemento.
Las colas pueden necesitar cantidad de memoria sobre
todo si se diseña con un gran numero de elementos. Para
evitar este desperdicio de memoria, existe un procedimiento
para diseñar las colas mediante una lista
circular.
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
De tal forma que el elemento Q(1), quede a
continuación de Q (n).
Los subalgoritmos (procedimientos)
de inserción y eliminación de una cola circular se
indican a continuación.
Héctor Estigarribia