Prévia do material em texto
Tipo de Dados Fila
ESTRUTURA DE DADOS
Objetivos de Aprendizagem
Descrever o conceito de fila,
interpretando a lei que rege a estrutura;
Examinar as principais diferenças para
uma lista e uma pilha;
Construir uma fila a partir do
entendimento do conceito;
Analisar operações de enfileiramento e
desenfileiramento;
Objetivos de Aprendizagem
Programar as operações de
enfileiramento e desenfileiramento;
Avaliar implementações de fila possíveis.
Agenda
Conceitos;
Operações;
Aplicação prática.
Filas
Uma fila é um conjunto ordenado de dados
de itens ou elementos a partir do qual
podem-se eliminar itens numa extremidade
(chamada de início da fila) e inserir itens na
outra extremidade (chamado de final da fila)
O primeiro elemento inserido na fila, será o
primeiro a sair
Por essa razão, uma fila é ocasionalmente
chamado de lista encadeada FIFO (first in, first
out) – o primeiro que entra é o primeiro a
sair
Filas
Existem muitos exemplos de fila no
mundo real
◦ Fila de banco
◦ Ponto de ônibus
◦ Pedágios de carros
◦ etc
Fila
A B C
início
final
Operações em Fila
Há três operações primitivas para se
aplicar em uma fila:
◦ Operação de verificação se a fila é vazia
◦ Operação de inserção
◦ Operação de Consulta e Impressão
◦ Operação de remoção
Operações em Fila
q = fila (queue)
inserir(q, A);
inserir(q, B);
Inserir(q, C);
A B C
início
final
Operações em Fila
q = fila (queue)
remove(q);
B C
início
final
Operações em Fila
q = fila (queue)
inserir(q, D);
inserir(q, E);
B D E
início
final
C
Implementação em C
Uma Fila pode ser implementada através
de um vetor ou de uma lista encadeada
(dinamicamente)
#define TAMMAX 100
struct nodo{
int fila[TAMMAX];
int inicio, fim;
}q;
struct nodo{
int valor;
struct nodo *prox;
}q;
vetor Lista Encadeada
Implementação em C
Evidentemente, usar um vetor para armazenar
uma fila introduz a possibilidade de estouro, caso
a fila fique maior que o tamanho do vetor
Ignorando momentaneamente a possibilidade de
underflow e estouro, a operação inserir(q,x)
poderia ser implementada pelas instruções:
q.fila[++q.fim] = x;
e a operação x = remove(q) poderia ser
implementada por:
x = q.fila [q.inicio++];
(depois de “remover” faz o início apontar para o
próximo)
Implementação em C
Como tratar o underflow e o estouro
(overflow) da fila ao se usar vetor?
◦ 1) para o tratamento de underflow, geralmente
se verifica o índice do vetor
Se o índice começa de 0 (zero) significa que não se
deve ter índices menores que zero (-1, -2 ...)
Esse cuidado deve se ter ao remover os itens da fila
◦ 2) Uma boa prática é utilizar uma função que
verificar se a fila esvaziou
Ex: if (inicio > fim) return filaVazia;
Implementação em C
Como tratar o underflow e o estouro
(overflow) da fila ao se usar vetor?
◦ 1) para o tratamento de overflow, geralmente
se verifica o tamanho máximo do vetor
Se o tamanho máximo é X, logo não se deve ter
índices maiores que X (X+1, X+2 ...)
Esse cuidado deve se ter ao inserir os itens na fila
◦ 2) Uma boa prática é utilizar uma função que
verificar se a fila chegou no limite
Ex: if (fim == TAMMAX) return limiteFila;
Implementação C
B D E
início
fim
C
0
início
3
fim
Após remoção
B D EC
1
início
3
fim
0 1 2 3
Implementação C
Como uma lista encadeada
Inserção
A B C D
início
fim
novoNodo = criaNodo(valor);
fim->prox = novoNodo;
fim = novoNodo;
fim
novoNodo
Implementação C
Como uma lista encadeada
Remoção
A B C D
início
fim
aux = inicio;
inicio = inicio->prox;
free(aux);
início
aux
Tipo de Dados Fila
ESTRUTURA DE DADOS
