Estrutura de dados - fila
é uma estrutura de dados e um tipo abstrato de dados comportamento se baseia no armazenamento de tipo First In First Out (FIFO), ou seja, estruturas onde o Primeiro elemento a Entrar é o Primeiro a Sair.
Seu
Conceitualmente,
a FILA possui duas operações básicas:
DEQUEUE: retira o primeiro elemento da Fila; e
QUEUE: insere um elemento no final da Fila.
Para
termos de implementação ainda temos funções de inicialização de filas, verificação se está vazia, acessa primeiro, ...
Em
termos de implementação, a Fila pode ser encadeada, estática, genérica ou não genérica. mais importante é compreender que a Fila é uma lista com regras mais restritas de acesso e operações mais simples.
O
A
fila é muito empregada na Computação, geralmente para sistemas onde há compartilhamento “justo” de recursos:
sistemas operacionais: fila de processos;
simulação discreta de sistemas: geralmente em problemas onde há recursos restritos e deseja-se simular um comportamento do sistema simulado; etc...
Mas
como especificamos um Tipo Abstrato de Dado FILA?
Elemento 0
Elemento 1
Elemento 2
Elemento 3
Como era de se imaginar, em uma fila os elementos estão dispostos em sequência
Elemento 0
Elemento 1
Elemento 2
Elemento 3
As operações de leitura e remoção devem ser realizadas somente no inicio, por isso, não se precisa utilizar estruturas de dados muito complexas para implementá-la. Uma lista encadeada simples já resolve muito bem a implementação de uma Fila. Ainda é indicado trabalhar com estruturas genéricas, para evitar reimplementações (retrabalhos)
Elemento 0
Elemento 1
Elemento 2
Elemento 3
Portanto, iremos trabalhar com uma Fila implementada através da estrutura que classificamos como Lista Encadeada Dinâmica Genérica.
Toda estrutura de encadeamento simples deve acomodar os dados utilizando referências para os próximos elementos.
Note que o