FILA DINÂMICA

Sáb Jul 01, 2017 12:59 pm

Definição

Uma fila é uma estrutura de dados dinâmica que admite remoção de elementos e inserção de novos objetos. Mais especificamente, uma fila (= queue) é uma estrutura sujeita à seguinte regra de operação: sempre que houver uma remoção, o elemento removido é o que está na estrutura há mais tempo.

Partindo do princípio "Primeiro a entrar ‐ Primeiro a sair", ou como é comumente conhecido, FIFO (First‐in ‐ First Out). Desta forma as operações que modificam o tamanho dos objetos da pilha necessitam respeitar este princípio

FILA DINÂMICA: Já na fila dinâmica, os objetos são alocados em tempo de execução e neste caso um elemento deve conhecer o endereço do seu sucessor. Os itens da fila dinâmica estão armazenados espalhados em posições na memória. Assim como em outras estruturas dinâmicas são utilizados ponteiros que armazenam endereços de memória, como método de organização e de operações como inserção e remoção.

A construção do protótipo de um elemento da Fila

Para determinar um elemento da pilha vamos nos servir do tipo struct.

Código:: typedef int TIPOCHAVE; typedef struct { TIPOCHAVE chave; } REGISTRO; typedef struct { REGISTRO reg; struct aux* prox; } ELEMENTO; typedef ELEMENTO* PONT; typedef struct { PONT inicio; PONT fim; } FILA;

Operações em Fila dinâmica

Inicialização

Código:: //Função: void inicializaFila(FILA f){ f->inicio = NULL; f->fim = NULL; }

Tamanho da Fila

Código:: ///Função: int tamanhoFila(FILA *f){ // Função para verificar o tamanho da FILA, como parâmetro int cont = 0; //cont vai receber 0, pq se não tiver elemento retorna 0; PONT aux = f->inicio; // while(aux!= NULL){ cont++; aux = aux->prox; } return (cont); }

Exibir Fila

Código:: //Função: void exibeFila(FILA *f){ // procedimento para exibir os elementos da FILA, passa a FILA como parâmetro um ponteiro if (f->inicio = NULL) printf("\nFILA não possui elemento"); // se for verdadeira exibe que a FILA não possui elemento PONT aux = f->inicio; //equanto o ponteiro não for diferente de NULL vai executar a instrução printf("\n Os elementos da minha FILA: "); while (aux!=NULL){ // se inicio for igual a NULL: A fila não possui elemento printf("%d" , aux->reg.chave); //imprimir os elementos aux = aux->prox; // tem que ir para o próximo elemento } }

Inserir elemento na Fila

Código:: //Função: void insereElemFila(FILA *f, REGISTRO reg){ // primeiro teste: testar se o inicio e o fim são NULL, se o elemento novo que criar vai fazer o auxiliar apontar para o próximo PONT novo = (PONT) malloc(sizeof(ELEMENTO)); novo->reg = reg; // novo recebe registro novo->prox = NULL; // if (f->inicio==NULL) f->inicio = NULL; else f->fim->prox = novo; f->fim = novo; // FIM vai receber o novo }

Excluir elemento da Fila

Código:: //Função: int excluirElemFila(FILA *f){ // excluir sempre o primeiro elemento da FILA, FIFA (first in, first out) if(f->inicio==NULL) return (-1); // significa que não tem elementos para excluir PONT apagar = f->inicio; // apagar vai receber o inicio da FILA f->inicio = prox; // inicio vai receber o proximo elemento free(apagar); if(f->inicio==NULL) f->fim=NULL; // se caso um único elemento for excluído, o fim recebe NULL return 0; }

Reinicializar Fila

Código:: //Função: void reinicializar(FILA *){ while(excluirElemFila(f)!=-1); // enquanto o excluir for diferente de -1, executa a chamada, só para quando for diferente de -1 }

Videos para reforços ( ABRA OS SPOILERS )

[ED] Aula 34 - Fila Estática - Inserção e Remoção:

[ED:

[ED] Aula 32 - Criando e Destruindo uma Fila Estática: