Aula 5 – Estr. Clássicas
Transcrição
Aula 5 – Estr. Clássicas
Aula 5 – Estr. Clássicas - Fila Universidade Federal de Santa Maria Colégio Agrícola de Frederico Westphalen Curso Superior de Tecnologia em Sistemas para Internet Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno FIFO - First In First Out • Para que um elemento entre na fila ele será sempre colocado em uma extremidade denominada final (término, fim); • Para que um elemento seja retirado da fila, ele sairá de uma outra extremidade denominada começo (início, frente); FIFO • First in, first out • Os elementos da fila são retirados na mesma ordem em que foram introduzidos: o primeiro a entrar é o primeiro a sair; • Não são permitidas operações sobre quaisquer nodos, somente sobre aqueles definidos pela organização da fila. • Controle de acesso a recursos compartilhados (fila de impressão, por exemplo) • Política de escalonamento de processos baseada em prioridades; Sistema Operacional • Definição das prioridades em uma lista de downloads; • Agendamento de tarefas; • Troca de mensagens em um sistema distribuído; • Leitura do buffer do teclado; • Enfileiramento de pacotes no equipamento de rede, antes de submetê-los ao enlace; • Etc. • Uma fila permite basicamente duas operações: Enfileirar (inserir um elemento na fila) Desenfileirar (retirar um elemento da fila) • Antes de pensar os algoritmos, precisamos: Pensar em uma estratégia de armazenamento da estrutura; Pensar na interface das operações que irão manipular os dados da estrutura; • Para representar fisicamente uma fila podemos usar diferentes estratégias: Contigüidade física – com o uso de vetores; Alocação dinâmica ou encadeamento – com a utilização de ponteiros; • Vamos adotar a opção 1 (utilização de vetores) em função da simplicidade dos algoritmos; • A organização lógica da fila independe da estratégia de armazenamento. #define MAX 100 typedef struct fila { int comeco; int final; int vetor[MAX]; } Fila; De que forma posso representar uma fila? • Inicialmente precisamos: Qual é a interface do TAD Fila? Criar e inicializar uma fila; Enfileirar (inserir) um elemento; Desenfileirar (retirar) um elemento; Destruir uma fila (liberar a memória ocupada pela mesma); • Saber se a fila está vazia; • Saber se a fila está cheia; • etc... • • • • Fila* criaFila(); void liberaFila(Fila* p); int inserir(Fila* p, int v); int retirar(Fila* p, int* v); int estahVazia(Fila* p); int estahCheia(Fila* p); • • • • • • • • • • Vetor[5]: começo final 0 1 3 2 1 3 0 2 4 5 12 40 30 20 Insere 12 Insere 40 Insere 30 Retira Insere 20 Retira Retira Insere 10 Insere 9 • Erro! Fila cheia 10 Fila* criaFila(); • Aloca memória para a estrutura física; • Inicializa os controles de início e o fim da fila; • Retorna um ponteiro para a estrutura criada; void liberaFila(Fila* p); • Recebe um ponteiro para uma estrutura do tipo fila e libera a memória ocupada por ela; int estahVazia(Fila* p); • O início e o fim da fila estão na mesma posição; int estahCheia(Fila* p); • O fim da fila está na última posição! int inserir(Fila* p, int v); • Recebe um ponteiro para uma estrutura do tipo fila e um valor a ser enfileirado; • Verifica se a fila já não está cheia; • Se não está, então ... Coloca o elemento na posição indicada pelo fim Incrementa o valor do fim; • A função inserir() retorna 1 (um) se o valor foi enfileirado ou então retorna 0 (zero) se não foi possível enfileirar; int retirar(Fila* p, int* v); • Recebe um ponteiro para uma estrutura do tipo fila e um ponteiro para uma variável inteira; • Verifica se a fila já não está vazia; • Se não está, então ... Retira o elemento da posição indicada pelo início; Incrementa o valor do início; • A função retirar() retorna 1 (um) se o valor foi retirado da fila ou então retorna 0 (zero) se não foi possível retirá-lo; a = criaFila(); inserir(a,10); inserir(a,20); inserir(a,30); int x; retirar(a, &x); printf("Elemento '%d' retirado",x); liberaFila(a); Exercícios para fixação • Dado um labirinto representado por uma matriz NxN, contendo -1 em posições onde há um obstáculo, 1 nas posições onde há ouro e 0 nas posições livres. Escreva um programa para percorrer o labirinto e determinar quanto ouro existe no mesmo. 0 1 2 3 4 5 6 0 -1 -1 -1 -1 -1 -1 -1 1 -1 0 0 -1 0 -1 -1 2 -1 0 0 0 0 1 -1 3 -1 -1 -1 0 0 0 -1 4 -1 1 -1 0 -1 0 -1 5 -1 0 0 0 -1 0 -1 6 -1 -1 -1 -1 -1 -1 -1 Coloca na fila a posição inicial (x,y) Enquanto a fila não está vazia Remove a posição do início da fila Para cada posição vizinha que é acessível e que não foi visitada, coloque na fila e marque como visitada. “Dobrar” o vetor de forma que as suas extremidades se encontrem • Observe a seguinte situação (considerando uma fila normal, de tamanho N implementada sobre um vetor): São inseridos N elementos na fila; Em seguida são retirados n-2 elementos; Tenta-se incluir mais um elemento; O que acontece? A fila acusará fila cheia! Mas há espaço no vetor! Isso é um problema da regra que define a fila? Não! O problema decorre da forma utilizada para representar a fila: o VETOR; • Se modificarmos a organização física da fila e a implementação de suas operações o problema pode ser resolvido. • Vamos imaginar um “vetor dobrado” de forma que o fim do vetor se encontre com o início • Antes de mais nada, uma fila circular é uma fila e portanto suas operações acontecem da seguinte forma: Inclusões: no final da fila; Retiradas: no início da fila; • A diferença está na forma de tratar a organização física da fila. A interface é a mesma da fila tradicional. #define MAX 100 typedef struct fila { int comeco; int final; int tamanho; int vetor[MAX]; } Fila; Precisamos controlar o tamanho da fila de outra forma! • Precisamos garantir que os indicadores de posicionamento da fila circular (começo e final) retornem ao início sempre que atingirem o valor limite do tamanho do vetor; • Algo como: variavel = variavel + 1 se variavel > MAX então variavel = 0 • As condições “fila cheia” e “fila vazia” também devem ser alteradas: • Uma fila está cheia se o campo que foi adicionado par controlar o tamanho for igual ao tamanho do vetor; • Uma fila está vazia se o tamanho for igual a zero; Exercícios para fixação • Modifique a implementação das operações e da estrutura utilizada para representar uma fila utilizando uma organização circular (conforme os conceitos discutidos até então);