Filas - java

Listas Lineares

ALGESD 07 Filas
Prof. Dr. Marcelo Duduchi

Vimos anteriormente o conceito de listas lineares e mostramos que tanto as pilhas quanto as filas são listas lineares restritas; Vimos que as pilhas caracterizam-se pela dinâmica em que o último elemento que entra é o primeiro a sair; Conheceremos agora as filas...

Filas
Uma lista linear onde a entrada é feita por uma extremidade e a saída é feita pela outra extremidade é conhecida como fila; Neste caso o primeiro elemento a entrar é o primeiro elemento a sair (First In First Out); Existem duas funções que se aplicam a todas as filas:
Store

Filas (modelo conceitual)
Retrieve

STORE, que insere um dado no final da fila; RETRIEVE, que remove o item do início da fila;

Filas (representação gráfica)

Filas (representação gráfica)

Filas (implementação)
Estaremos optando por implementar uma fila circular que é mais eficiente que a fila onde “empurramos” os elementos para as posições iniciais do vetor; Na fila circular tanto o front quanto o rear caminham em direção ao final do vetor porém, ao chegar no final consideramos que voltamos ao início dele de forma “circular”;

Filas (implementação)
Na Inclusão colocamos o elemento na posição do rear e ele vai para a próxima posição; front front
A
8 7 6 5 4 2 3 1

A B rear
5 4 7 6 2 3 8 1

B C

C rear store (“C”,fl);

Filas (implementação)
Na retirada retornamos o elemento que está no front e ele vai para a próxima posição; front
A A front B
7 6 5 4 3 2 8 1 8 7 6 5 4 3 2 1

Filas (implementação)
A condição de fila vazia acontece quando front é igual a rear; A condição de fila cheia acontece quando o “próximo de rear” for igual a front Uma das possíveis saídas para fila cheia ser diferente de fila vazia; Por conta disto um elemento do vetor é “sacrificado”;

B C

C

rear retrieve (fl);

rear

Filas (implementação)
Consideremos para a nossa implementação um grupo de operações: NEXT: indica quem é o próximo elemento;