Colas

Solo disponible en BuenasTareas
  • Páginas : 8 (1884 palabras )
  • Descarga(s) : 0
  • Publicado : 27 de noviembre de 2010
Leer documento completo
Vista previa del texto
Colas
Es otro tipo especial de las listas, en el cual los elementos se insertan en un extremo (posterior) y se suprime en el otro (anterior o frente). Las colas también se les conocen como listas FIFO (first-in first-out) (primero en entrar – primero en salir)
Operaciones
* ANULA: Convierte la cola C en una lista vacía.
* FRENTE: Es una función que devuelve el valor del primerelemento de la cola C.PONE_EN_COLA(x,C): Insertar el elemento x al final de la cola C.
* QUITA_EN_COLA: Suprime el primer elemento de C.
* VACIA: Devuelve verdadero si, y sólo si, C es una cola vacía.
Por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro.

Tipos de colas:
* Colas de prioridad: Enellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.
* Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un arraycircular con Ini y Fin que apunten a cada uno de los extremos.
-Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al principio ó al final.
-Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al principio y al final.
Colas de prioridad: son aquellas que cumplen dos reglas:
1. Dedos elementos siempre se atenderá antes al que tenga mayor prioridad.
2. Si dos elementos tienen la misma prioridad se atiende primero el que llego antes.

Las operaciones básicas de una cola son “enqueue” (meter) y “dequeue” (sacar)
* enqueue: añade un nuevo elemento a final de la cola
* dequeue: elimina (saca) el primer elemento de la cola
Otras operaciones usualmenteincluidas en el tipo abstracto COLA son:
* isEmpty (estáVacia): verifica si la cola está vacía
* isFull (estáLlena): verifica si la cola está llena

Realización de colas basadas en apuntadores.
Se mantiene un apuntador (o un cursor) al último elemento y e mantiene un apuntador al frente.
En Pascal: se utiliza una celda ficticia como encabezamiento y se tendrá el apuntador frontaldirigido a ella. Permite manejar convenientemente una cola vacía.
Representación de la cola

Realización de colas con arreglos circulares.
El objetivo de una cola circular es aprovechar al máximo el espacio del arreglo. La idea es insertar elementos en las localidades previamente desocupadas. La implementación tradicional considera dejar un espacio entre el frente y la cola.

Hay muchos lugaresen donde se pueden ver las aplicaciones de una cola, la fila de un supermercado, la cola de autos formarse en la caseta, etc. Todos ellos representan una cola que se representa en diferentes situaciones.

Colas: Es una estructura lineal de datos. Una cola es un grupoordenado 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 pilases 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 serprocesados 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...
tracking img