Tad Colas

TAD COLA

FACILTADORA: Ingeniera deSistemas Zamantha González MISION SUCRE

•Yulisbeth Diaz

•Yamiret Padilla

•Dionicio Gimenez

•Enrique Henriquez

•Maria Rodriguez

•Antonio Sevilla

Tipo de Dato Abstracto

Un Tipo de Dato Abstracto (TDA) o Abstract Data Types (TAD)se define como un modelo matemático con un conjunto deoperaciones que se definen sobre este modelo.

Define un tipo de dato e incluye la descripción de todo elcomportamiento asociado al dato.

No está asociado a ninguna implementación.

El implementar un TAD supone la traducción de lasespecificaciones del TAD en las sintaxis de un lenguaje deprogramación en particular.

FACILTADORA: Ingeniera De Sistemas Zamantha González MISION SUCRE

Conceptos Básicos del TAD Cola

“Una Cola es un contenedor de objetos que son insertados y eliminados de acuerdo con el principio de que el primero en entrar es el primero en salir (FIFO-First In First Out)”.

“Una Cola es un caso particular de lista en el cual loselementos se insertan en un extremo (el posterior o final) y se suprimen en el otro (el anterior o frente)”.

Las Colas se conocen también Como Listas FIFO ( first-infirst-out) o listas ``primero en entrar, primero en salir''.

Un ejemplo de cola es la Cola de impresión en el sistema operativo Windows. Cada usuario de una red de Windows coloca sus trabajos de impresión y el sistema lo imprime en el mismo orden en que fueron insertados en la cola de impresión


Ejemplos Cotidianos de Colas


Conceptos Básicos del TAD Cola

La estructura cola se puede describir de forma intuitiva con ejemplos de la vida cotidiana. Por ejemplo, las personas esperando para usar un cajero automático: cuando llega alguien que quiere usar el cajero debe colocarse detrás del último, y la primera persona de la cola será la primera que use el cajero.

Tambien se pueden ejemplificar el S.O. en el Tiempo com-partido en el cada usuario va esperando su turno igual que en el multiproceso.

0 1 2 3 4

A B C D E FINALFRENTE


Especificación formal del TAD Cola

La estructura Cola se especifica formalmente por ser una Lista ordenada en la cual las Elimnaciones se realizan en un solo extremo; llamado FRENTE o PRINCIPIO de la Cola y los nuevos elementos se Añaden por el otro extremo lamado FONDO o FINAL de la Cola .

Existen Operaciones que definen las especificacion Formal del TAD Cola, entre ellas tenemos:

ColaCrear

ColaInsertar

ColaExtraer

ColaHayElementos

ColaEliminar

ColaLlena

ColaVacia


Especificación formal del TAD ColaEspecificación Formal

Tipo: Cola (Elemento)

Sintaxis:

crea Cola

inserta(Cola,Elemento) Cola

vacia(Cola) booleano

primero(Cola) Elemento

suprime(Cola) Cola

Semántica:

vacia(crea) cierto

vacia(inserta(C,E)) falso

primero(crea) error

primero(inserta(C,E)) si vacia(C) E |primero(C)

suprime(crea) error

suprime(inserta(C,E)) si vacia(C)crea|inserta(suprime(C),E)


Especificación formal del TAD Cola

A B C D FINALFRENTE

B C D E FINALFRENTE

B C D E FINALFRENTE

Estructura Original

…despues de ELIMINAR un elemento

…despues de INSERTAR un elemento

Implementaciones en Colas

•En esta sección mostraremos tres implementaciones para

el TDA Cola:

•Implementación basada en el TAD Arreglos.

•Implementación basada en el TAD Lista Secuencial.

•Implementación con Listas Enlazadas y Doblemente

Enlazadas.

•Implementación con Lista Circular Enlazada y

Doblemente Enlazadas.


Implementación de Cola con Lista Secuencial

•No hay correspondencia entre la posición del último

nodo y la cantidad de nodos de la cola.

•La condición de cola llena y de cola vacía, no se pueden

verificar haciendo uso del índice del arreglo.

•En el caso del método secuencial se usa una asignación

de memoria contigua y fija de antemano. Si esto no es lo

indicado para la aplicación, se recomienda utilizar el

método enlazado.

Implementación de Cola con Lista Secuencial

La Cola lineal o Vectorial es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica FIFO (primero en entrar primero en salir). Las colas lineales se representan gráficamente de la siguiente manera:

Implementación con Vectores

1 2 3 4 … N

A B C D

Frente Final

…

Máximo

Implementación de Cola con Lista Enlazada

En una lista enlazada se asigna memoria para elalmacenar los elementos de la lista conforme se vanecesitando, es decir a medida que se añaden oinsertan los elementos, y se conectan los elementosde la lista con punteros.

La memoria es liberada cuando ya no se necesitamás un elemento en la lista.

Esquemáticamente una lista enlazada se representapor una secuencia de nodos conectados por enlaces.


Cada nodo está conectado al siguiente por un solo

enlace, a esta estructura de datos se llama lista

simplemente enlazada.

primero


