Colas Y Pilas

Colas pilas y listas

Se pueden dividir a los programas en dos partes fundamentales que son:

Algoritmos

Estructuras de datos

Los datos físicos se encuentran asociados a un mecanismo de datos, que controla la forma en la que la información puede ser accedida por los programas, existen principalmente cuatro tipos de estos mecanismos.

Que son :

Las colas

Las pilas

Las listas

Los árboles

Cada uno de los métodos mencionados con anterioridad proporciona una solución a cada tipo de problema. Cada uno un dispositivo que realiza una operación de almacenamiento y de recuperación de los datos dados.

Todos ellos tienen dos elementos en común, como es :

El almacenamiento de datos

La recuperación de datos

Colas (Queue)

Las colas no son más que listas lineales de información a las cuales se accede de un modo determinado siendo el de tipo (FIFO) lo que quiere decir que el primer dato en entrar es también el primer dato en salir, en las colas no se permite el acceso aleatorio a ningún elemento concreto(como ejemplo podemos imaginar la cola de un supermercado, la de un cine,.....), las inserciones para las colas se hacen al final de la lista.

Hay que tener en cuenta que las operaciones de recuperación es destructiva (elimina el elemento) de la cola, si no es almacenado en otro lugar se destruye. Las colas se utilizan principalmente en las simulaciones, planificación de sucesos, y los procesos de entrada salida con buffer.

Las colas circulares: No son mas que una variante de las anteriores y su diferencia es que mientras que en las colas lineales es necesario parar el programa cuando se alcanza el limite del array en las circulares, la cola está llena solo cuando el índice de almacenamiento y el índice de recuperación son iguales, en otro caso la cola aun tiene espacio para almacenar más datos. Su utilización más común es en los sistemas operativos en los que la cola circular mantiene la información que se lee de archivo y que se escribe en archivo, aplicaciones de tiempo real, etc...

Pilas

Una pila es lo contrario de una cola, ya que su acceso es de tipo LIFO, el último que entra es el primero que sale, imaginar un montón de libros unos encima de otros y que para acceder al segundo por arriba primero es necesario coger el primero, su utilización principal es para el software de sistemas, compiladores, interpretes.

Las dos operaciones básicas, son las de almacenamiento y la de recuperación, que se llaman push (la de almacenamiento ) y pop (la de recuperación), para implementar una pila se necesitan las dos operaciones mencionadas con anterioridad y una zona de memoria para utilizarla como pila, se puede utilizar un array, o una zona asignada mediante asignación dinámica de memoria. Al igual que en las colas, la función de recuperación elimina el valor de la lista, y si este no se almacena en algún lugar, este se destruye.

La variable top es el índice de la siguiente posición libre de la pila. Cuando se implementan estas funciones, lo más importante es evitar el desbordamiento de la pila por los dos extremos, si top =0 la pila esta vacía y si top >que la ultima posición de almacenamiento la pila está llena.

...