Colas:

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, 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 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 y pop, 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  esbordamiento 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.

Listas enlazadas:

Al contrario que las pilas y las colas las listas enlazadas pueden acceder a una zona de memoria de forma aleatoria, ya que cada trozo de información lleva un enlace al siguiente elemento de la cadena. Una lista enlazada requiere una estructura de datos compleja, al contrario que las colas o las pilas, que pueden operar con elementos simples o complejos, además una operación de  ecuperación en una lista enlazada no elimina ni destruye el elemento de la lista. Para poder eliminar un elemento de una lista es necesario utilizar una operación especifica de eliminación.

Las listas enlazadas se utilizan principalmente para dos propósitos, crear arrays de un tamaño desconocido en memoria, y los archivos de almacenamiento en disco para bases de datos, las listas enlazadas permiten insertar y eliminar nuevos elementos.

Listas simplemente enlazadas:

Una lista  simplemente enlazada necesita que cada elemento contenga un enlace con el siguiente elemento, cada elemento consiste
en una estructura de campos de información  a punteros de enlace.

Existen dos formas de construir una lista simplemente enlazada , la primera es añadir un nuevo elemento al principio o al final de la lista, la otra añade los elementos en un punto especifico de la lista.

Si la lista ya esta ordenada, es conveniente mantenerla así, insertando los nuevos elementos en su lugar apropiado para lo cual se explora la lista de forma secuencial hasta encontrar el lugar apropiado, la nueva dirección se inserta en ese punto y los enlaces se vuelven a colocar como sea necesario.

Listas doblemente enlazadas:

Las listas doblemente enlazadas consisten en datos y enlaces tanto al elemento siguiente como al elemento anterior. Con lo que se consiguen dos grandes ventajas, primero la lista se puede leer en cualquier dirección, la segunda es que se pueden leer los enlaces hacia delante como hacia atrás, con lo que si un enlace resulta no valido se puede reconstruir utilizando el otro enlace.

Como en las listas simplemente enlazadas, las doblemente enlazadas pueden contener una función que almacene cada elemento en una posición especifica de la lista a medida que esta se construye, en lugar de colocar cada elemento al final de la lista.

Para mayor informacion consultar las siguientes paginas:

http://www.lcc.uma.es/~pscp/doc/colas.doc

http://es.wikipedia.org/wiki/Lista_(inform%C3%A1tica)

About these ads