Apúntate...


Consultas, desarrollo de programas y petición de presupuestos:

miércoles, 12 de septiembre de 2012

Fifo y Lifo

Listas Fifo y Lifo

¿que es una lista fifo?
Primero en Entrar, Primero en Salir, en inglés First In, First Out (FIFO), es un concepto utilizado en estructuras de datoscontabilidad 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 le denomina «primero en llegar, primero en ser atendido», en inglés: First Come, First Served (FCFS).
https://es.wikipedia.org/wiki/First_in,_first_out



¿y que es una lista lifo?
El término LIFO es el acrónimo inglés de Last In, First Out (“último en entrar, primero en salir”), también conocido como FILO que es la sigla de First In, Last Out (“primero en entrar, último en salir”). Puede tener distintos significados según el contexto.

Para implementar este tipo de listas en gambas3,  lo haremos de forma genérica, vamos a usar este diagrama uml para que veais más claro como se organizará el código fuente y sus clases:


En el ide de gambas3, se queda de esta manera:



Clase ApiLista:


PUBLIC SUB anadir(Obj AS Variant)

END


PUBLIC FUNCTION extraer() AS Variant

END


PUBLIC FUNCTION getlongitud() AS Integer

END




Clase colaFifo:

' Gambas class file

INHERITS ApiLista

PRIVATE primero AS Nodo
PRIVATE ultimo AS Nodo
PRIVATE longitud AS Integer

PUBLIC SUB anadir(obj AS Variant)


DIM aux AS NEW Nodo
aux.objeto = obj
IF longitud = 0 THEN
primero = aux
ELSE
ultimo.siguiente = aux
ENDIF


ultimo = aux
longitud += 1


END




PUBLIC FUNCTION extraer() AS Variant

DIM obj AS Variant
IF longitud = 0 THEN
RETURN -111 'cola vacia

ELSE
obj = primero.objeto
primero = primero.siguiente
longitud -= 1
RETURN obj
ENDIF

END


PUBLIC FUNCTION getlongitud() AS Integer

RETURN longitud

END




Clase pilaLiFo:

' Gambas class file

INHERITS ApiLista


PRIVATE top AS Nodo
PRIVATE longitud AS Integer


PUBLIC SUB anadir(obj AS Variant)


DIM aux AS NEW Nodo
aux.objeto = obj
aux.siguiente = top
top = aux
longitud += 1


END



PUBLIC FUNCTION extraer() AS Variant
DIM obj AS Variant


IF top = NULL THEN
RETURN NULL ' lista vacia
ENDIF


obj = top.objeto
top = top.siguiente
longitud -= 1
RETURN obj

END


PUBLIC FUNCTION getlongitud() AS Integer


RETURN longitud


END





Clase Nodo:

PUBLIC objeto AS Variant
PUBLIC siguiente AS Nodo





En el Formulario FMain: 


Crearemos unas listas tipo pilaLifo y colaFifo, añadiremos algunos elementos y luego lo extraeremos, mostrandolo en un textarea.


PUBLIC SUB Form_Open()

DIM i AS Integer
DIM elementos AS Integer


DIM pila AS NEW pilaLiFO
DIM cola AS NEW colaFifo



' Añadimos los mismos elementos a la pila y la cola.
FOR i = 0 TO 9
pila.anadir("AB" & Str$(I))
cola.anadir("AC" & Str$(I))
NEXT


' Extraer Pila
TextArea1.text = "Orden de Extraccion de la pila LIFO:\n"


elementos = pila.getlongitud()


FOR i = 0 TO elementos - 1
TextArea1.text &= " [" & pila.extraer() & "] "
NEXT


TextArea1.text &= "\n-------\n"
'Extraer en Cola
TextArea1.text &= "Orden de Extraccion de la cola FIFO:\n"




elementos = cola.getlongitud()


FOR i = 0 TO elementos - 1
TextArea1.text &= " [" & cola.extraer() & "] "
NEXT



END






Ejemplo funcionando:



Código Fuente:
Alojado en google drive



Nota:
Extensión para libreoffice para colorear código fuente:
http://extensions.libreoffice.org/extension-center/coooder

No hay comentarios:

Publicar un comentario en la entrada

A falta de donativos... un poco de publicidad