Baixe o app para aproveitar ainda mais
Prévia do material em texto
* * Filas * * Filas Outro caso particular de Lista Linear Conjunto ordenado de itens onde as inclusões só podem ser feitas em uma extremidade (fim da fila) e as remoções só podem ser feitas na outra extremidade (início da fila) Exemplo real clássico: fila de pessoas esperando atendimento em um banco: as pessoas do início da fila são atendidas antes e as que chegam depois, entram no fim da fila * * Filas Devido às características das operações da fila, o primeiro elemento inserido será o primeiro a ser retirado A política de inserção e remoção de dados à maneira de uma fila é conhecida como "FIFO" (First In, First Out) Filas são usadas tipicamente quando deseja-se processar itens de acordo com sua ordem de chegada * * Filas Aplicação em Computação: Fila de Impressão Exemplo: início início início fim fim fim A C * * Filas – Operações Básicas Seja F uma fila, e e um elemento: insere(F, e): e é inserido no final da fila F retira(F, e): retira o elemento mais antigo da fila F (o elemento que está no início de F) e retorna seu valor através de e vazia(F): indica se a fila está vazia ou não comp(F): retorna o número de elementos na fila F (comprimento da fila) * * Filas - Exemplo início início início fim fim fim A C fila insere(fila,A); insere(fila,B); insere(fila,C); ok=retira(fila,e); * * Fila – Funções Básicas Funções Básicas: vazia(&fila); inicia(&fila); retira(&fila, &e); insere(&fila, e); * * Filas 2ª PARTE * * Filas - Implementações Diversas formas de implementar, que se distinguem por: natureza dos elementos maneira como elementos são armazenados operações disponíveis Duas formas clássicas: Listas Seqüenciais (Vetor) Lista Encadeada * * Filas em Listas Seqüenciais Problema: vetor tem tamanho fixo e limitado, enquanto que a fila cresce com a necessidade, sem limite Solução: limitar o tamanho máximo da fila ao tamanho do vetor Problema: impossível remover elemento de uma fila vazia Solução: utilizar a função vazia(F) antes de remover elemento Problema: controlar início e fim da fila Solução: incluir dois campos (ini e fim) para armazenar a posição do início e do fim da fila * * Filas com Vetor #define MAX 100 typedef int tp_item; typedef struct { tp_item item[MAX]; int ini,fim; } tp_fila; tp_fila fila; * * Filas com Vetor Considerações Iniciais: fila.fim=-1; /* posição do último elemento */ fila.ini=0; /* posição do primeiro elemento */ Fila Vazia: (fila.fim<fila.ini) Fila Lotada: (fila.fim==MAX-1) No de elementos: (fila.fim-fila.ini+1) Função insere: f.item[++f.fim]=e; Função retira: *e=f.item[f.ini++]; * * Filas com Vetor Problema: ini e fim avançam à medida em que são feitas inclusões e remoções pode acontecer de a fila ter espaço mas ser considerada lotada (situação 4)!! ini: 0 fim: -1 MAX: 5 A B C ini: 0 fim: 2 MAX: 5 C ini: 2 fim: 2 MAX: 5 C D E ini: 2 fim: 4 MAX: 5 (1) (2) (4) (3) A B C A B D E 0 1 2 3 4 * * e=f.item[0]; for (i=0; i<fila.fim; i++) fila.item[i]=fila.item[i+1]; Filas com Vetor Solução 1: modificar retira para deslocar a fila no sentido do início do vetor a cada remoção e eliminar o campo fila.ini início é sempre no 0 fim: -1 MAX: 5 A B C fim: 2 MAX: 5 C fim: 0 MAX: 5 C D E fim: 2 MAX: 5 (1) (2) (4) (3) A B C A B D E Fila vazia: (fila.fim==-1) * * Filas com Vetor Problemas com a Solução 1: Cada eliminação envolve deslocar todos os elementos restantes da fila Ineficiência (principalmente para grandes filas) A definição da operação de remoção envolve a manipulação de apenas um elemento e a sua implementação deve refletir este fato, sem envolver operações adicionais * * Filas com Vetor Outra Solução? * * Fila Circular Solução 2: visualizar o vetor que armazena a fila como um círculo Fila Circular se o último elemento da fila ocupa a última posição do vetor, um novo elemento pode ser inserido no início do vetor ini: 0 fim: -1 MAX: 5 A B C D ini: 0 fim: 3 MAX: 5 C D ini: 2 fim: 3 MAX: 5 F G C D E ini: 2 fim: 1 MAX: 5 (1) (2) (4) (3) A B C D A B E F G 0 1 2 3 4 * * Fila Circular Outras considerações: Função para determinar o próximo elemento: int prox (int pos) { if (pos==MAX-1) return 0; else return pos+1; } * * Fila Circular – Fila Vazia Determinação de Fila Vazia? não pode mais ser feita por (fila.fim<fila.ini) ini: 0 fim: -1 MAX: 5 F G C D E ini: 2 fim: 1 MAX: 5 (1) (4) 0 1 2 3 4 0 1 2 3 4 * * Fila Circular – Fila Vazia Problema com a Fila Circular: determinação de Fila Vazia não pode mais ser feita com (fila.fim<fila.ini) Solução: considerar que fila.ini é a posição anterior ao primeiro elemento da fila Para verificar se a fila está vazia: (fila.ini==fila.fim) Para inicializar início e fim com última posição: fila.ini = fila.fim = MAX-1; (precede posição 0) * * Fila Circular – Fila Vazia Solução! (fila.ini==fila.fim) ini: 4 fim: 4 MAX: 5 A B C D ini: 4 fim: 3 MAX: 5 ini: 3 fim: 3 MAX: 5 F G H E ini: 3 fim: 2 MAX: 5 (1) (2) (4) (3) A B C D A B C D E F G H 0 1 2 3 4 0 1 2 3 4 * * Fila Circular – Fila Cheia Problema: Determinação de Fila Cheia Situação idêntica à da Fila Vazia Solução: “sacrificar” uma posição do vetor, permitindo incluir apenas MAX-1 elementos há sempre uma posição vazia para marcar início/fim da fila Teste de Fila Cheia: prox(fila.fim)==fila.ini * * Fila Circular – Fila Cheia Fila Vazia (fila.ini==fila.fim) ini: 4 fim: 4 MAX: 5 A B C D ini: 4 fim: 3 MAX: 5 ini: 3 fim: 3 MAX: 5 F G H E ini: 3 fim: 2 MAX: 5 (1) (2) (4) (3) A B C D A B C D E F G H 0 1 2 3 4 0 1 2 3 4 Fila Cheia (prox(fila.fim)==fila.ini) * * Fila Circular – Fila Cheia Outra Solução: Adicionar um novo campo (tam) na estrutura para armazenar o número de elementos na fila Fila Vazia: (fila.tam==0) Fila Cheia: (fila.tam==MAX-1) Solução não adotada pela maioria dos autores e programadores * * Fila Circular Funções Básicas: vazia(&fila); inicia(&fila); retira(&fila, &e); insere(&fila, e); * * Fila Circular Função vazia(&fila): int vazia(tp_fila *f) { if (f->ini == f->fim) return 1; else return 0; } /* outra opção */ int vazia(tp_fila *f) { return (f->ini==f->fim); } Função inicia(&fila): void inicia (tp_fila *f) { f->ini=f->fim=MAX-1; } * * Fila Circular int retira(tp_fila *f, tp_item *e) { if (vazia(f)) return 0; else { f->ini=prox(f->ini); *e=f->item[f->ini]; return 1; } } * * Fila Circular int insere(tp_fila *f, tp_item e) { if (prox(f->fim)==f->ini) return 0; else { f->fim=prox(f->fim); f->item[f->fim] = e; return 1; } } * * Fila Circular Como percorrer a Fila? ? * * Fila Circular if (!vazia(&fila)) { i=fila.ini; do { i=prox(i); printf("%d\t",fila.item[i]); } while (i!=fila.fim); printf("\n"); } /*outra forma */ i=fila.ini; while (i!=fila.fim) { i=prox(i); printf("%d\t",fila.item[i]); } printf("\n"); Para percorrer: * 105 * 104 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105 * 105
Compartilhar