colas y pilas



PROYECTO FINAL



Materia: Estructura De Datos
Carrera: Ingeniería en computación
Fecha de entrega: 28 de Noviembre del 2013





CONCEPTO DE COLA
Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista (Fig. 11.1).
Un elemento se inserta en la cola (parte final) de la lista y se suprime oelimina por la frente (parte inicial, frente) de la lista.



Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.
Las operaciones usuales en las colas son Insertar y Quitar. La operación Insertar añade un elemento por el extremo final de la cola, y la operación Quitar elimina o extrae un elemento por el extremo opuesto,el frente o primero de la cola. La organización de elementos en forma de cola asegura que el primero en entrar es el primero en salir

Especificaciones del tipo abstracto de datos Cola
Las operaciones que sirven para definir una cola y poder manipular su contenido son las siguientes:


Tipo de dato: Dato que se almacena en la cola.
Operaciones: CrearCola Inicia la cola como vacía.

Insertar Añade un dato por el final de la cola.
Quitar Retira (extrae) el elemento frente de la cola.
Cola vacía Comprobar si la cola no tiene elementos.
Cola llena Comprobar si la cola está llena de elementos.
Frente Obtiene elelemento frente o primero de la coja.
Tamaño de la cola Número de elementos máximo que puede contener la cola.
Desde el punto de vista de estructura de datos, una cola es similar a una pila. En una cola, los datos se almacenan de un modo lineal y el acceso a los datos sólo está permitido en los extremos de la cola.
La forma que los lenguajes tienen para representar el TAD Cola depende dedónde se almacenen los elementos, en un array o en una lista dinámica. La utilización de arrays tiene el problema de que la cola no puede crecer indefinidamente, está limitada por el tamaño del array; como contrapartida, el acceso a los extremos es muy eficiente. Utilizar una lista dinámica permite que el número de nodos se ajuste al de elementos de la cola; por el contrario, cada nodo necesitamemoria extra para el enlace y también está el límite de memoria de la pila del computador



TIPO COLA IMPLEMENTADA CON ARRAY
Al igual que las pilas, las colas se pueden implementar utilizando arrays o listas enlazadas. En esta sección se considera la implementación utilizando arrays. La definición de una Cola ha de contener un array para almacenar los elementos de la cola, y dos marcadores oapuntadores para mantener las posiciones frente y final de la cola; es decir, un marcador apuntando a la posición de la cabeza de la cola y el otro al primer espacio vacío que sigue al final de la cola. Cuando un elemento se añade a la cola, se verifica si el marcador final apunta a una posición válida, entonces se añade el elemento a la cola y se incrementa el marcador final en J. Cuando unelemento se elimina de la cola, se hace una prueba para ver si la cola está vacía y, si no es así, se recupera el elemento de la posición apuntada por el marcador (puntero) de cabeza y éste se incrementa en 1. La operación de añadir un nuevo elemento en la cola comienza a partir de la posición final 0, cada vez que se añade un nuevo elemento se incrementa final en l. La extracción de un elemento sehace por el frente, cada vez que se extrae un elemento avanza frente una posición.
En la Figura 11.3 se puede observar cómo avanza el puntero frente al extraer un elemento.
El avance lineal de frente y final tiene un grave problema, deja huecos por la izquierda del array. Puede ocurrir que final alcance el índice más alto del array, no pudiéndose insertar nuevos elementos y, sin embargo, existir...