10_Filas

Prévia do material em texto

FILAS ESTÁTICAS E DINÂMICASFILAS ESTÁTICAS E DINÂMICAS
.: ESTRUTURA DE DADOS :..: ESTRUTURA DE DADOS :.
André Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo Santana
andremacedo@ufpi.edu.br
FilasFilas EstáticasEstáticas SequenciaisSequenciais
• Fila é um conceito muito utilizado na Ciência da Computação. Consiste em uma
metáfora emprestada do mundo cotidiano para resolver muitos problemas de
forma simplificada, pois é uma estrutura muito simples e muito poderosa como
elemento básico de solução de problemas complexos;
• São estruturas lineares com disciplina de acesso;
ConceitosConceitos
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Uma Fila é um caso especial de lista na qual as inserções são feitas em uma
extremidade chamada início e as retiradas são feitas na outra extremidade
denominada fim, cujo critério de acesso é denominado FIFO -First In First Out;
• Critério FIFO:
• Exigem acesso às duas extremidades;
• Início: onde é feita a retirada;
• Fim: onde é feita a inserção;
Fila Estática Sequencial
Procedimentos básicos:
• inicializar fila;
• inserir um elemento;
• excluir um elemento;
• acessar um elemento;
EstruturaEstrutura e e OperaçõesOperações
FilasFilas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Antes de começar a carregar a Fila com os dados é necessário declarar a
estrutura e inicializá-la. O processo de inicialização é realizado por uma função
que atribui ini=0 e fim=-1;
• A função inserir_fl() recebe dois parâmetros e a cada inserção o novo endereço
será calculado somando 1 à variável fim.
OperaçõesOperações: : InserirInserir e e RetirarRetirar
FilasFilas EstáticasEstáticas SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• A função retirar_fl(), obedecendo à política FIFO, é assim definida;
OperaçõesOperações: : OutrasOutras
FilasFilas EstáticasEstáticas SequenciaisSequenciais
• Duas outras funções também são normalmente implementadas no TAD Fila:
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Testar se a fila está vazia
Retornar o primeiro 
elemento da fila
ConceitosConceitos
FilasFilas CircularesCirculares SequenciaisSequenciais
• As soluções sobre Filas apresentadas anteriormente não são completas, uma vez
que ao chegar no final do vetor podemos ter uma fila cheia sem estar realmente
cheia, já que podem ter sido retirados alguns elementos.
• Há duas maneiras de solucionar esta situação:
• Incluir testes para verificar o final do vetor
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Incluir testes para verificar o final do vetor
• Verdadeiro: testar novamente os valores iniciais
• Se ocupados, fila cheia
• Senão, livres para uso
• Utilizar o conceito de filas circulares;
• Modificação na estrutura: elem[], ini, fim, tam;
Fila Estática Sequencial
Procedimentos básicos:
• inicializar fila;
• inserir um elemento;
• excluir um elemento;
• acessar um elemento;
EstruturaEstrutura e e OperaçõesOperações
FilasFilas CircularesCirculares SequenciaisSequenciais
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• O processo de inicialização de uma fila circular é
realizado por uma atribuindo ini=1, fim=0 e tam=0;
• A função inserir_flc() recebe dois parâmetros e a cada inserção os endereços das
variáveis fim e tam.
OperaçõesOperações: : InserirInserir
FilasFilas EstáticasEstáticas SequenciaisSequenciais
?
André M. Santana UFPI - CCN - DIEEstruturas de Dados
?
• A função retirar_flc() recebe dois parâmetros e a cada inserção os endereços das
variáveis ini e tam.
OperaçõesOperações: : ExcluirExcluir
FilasFilas EstáticasEstáticas SequenciaisSequenciais
?
André M. Santana UFPI - CCN - DIEEstruturas de Dados
?
OperaçõesOperações: : OutrasOutras
FilasFilas EstáticasEstáticas SequenciaisSequenciais
• Duas outras funções são normalmente implementadas no TAD Fila Circular:
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Testar se a fila está vazia
Retornar o primeiro 
elemento da fila
Fila Encadeada Estática
Procedimentos básicos:
• inicializar fila;
• inserir um elemento;
• excluir um elemento;
• acessar um elemento;
EstruturaEstrutura e e OperaçõesOperações
FilasFilas EncadeadasEncadeadas EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Toda estrutura deve ser inicializada para
ser utilizada em inserções e remoções;
•
OperaçõesOperações: : InserirInserir
FilasFilas EncadeadasEncadeadas EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
?
OperaçõesOperações: : ExcluirExcluir
FilasFilas EncadeadasEncadeadas EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
?