Filas Encadeadas e Algoritmos de Alta Performance - Implementação e Operações

1 Listas Encadeadas Especiais Filas Encadeadas Algoritmos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr 2 Definição Uma fila é um conjunto ordenado de itens onde a remoção de itens se faz em um extremo e a inserção em outro É uma estrutura de dados que segue a disciplina FIFO First In First Out primeiro a entrar primeiro a sair E0 E1 En1 fim início início fim 3 Exemplo de Uso de Filas Algoritmos de Alta Performance Prof Patrícia Magna 4 Como implementar o tipo de dado Fila Algoritmos de Alta Performance Prof Patrícia Magna Implementação sequencial Utiliza um vetor para armazenar elementos Encadeada Faz alocação dinâmica na memória para cada elemento a ser armazenado na fila Não vamos implementar 5 Operações com Fila init inicia a fila deixandoa vazia isEmpty verifica se a fila está vazia retornando verdade se estiver vazia e falso caso contrário enqueuevalor insere um elemento em apenas uma extremidade da fila final da fila valor dequeue remove um elemento em apenas uma extremidade da fila início da fila valor first lê o elemento que está no início da fila e armazena em valor 6 Definição do Tipo de Dado Fila A definição do tipo de dado fila utilizando alocação dinâmica devese da mesma forma que para lista encadeada definir o nó Assim como TAD tipo abstrato de dado NO dado tipodoelemento da FILA prox ponteiro para NO 7 Definição do Tipo de Dado Fila Em JAVA private class NO int dado supondo fila armazena valor inteiro NO prox 8 Definição do Tipo de Dado Fila Uma fila precisa dos seguintes componentes Local para armazenar cada elemento nó Uma indicação de início da fila Uma indicação de final da fila Exemplo de fila com 2 elementos v1 ini v 2 fim 9 Fila Encadeada init Inicia a fila deixandoa na condição de fila vazia início fim NULO Módulo init ini NULO fim NULO ini fim 10 Implementação em JAVA init public void init ini fim null ini fim 11 Fila Encadeada IsEmpty Verifica se a fila está vazia Retorna verdade se estiver vazia falso caso contrário modulo IsEmpty se ini NULO e fim NULO então retornaverdade senão retornafalso 12 Fila Encadeada enqueue Esta operação deve considerar que existem duas situações distintas se a fila estiver vazia ambos os ponteiros de início e fim da fila devem apontar para o mesmo nó caso contrário apenas devese movimentar o ponteiro de fim 13 Fila Encadeada enqueue modulo enqueueelem novo referência para nó novo ALOCA nó novoprox NULO novodado elem se isEmpty verdade ini novo senão fimprox novo fim novo 14 Exemplo de Inserção na Fila Encadeada Supondo que a fila está vazia os ponteiros ini e fim estariam apontando para NULO Depois do ALOCA nó o nó está alocado e é referenciado por novo novo Depois do atributo prox do novo nó alocado e apontado por novo receber o ponteiro NULO e o dado receber v1 novodado v1 v1 novo ini fim ini fim 15 Exemplo de Inserção na Fila Encadeada cont Posicionando os ponteiros ini e fim para apontar a fila em sua nova configuração ini novo fimnovo v1 ini fim novo 16 Exemplo de Inserção na Fila Encadeada Verificando que a fila não está mais vazia fazse fimprox apontar para o novo nó fimprox novo e depois fim apontar para o mesmo nó apontado por novo fim novo v1 ini v2 novo fim v1 ini fim v2 novo Inserindo mais um elemento iniciando com o ALOCA nó e novodado recebendo v2 novodado v2 17 Implementação em JAVA enqueue public void enqueue int elem NO novo new NO novodado elem novoprox null if isEmpty ini novo else fimprox novo fim novo 18 FIRST Retorna o valor do elemento que está no início da fila se esta não estiver vazia Implemente essa operação 19 dequeue Retira um elemento do início da fila Considerando as possíveis situações da fila Se fila for composta por apenas 1 elemento Os ponteiros ini e fim devem ser alterados para NULO quando o elemento for retirado Caso tenha mais do que 1 elemento O ponteiro ini é o único a ser alterado 20 Operação dequeue modulo dequeue valor inidado ini iniprox se ini NULO fim NULO retorna valor 21 Exercícios 1 Elabore um programa que crie uma fila de números inteiros inserindo valores até que seja digitado um valor negativo E depois retire cada elemento inserido na fila apresentando na tela de saída 22 Exercícios 2 Implemente um programa que simule a inserção e remoção de processos na fila de uso do processador para tanto o programa deve ter um menu com as seguintes opções 1 Submete processo lê do teclado a identificação do processo pid valor inteiro e insere na fila de processos 2 Processa retira da fila 1 processo apresente o pid e depois lê do teclado se este foi concluído Se sim escreve na tela de saída mensagem de conclusão do processo pid Se não processo deve retornar ao final da fila 3 Encerrar programa permitido apenas se a fila estiver vazia 23 Exercícios 3 Simule em um programa o atendimento de pacientes em um consultório que não trabalha com agenda de horário colocando os pacientes em uma fila por ordem de chegada Cada paciente para entrar na fila deve informar o seu nome 4 Modifique o programa anterior para que cada paciente tenha como atributos além do nome sua idade 24 Referências Bibliográficas ASCÊNCIO AFG ARAUJO GS Estruturas de Dados Algoritmos Análise de Complexidade e Implementações em JAVA e CC São Paulo EdPearson Prentice Hall 2010 PEREIRA SL Estruturas de Dados Fundamentais Conceitos e Aplicações São Paulo Ed Érica 1996 TENEMBAUM AM et al Estruturas de Dados usando C Makron Books Ltda 1995 DEITEL P J Deitel HM Java como programar 8ª edição São Paulo EdPearson Prentice Hall 2010 25 Copyright 2024 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores