Fila Dnâmica

Prévia do material em texto

Estrutura de Dados 
Faculdade Integradas do Ceará 
Análise e Desenvolvimento de Sistemas 
 
 
Agenda 
 
 
Listas Lineares Encadeadas: 
Fila Dinâmica 
 Estrutura de Dados . 
 Estrutura de Dados . 
 
 
 
 
 
 
 
 
Estrutura de Dados Fila Dinâmica 
conceituar, representar, compreender e implementar as operações com filas 
 Estrutura de Dados . 
O que é uma Fila 
 
• O que diferencia a fila da pilha é ordem de saída 
dos elementos: enquanto a pilha é do tipo LIFO na 
fila “o primeiro que entra é o primeiro que sai” (a 
sigla FIFO – first in, first out - é usada para 
descrever esta estratégia). 
• A idéia fundamental da fila é que só podemos 
inserir um novo elemento no final da fila e só 
podemos retirar o elemento no inicio. 
Fila 
 
 Estrutura de Dados . 
• Filas são listas nas quais somente 
podem ser acessados os dois 
nodos que estão nas duas 
extremidades da fila. 
• As inclusões e novos nodos são 
sempre efetuadas no final da fila, e 
as operações de consulta, alteração 
e remoção, no seu início. 
• Esta disciplina de acesso recebe o 
nome de FIFO e é responsável por 
caracterizar uma fila. 
Fila 
Característica 
 Estrutura de Dados . 
Fila 
Implementação 
 Estrutura de Dados . 
• As operação que podem ser realizadas sobre uma fila 
são limitadas pela forma de acesso da estrutura 
(FIFO): 
– Criar uma fila vazia; 
– Verificar se a fila está cheia e/ou vazia; 
– Inserir um novo nodo no final da fila (enfileirar); 
– Excluir o nodo que está no início da fila (desenfileirar); 
– Consultar e/ou alterar o nodo que está no início da fila; 
– Destruir a fila. 
Fila Dinâmica 
Operações 
 Estrutura de Dados . 
struct nodo{ 
 int elemt; 
 nodo *prox; 
}; 
 
struct tipoFila{ 
 nodo * inicio; 
 nodo * fim; 
}; 
 
tipoFila fila; 
 
 Estrutura de Dados . 
Fila Dinâmica 
Representação – Definição da Estrutura 
 
void inicializaFila(tipoFila *f); 
int filaVazia(tipoFila *f); 
void insereNaFila (tipoFila *f, int 
elemento); 
int removeDaFila (tipoFila *f); 
 
 Estrutura de Dados . 
Fila Dinâmica 
Operações 
void inicializaFila(tipoFila *f) { 
 f->inicio=NULL; 
 f->fim=NULL; 
} 
Fila Dinâmica 
Criar Fila Vazia 
 Estrutura de Dados . 
int filaVazia (tipoFila *f) { 
 return (f->inicio==NULL); 
} 
Fila Dinâmica 
Testar Fila Vazia 
 Estrutura de Dados . 
Existem duas situações que devem ser tratadas 
diferentemente: Quando a Fila está vazia e quando não 
está vazia. A seguinte sequência de passos deve ser 
utilizada: 
1. aloca o novonodo 
2. atribui os valores ao novo nodo 
3. Se a fila está vazia 
1. inicio = novonodo 
2. fim = novonodo 
4. Senão 
1. o prox do nodo apontado por fim recebe o 
novonodo 
2. fim=novonodo 
Fila Dinâmica 
Enfileirar 
 Estrutura de Dados . 
void insereNaFila(tipoFila *f, int elemento){ 
 nodo *novonodo; 
 novonodo = (nodo*)malloc(nodo); 
 novonodo->elemt=elemento; 
 novonodo->prox=NULL; 
 if (filaVazia(f)){ 
 f->fim=novonodo; 
 f->inicio=novonodo; 
 } 
 else{ 
 f->fim->prox = novonodo; 
 f->fim = novonodo; 
 } 
} 
Fila Dinâmica 
Enfileirar 
 Estrutura de Dados . 
A remoção deve guardar o valor que está no fim da Fila, 
atualizar o ponteiro de Fim e liberar o nodo que estava no 
fim. Os seguintes passos devem ser seguidos: 
 
Se a Fila não estiver vazia: 
1. Guarda o valor contido no nodo a ser eliminado 
(que está no inicio da Fila); 
2. Guarda o endereço do nodo a ser eliminado 
(inicio) em um apontador auxiliar (rem); 
3. Inicio recebe o próximo de inicio; 
4. Libera a área apontada por aux. 
Fila Dinâmica 
Desenfileirar 
 Estrutura de Dados . 
int removeDaFila(tipoFila *f){ 
 no* rem; 
 int elemt = -1; 
 if (!filaVazia(f)) { 
 elemt = f->inicio->chave; 
 rem = f->inicio; 
 if(f->inicio->prox != NULL){ 
 f->inicio = f->inicio->prox; 
 }else{ 
 inicializaFila(f); 
 } 
 free(rem); 
 }else { 
 cout << "A fila ja esta vazia, nao ha o que remover"; 
 } 
 return elemt; 
} 
Fila Dinâmica 
Desenfileirar 
 Estrutura de Dados . 
Dúvidas 
 Estrutura de Dados .