FIFO

Em engenharia da computação, FIFO (acrônimo para First In, First Out, que em português significa primeiro a entrar, primeiro a sair) refere-se a estruturas de dados do tipo fila. Tem uma estrutura diferente da estrutura de uma LIFO (que significa Last In, First Out, as pilhas).

As listas são amplamente utilizadas em programação para implementar filas de espera. Em uma fila de tipo FIFO os elementos vão sendo colocados na fila e retirados (ou processados) por ordem de chegada. A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Como exemplo de aplicação para filas, pode-se citar a fila de processos de um sistema operacional. Nela, é estabelecido um tempo t a ser usado por cada um dos processos. Se durante a execução de um processo o tempo passa de 0 a t, este é posto na fila e o processo seguinte é executado. Se o processo seguinte não terminar de ser executado no tempo t, ele é posto na fila e o processo subsequente é executado, e assim por diante até todos os processo serem executados.

Em termos de controle de estoque, refere-se a um método de armazenamento onde os itens são consumidos por ordem de chegada.

Em ciência da computação, LIFO (acrônimo para a expressão inglesa Last In, First Outque, em português significa último a entrar, primeiro a sair) refere-se a estruturas de dados do tipo pilha. É equivalente a FILO, que significa First In, Last Out .

O conceito de pilha é amplamente utilizado na informática, como, por exemplo, durante a execução de um programa, para o armazenamento de valores de variável local a um bloco e também para conter o endereço de retorno do trecho de programa que chamou a função ou procedimento atualmente em execução.

Usa-se os termos push e pop para denominar a inserção e remoção de elementos da pilha, respectivamente. Usa-se o termo top para consultar o elemento do topo da pilha, sem o remover.

Uma pilha é uma lista linear na qual o primeiro elemento a entrar é o último elemento a sair. Ela possui apenas uma entrada, chamada de topo, a partir da qual os dados entram e saem dela.

3.1 ALOCAÇÃO SIMPLESMENTE ENCADEADA E DUPLAMENTE ENCADEADA

Uma lista simplesmente encadeada é uma sucessão de nós onde cada nó aponta para o próximo nó da lista. O nó que possuir o valor null no ponteiro para próximo é o último nó da lista. É de extrema importância que seja mantida uma referência para o primeiro nó da lista, caso esta referência for null, significa que a lista esta vazia. Em certas situações também é útil possuir uma referência ao último nó.

Uma lista duplamente encadeada é uma sucessão de nós onde cada nó aponta para o próximo nó da lista e para seu predecessor. Assim, além do campo relativo ao dado, cada nó possui dois ponteiros, que chamaremos de prox e ant. O objetivo do duplo encadeamento é tornar mais simples e mais eficiente à execução dos algoritmos.

Os elementos podem ocupar quaisquer células de memória (não necessariamente consecutivas) e, para manter a relação de ordem linear, juntamente com cada elemento é armazenado o endereço do próximo elemento da lista.

Os elementos são armazenados em blocos de memória denominados nodos, sendo que cada nodo é composto por dois campos: um para armazenar dados e outro para armazenar endereço.

Endereço Conteúdo

L=3FFA a1 1C34 Primeiro elemento, acessível a partir de L

1C34 a2 BD2F Note que o segundo não ocupa o endereço consecutivo à a1

BD2F a3 AC12

...

1000 an-2 3A7B  Cada nodo armazena um elemento e um endereço do próximo elemento da lista

...

14F6 an-1 5D4A

5D4A an null  Último elemento da cadeia, o endereço nulo indica que o elemento não tem um sucessor.

Elimina a fragmentação externa no disco

• Arquivos podem crescer indefinidamente

• Não há necessidade de compactar o disco

• O acesso a um bloco i implica em percorrer a lista encadeada

• Afeta o desempenho

• Adequado para acesso seqüêncial