Trabalho analises

FIFO e FILO (Item 4.1)

Listas lineares são coleções ordenadas de elementos (valores) do mesmo tipo, tais listas podem ser comparadas a uma lista de compras, por exemplo, onde os elementos são do tipo “produto”, e a lista é ordenada em uma sequência aleatória ou não a depender de usuário da lista, existem várias formas de se implementar listas como estrutura de dados, como por exemplo  FIFO (First In, First Out, traduzido Primeiro a Entrar, Primeiro a Sair) e FILO (First In, Last Out, traduzido Primeiro a Entrar, Ultimo a Sair). Ambas as formas citadas (FIFO e FILO), podem formar listas como estrutura de dados porem suas ordens para inclusão, exclusão, e pesquisa podem conter algumas diferenças.

Definições:

FIFO do inglês First In, First Out que traduzido quer dizer “Primeiro a Entrar, Primeiro a Sair”, nome que é levado ao pé da letra já que o elemento que primeiro foi inserido será retirado por ultimo, isso acontece por que essa estrutura é uma espécie de fila contem dois pólos no pólo A os elementos são inseridos e no pólo B os elementos são retirados, sendo impossível uma operação contraria como na figura 1.0.

[pic 1]

No nosso cotidiano podemos comparar o conceito FIFO a uma fila de caixa eletrônico, onde os primeiros usuários a chegar são os primeiros a saírem já que em circunstâncias normais os uma pessoa que está no fim da fila não pode ser a primeira a usar o caixa.  Na programação o conceito FIFO é constantemente aplicado para a criação de filas de espera.

Nesse tipo de estrutura existe um apontador para cada extremidade da fila e cada campo possui no mínimo um apontador para o seu sucessor, como mostrado na figura 1.1.  

[pic 2]

FILO do inglês First In, Last Out que traduzido quer dizer “Primeiro a Entrar, Ultimo a Sair”, também denominada de Pilha, nesse conceito os elemento inseridos primeiro são os últimos a serem retirados, isso ocorre porque só a um pólo (chamado de Topo) que é usado para ambas as operações de entrada e saída como mostra a figura 2.0.

 Pode-se comparar uma estrutura LIFO a uma pilha de pratos que acabaram de ser lavados e precisão ser guardados, o encarregado da tarefa vai normalmente retirar e guardar os pratos que estão no topo da pilha sendo que o primeiro prato a ser lavado será o ultimo a ser retirado.[pic 3]

Nesse conceito cada campo tem no mínimo um apontador para seu antecessor e tem-se um apontador para o topo da pilha como mostra a figura 2.1.

[pic 4]

Existem também listas simplesmente encadeadas (também conhecida como alocação simplesmente encadeada), e listas duplamente encadeadas (também conhecida como alocação duplamente encadeada), estes tipos de listas podem ser aplicados nos conceitos FIFO e FILO.

Definições:

Lista Simplesmente encadeada o alocação simplesmente encadeada, é uma boa alternativa na implementação de arrays, consistem em uma lista em sequencial em que cada nó contém apenas um apontador que aponta para seu sucessor, como pode ser visto na figura 3.0, essa forma oferece a vantagem de ocupar pouco espaço em disco físico ou memória RAM, porém essa vantagem não é muito considerável nos dias de hoje já que discos rígidos e memórias RAM atualmente tem baixo custo, por outro lado tem-se a desvantagem de que cada elemento da lista só tem ligação com o próximo item  da lista o que a torna pouco confiável.

[pic 5]

Lista duplamente encadeada ou alocação duplamente encadeada é uma extensão da lista simplesmente encadeada, consiste em uma lista em que cada nó possui dois ponteiros, um que aponta para o seu antecessor e um que aponta para o seu sucessor como na figura 3.1, em comparação com a lista simplesmente encadeada a lista duplamente encadeada consome mais espaço em disco já que contém uma variável a mais para guardar a localização do elemento anterior, porém essa vantagem não é muito considerável nos dias de hoje já que discos rígidos e memórias RAM atualmente tem baixo custo, por outro lado é mais ágil que uma lista simplesmente encadeada já que pode se acessar o elemento anterior sem fazer uma varredura de toda a lista.