jueves, 9 de febrero de 2012

Memoria Lifo y Fifo

Memoria Lifo y Fifo
First in, first out (FIFO)




First in, first out o FIFO (en español "primero en entrar, primero en salir"), es un concepto utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que la primera persona que entra es la primera persona que sale.
También se lo llama first come first served o FCFS (en español "primero en llegar, primero en ser atendido").

FIFO se utiliza en estructuras de datos para implementar colas. La implementación puede efectuarse con ayuda de arrays o vectores, o bien mediante el uso de punteros y asignación dinámica de memoria.


Si se implementa mediante vectores el número máximo de elementos que puede almacenar está limitado al que se haya establecido en el código del programa antes de la compilación (cola estática) o durante su ejecución (cola pseudoestática ó dinámica). 
Sea cual sea la opción elegida, el número de elementos que podrá almacenar la cola quedará determinado durante toda la ejecución del programa. Así, el sistema debe reservar el tamaño de memoria necesario para acoger todos los datos, sea cual sea el número de elementos usados.

En algunas aplicaciones, esto supone un problema ya que puede desconocerse el número de elementos a contener en la cola. La sencilla solución de reservar más memoria de la que se supone que se necesitará, puede conducir a un despilfarro de la memoria (la cola puede esté llena, aprovechando toda la memoria reservada; o bien, nunca terminar de llenarse, ocupando recursos innecesarios en memoria). 
Sin embargo, si se usa asignación dinámica de memoria, el número máximo no está declarado en tiempo de compilación sino en tiempo de ejecución, es decir, se reserva memoria a medida que se necesite expandir el tamaño de la cola (adaptándose al tamaño necesario en cada momento en función de los elementos que hay en la cola), haciendo un mejor uso de la memoria disponible.

Uno de los usos de las colas es la exploración "en anchura" de un árbol binario de búsqueda. Otro uso típico de las colas, es la gestión de descargas de una aplicación P2P.

LIFO

El término LIFO es el acrónimo inglés de Last In First Out (último en entrar, primero en salir). Puede tener distintos significados según el contexto:


El término LIFO se utiliza en estructuras de datos y teoría de colas. Guarda analogía con una pila de platos, en la que los platos van poniéndose uno sobre el otro, y si se quiere sacar uno, se saca primero el último que se puso.
En ciencias de la computación y de teoría de colas se refiere a los elementos almacenados en la forma en que algunos tipos de estructuras de datos se procesan. Por definición, en una lista LIFO lineal estructurado, los elementos pueden ser añadidos o despegado de un solo extremo, llamado el "superior". Una estructura LIFO puede ilustrarse con el ejemplo de una pila de bandejas. La última bandeja que se coloca en la parte superior es también el primero en ser retirado de la parte superior.

El término en la computación se refiere generalmente a los principios abstractos de procesamiento lista y almacenamiento temporal, particularmente cuando hay una necesidad de acceder a los datos en cantidades limitadas, y en un cierto orden. LIFO es el más utilizado en los casos en que los últimos datos añadidos a la estructura debe ser de los primeros datos que deben ser removidos o evaluado. 


Una analogía útil es el empleado de oficina: una persona sólo puede manejar una página a la vez, por lo que la pieza superior del papel añadido a un montón es el primero fuera, en paralelo a las limitaciones como el ancho de bus de datos y el hecho de que sólo se puede manipular un único binario de dirección de datos en un ordenador al mismo tiempo. 
El resumen mecanismo de LIFO, cuando se aplica a la informática, inevitablemente recaen en las estructuras de datos reales implementados como las pilas del mismo nombre, cuya relación con la "pila de papel", "pila de placas "Debería ser obvio. Otros nombres para el dispositivo se "Empuje hacia abajo la lista" y "pilas"

El término FILO ("primero en entrar, último en salir") se puede utilizar como sinónimos, ya que el término hace hincapié en que las adiciones a la lista de los primeros es necesario esperar hasta que la altura de la estructura LIFO "de arriba" para acceder. 
Los LCFS plazo ("en último lugar, primero servido") se utiliza a veces en la teoría de las colas. La diferencia entre una lista general, una matriz, cola, o una pila, se define por las normas aplicadas y se utiliza para acceder al mecanismo.  En cualquier caso, una estructura LIFO se accede en orden inverso a la cola : "Hay ciertas situaciones frecuentes en la informática cuando se quiere restringir las inserciones y deleciones de modo que sólo puede tener lugar al principio o al final de la lista, no en el centro. Dos de las estructuras de datos útiles en este tipo de situaciones son pilas y colas






No hay comentarios:

Publicar un comentario