Estruturas de Dados - Filas (Dibio)

Prévia do material em texto

dibio@unb.br
Roteiro
 Filas
 Implementação simples com vetor
 Implementação circular
 Implementação com Listas Encadeadas
 Fila simples
 Fila dupla
 Aplicações típicas de filas
 Referências Bibliográficas
dibio@unb.br
Filas
● Um tipo particular de listas
● Sequência dinâmica de elementos (nós, células), 
na qual a remoção só pode ser feita no primeiro, e 
a inserção no final da sequência
● Estratégia FIFO (First In, First Out) 
dibio@unb.br
Uso/aplicações
● Um exemplo comum de aplicação de filas é em 
programas de simulação, onde filas de 
processos/eventos com prioridade na execução são 
implementados com essa estrutura;
– filas de prioridade 
– distâncias em rede
– sistemas com recursos compartilhados (e.g. s.o., tempo 
real) 
dibio@unb.br
dibio@unb.br
Fila com um vetor comum
dibio@unb.br
Implementação do conceito Fila 
com um vetor comum
dibio@unb.br
Fila com vetor “comum”
● Nessa estratégia “comum” do vetor, uma ponta 
tende a contrair e a outra a expandir com as 
remoções e inserções;
dibio@unb.br
Fila com vetor circular
dibio@unb.br
Fila com vetor circular
● Ocupação dos elementos de forma circular
dibio@unb.br
Incremento para forma circular
● Os índices devem ser controlados de forma 
diferente, por exemplo 
dibio@unb.br
Operações básicas para um TAD 
fila (com implementação vetor)
dibio@unb.br
dibio@unb.br
Ex: TAD de uma Fila usando um 
vetor fixo (tamanho N)
dibio@unb.br
Ex: Função de Inserção
dibio@unb.br
Ex: Função de Remoção
dibio@unb.br
Ex: Testar se a fila está vazia
dibio@unb.br
Ex: Liberar memória da fila
dibio@unb.br
Exercício:
● Escreva a função incremento (incr) para a fila com 
vetor nas duas estratégias (comum e circular)
dibio@unb.br
Implementação de Fila com Lista 
Encadeada (estratégia circular)
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
Exercício para casa 
● Criar funções (TAD) para operações básicas na 
Fila Dupla usando uma implementação com vetor
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43