Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 } Tiago Maritan } tiago@ci.ufpb.br Universidade Federal da Paraíba Centro de Informática Departamento de Informática Estrutura de Dados Filas 2 Conteúdos Abordados } O Conceito de Fila } Filas com Representação Sequencial } Filas com Representação Dinâmica 3 Filas } Listas que possuem a seguinte característica: } Inserção é sempre feita no final da fila (lista) } Remoção é feita no início da fila. } Analogia: filas do nosso dia-a-dia } Fila de banco, fila de carros num pedágio, etc. } FIFO: First In First Out fim da fila início da fila 4 Aplicações de Filas } Escalonamento de "Jobs": } Fila de processos aguardando os recursos do SO; } Fila de pacotes a serem transmitidos numa rede de comutação de pacotes. } Fila de impressão Operações em uma fila } insere(q, A); } insere(q, B); } insere(q, C); } x = retira (q); } insere(q, D); } insere(q, E) 6 Operações com Filas } Interface: } Criar uma fila vazia; } Testar se a fila está vazia; } Verificar se a fila está cheia; } Obter o tamanho da fila; } Consultar o elemento da frente da fila; } Inserir um novo elemento no fundo da fila; } Remover o elemento da frente da fila. 7 Filas com Representação Sequencial 8 Implementação de Filas Sequenciais } Fila sequencial é uma estrutura com: } Um array (vetor) de elementos; } Dois índices que representam o início e fim da fila; # define MAX 100 typedef struct { int item[MAX]; int inicio; int fim; int tamanho; } tFila; /* tipo Fila */ Implementação de Filas Sequenciais 9 } Problemas na implementação sequencial: } Quando índice fim possui o valor MAX - 1 não implica, necessariamente, que haja MAX -1 elementos na fila. } Isto só é verdade, se índice início possuir o valor zero; } início da fila move-se para a direita a cada retirada de elemento. } Solução: } Implementar como uma fila circular ¨ Reutilizando as posições já ocupadas pela fila; 10 Implementação de Filas Sequenciais /* Definição das Operações */ //Cria uma Fila void cria (tFila *F) { F->inicio = 0; F->fim = -1; F->tam = 0; } //Verifica se a Fila está vazia int vazia (tFila F) { if (F.tam == 0) return 1; else return 0; } //continua... 11 Implementação de Filas Sequenciais //Verifica se a Fila está cheia int cheia (tFila F) { if (F.tam == MAX) return 1; else return 0; } //Obtém o tamanho da Fila int tamanho(tFila F) { return (F.tam); } // continua... 12 Implementação de Filas Sequenciais // Consulta o elemento do início da fila. // Retorna 0 se a fila estiver vazia, 1 caso contrário. // O parâmetro dado irá receber o elemento do inicio int primeiro (tFila F, int dado) { if (vazia(F)) return 0; //Erro: Fila vazia else{ *dado = F.item[F.inicio]; return 1; } } // continua... 13 Implementação de Filas Sequenciais //Insere um elemento no fim de uma fila //Retorna 0 se a fila estiver cheia, 1 caso contrário. int insereCirc (tFila *F, int dado) { if (F->tam == MAX) return 0; // Erro: fila cheia F->fim = (F->fim + 1) % MAX; //circularidade F->item[F->fim] = dado; F->tam++; return 1; } // continua... 14 Implementação de Filas Sequenciais //Retira o elemento do início da fila //Retorna 0 se a fila estiver vazia, 1 caso contrário //O parâmetro dado irá receber o elemento retirado int retiraCirc (tFila *F, int *dado) { int res = 0; if (vazia(*F)) return 0; // Erro: Fila vazia res = primeiro(*F, dado); F->inicio = (F->inicio + 1) % MAX ; //circularidade F->tam--; return 1; } 15 Filas com Representação Dinâmica Implementação de Filas com Representação Dinâmica 16 } Implementa como uma lista com duas cabeças } Uma cabeça aponta para o início da fila } Outra aponta para o fim; início fim 17 Implementação de Filas Encadeadas // Definição da ED Fila Encadeada com Duas Cabeças typedef struct no { int dado; struct no *prox; } tNo; typedef struct fila { tNo *inicio; /* aponta para o inicio da fila */ tNo *fim; /* aponta para o fim da fila */ int tam; } tFila; /* tipo fila */ 18 Implementação de Filas Encadeadas /* Definição das Operações */ //Cria uma Fila void cria (tFila *F) { F->inicio = NULL; F->fim = NULL; tam = 0; } //Verifica se a Fila está vazia int vazia (tFila F) { if (F.tam == 0) return 1; else return 0; } // continua... 19 Implementação de Filas Encadeadas //Obtém o tamanho da Fila int tamanho (tFila F) { return F.tam; } // Consulta o elemento do início da fila // Retorna 0 se a fila estiver vazia, 1 caso contrário // O parâmetro elem recebe o elemento início int primeiro (tFila F, int *elem) { if (vazia(F)) return 0; //Erro: Fila vazia *elem = (F.inicio)->dado; return 1; } // continua... 20 Implementação de Filas Encadeadas //Insere um elemento no fim de uma fila //Retorna 0 se a mem. for insuficiente, 1 caso contrário int insere (tFila *F, int valor ) { tNo *novoNo; novoNo = malloc(sizeof(tNo)); if (novoNo == NULL) return 0; // erro: mem. insuficiente novoNo->dado = valor; novoNo->prox = NULL; if (vazia(*F)){ //Inserção em fila vazia F->inicio = novoNo; F->fim = novoNo; } else { (F->fim)->prox = novoNo; // liga com a fila F->fim = novoNo; // atualiza o novo fim. } F->tam++; return 1; } 21 Implementação de Filas Encadeadas //Retira o elemento do início da fila //Retorna 0 se a fila estiver vazia, 1 caso contrário //O parâmetro valor irá receber o elemento retirado int retira (tfila *F, int *valor ) { tNo *aux ; int res; if (vazia(*F)) {return 0;} //Erro: Fila vazia res = primeiro(*F, valor); if (F->inicio == F->fim) // Fila com 1 elemento F->fim = NULL; aux = F->inicio; F->inicio = aux->prox; F->tam--; free(aux); return (1); } 22 } Tiago Maritan } tiago@ci.ufpb.br Universidade Federal da Paraíba Centro de Informática Departamento de Informática Estrutura de Dados Filas
Compartilhar