•Un nodo de una lista simplemente enlazada

contiene dos campos: datos (contiene un elemento

de la lista) y siguiente (almacena un enlace al

siguiente nodo de la lista).

•El campo siguiente del último nodo contiene un

símbolo especial que indica el final de las lista.

•Se accede a la lista por medio de un apuntador al

primer elemento y solo se puede recorrer la lista en

un sentido, del primer nodo al último nodo.

Implementación de Cola con Lista Doblemente Enlazada

•Cada nodo contiene tres campos: un campo que

almacena el elemento de la lista y los otros dos

almacenan los enlaces a los nodos precedente y siguiente

de la lista.

•Se usan punteros nulos para marcar ambos extremos de

la lista.

primero•…


Cola circular 0 1 N-1 2 . . 3 13 4 12 5 11 6 10 7

9 8

La cola circular propone tratar el arreglo como un círculo

donde cuando aLength se hace igual a aSize, el siguiente

elemento es el de índice 0. Esto permite utilizar todos los

espacios que quedan libres en el arreglo luego de

realizar eliminaciones de nodos.


Implementación de Cola con Lista Enlazada Circular

El campo siguiente del último nodo de la lista apunta al

primer nodo de la lista.

primero


Implementación de Cola con Lista Doblemente Enlazada Circular

El campo siguiente del último nodo apunte al primer nodo

de la lista y el campo anterior del primer nodo apunte al

último nodo de la lista.

primero•…


Aplicaciones con Colas

•Las Colas son comunes en la vida cotidiana: Colas de alumnos, Colas de

clientes en bancos, listas de espera, Colas para imprimir etc.

•Las colas, al igual que las pilas, resultan de aplicación habitual en muchos

problemas informáticos.

•Su utilización es infinita, desde la simulación de una cola formada frente a

un cajero automático, hasta la cola de impresión.

•Quizás la aplicación más común de las colas es la organización de tareas

de un ordenador. Los procesos forman colas para la utilización de los

recursos de un sistema computacional.

•Cuando aplicamos restricciones de acceso a la estructura tenemos Doble

Colas o Dipolos que son listas especiales; las cuales trataremos en esta

presentación


Aplicación de Cola con Bicola o Doble Cola

Esta estructura es una Cola Bidimensional en que las inserciones y

eliminaciones se pueden realizar en cualquiera de los dos extremos de la

Bicola. Gráficamente representamos una Bicola de la siguiente manera:.

EliminaElimina

Inserta Inserta

•Esta estructura equivale a dos colas colocadas una en un sentido y la otra

en sentido contrario, por ello las operaciones de inserción y eliminación se

pueden realizar por ambos extremos.

•Dos casos especiales se pueden tener, el dipolo de entrada restringida

donde sólo se puede insertar por un extremo y eliminar por ambos, y el

dipolo de salida restringida, donde se puede insertar por ambos extremos y

sólo se puede suprimir por un extremo.


Aplicación de Cola con Bicola o Doble Cola

Existen dos variantes de la doble cola:

•Doble cola de entrada restringida.

•Doble cola de salida restringida.

Elimina

Elimina Inserta

La segunda variante acepta inserciones por ambos extremos de la

cola y eliminaciones al final de la cola

InsertaElimina

Inserta

La primera variante sólo acepta inserciones al final de la cola y

eliminaciones por ambos extremos de la cola.


Operaciones Básicas en Colas

Las operaciones con Colas son muy sencillas, prácticamente no hay casos

especiales, Las Colas sólo permiten añadir y leer elementos:

• ColaCrear Inicializa la Cola en 0.

•ColaInsertar Inserta elemento al final de la Cola.

•ColaExtraer Saca elemento del principio de la Cola.

•ColaHayElementos Indica si hay elementos en la Cola.

•ColaEliminar Borra todos los elementos de la Cola.

•ColaLlena Indica si la Cola esta Llena.

•ColaVacia Indica si la Cola esta Vacía.


Operaciones en Colas

ColaCrear: Inicializa la Cola, Define Máximo de elementos, punterosprincipio y final.

Algoritmo

Si N > 0

Reservar memoria

Max_Elementos = 0

final = 0

principio = 0

N_Elementos = 0

si_no

ERROR !

Fin _ si.



ColaInsertar: Inserta un elemento en la Cola, si no esta llena, se ubica enla ultima posición y actualiza.

Algoritmo

Si Inicializada

Si N_Elementos < Max_Elementos

N_Elementos [final]= valor

final=(final +1)% Max_Elementos

N_Elementos ++

si_no

ERROR !

Fin _ si.

si_no

ERROR !

Fin _ si.

A B C D E A B C D E F



ColaIExtraer: Saca un elemento en la Cola, si no esta llena, se ubica en laultima posición y actualiza.

Algoritmo

Si Inicializada

Si N_Elementos > 0

valor=Elementos [principio]

principio=(principio +1)% Max_Elementos

N_Elementos --

si_no

ERROR !

Fin _ si.

si_no

ERROR !

Fin _ si.

A B C D E B C D E F


TAD COLA


Travel

Tad Colas