Filas com Armazenamento Sequencial - Estruturas de Dados

ESTRUTURAS DE DADOS FILAS COM ARMAZ SEQUENCIAL Prof Ms Peter Jandl Junior ADS FATEC Jundiaí ARMAZENAMENTO SEQUENCIAL Quando é usado um bloco único de memória para organizar uma estrutura de dados 06032022 C 20132022 JANDL 2 ARMAZENAMENTO DE ESTRUTURAS DE DADOS Armazenamento Sequencial Situação onde toda a estrutura de dados é armazenado em um único bloco de memória organizado como uma sequência de posições contíguas ie sem descontinuidades Armazenamento Não Sequencial Situação onde a estrutura de dados à medida de seu crescimento é armazenada em pequenos blocos de memória que ocupam posições esparsas ie distribuídas na memória 06032022 C 20132022 JANDL 3 ARMAZENAMENTO SEQUENCIAL Existem muitos problemas onde os dados necessários apresentamse como uma sequência Pilhas filas e listas de qualquer espécie Nestas situações é comum o uso de estruturas de dados baseadas no armazenamento sequêncial ie que utilizam arrays Um array é um conjunto de elementos do mesmo tipo armazenados numa região contínua de memória 06032022 C 20132022 JANDL 4 ARRAYS Vantagens Organização simples Elementos do mesmo tipo Acesso direto a qualquer elemento Armazenamento eficiente se usado quase integralmente Desvantagens Não podem ter tamanho alterado Só armazenam elementos do mesmo tipo Opção ineficiente de armazenamento quando número de elemento varia muito 06032022 C 20132022 JANDL 5 FILAS Outra tipo de estrutura de dados simples mas extremamente útil tanto que é muito utilizada 06032022 C 20132022 JANDL 6 FILAS São estruturas de dados onde seus elementos são colocados em sequência respeitandose a ordem de entrada adição A entrada é realizada somente em um extremo seu fim enquanto a saída é realizada apenas no outro seu início Quando um elemento é removido os demais são deslocados de uma posição para o início a fila anda Esta estrutura de dados é semelhante a uma fila de carros pessoas caixas ou pedidos 06032022 C 20132022 JANDL 7 A ideia de Fila também é um TAD Tipo Abstrato de Dados FILASOPERAÇÕES Operações comuns sobre uma fila Adição de elemento no fim Remoção de elemento do início Contagem dos elementos contidos na fila Indicação de fila vazia Listagem dos elementos contidos na fila e Consulta sem remoção do elemento do início Tais operações são independentes do tipo de elemento armazenado na fila 06032022 C 20132022 JANDL 8 Tais operações constituem a interface da estrutura de dados FILACOM ARMAZENAMENTO SEQUENCIAL Uma fila pode ser implementada com auxílio de um array Vantagens solução simples e versátil Desvantagens elementos do mesmo tipo tamanho limitado e movimentação dos elementos 06032022 C 20132022 JANDL 9 Fila Vazia 5 Fila com um elemento 73 5 Fila com dois elementos 8 73 5 Fila com três elementos 8 73 Fila com dois elementos FILASOPERAÇÕES Padronização das operações comuns adicionarint adição de elemento no fim remover remoção de elemento do início comprimento contagem dos elementos contidos na fila vazia indicação de fila vazia elementoint consulta sem remoção do elemento na posição p cheia indicação de fila cheia capacidade quantidade máx de elementos toString listagem dos elementos contidos na fila 06032022 C 20132022 JANDL 10 Tais operações constituem a interface da estrutura de dados FILAINTREPRESENTAÇÃO UML 06032022 C 20132022 JANDL 11 FilaInt FilaIntint adicionarint void remover int elementoint int capacidadeint comprimentoint cheia boolean vazia boolean toString String v int fim int FilaInt Nome da classe CamposAtributos da classe OperaçõesMétodos da classe Legenda público privado protegido FILACOM ARMAZ SEQUENCIAL public class FilaInt private int v private int fim 0 public FilaIntint tam v new inttam public FilaInt this4 public int comprimento return fim Não implementados aqui public int capacidade public String toString public int elementoint p public void adicionarint elem vfim elem fim public int remover if vazia throw new RuntimeExceptionvazia int aux v0 for int i1 ifim i vi1 vi fim return aux public boolean vazia return fim0 public boolean cheia return fimvlength 06032022 C 20132022 JANDL 12 A remoção de um elemento exige movimentação dos remanescentes USO DA CLASSE FILAINT Para declarar uma fila de inteiros FilaInt fila Para instanciar uma fila de inteiros com tamanho padrão fila new FilaInt Para declarar e instanciar com outro tamanho FilaInt fila new FilaInt 33 06032022 C 20132022 JANDL 13 USO DA CLASSE FILAINT Para saber quantos elementos existem na fila int quant filacomprimento Para conhecer a capacidade da fila int max filacapacidade Para testar se fila vazia if filavazia fila está vazia else fila não está vazia Para testar se fila cheia if filacheia fila está cheia else fila não está cheia 06032022 C 20132022 JANDL 14 USO DA CLASSE FILAINT Para adicionar um elemento na fila int elem 10 filaadicionarelem Para retirar um elemento da fila int elem filaremover Para obter sem remover um elemento da fila int elem filaelemento0 o primeiro inserido início Para conhecer elemento que está no fim da fila sem removêlo int final filaelemento filacomprimento1 06032022 C 20132022 JANDL 15 FILATESTAFILA01 public class TestaFila01 public static void mainString a FilaInt f new FilaInt10 SystemoutprintlnftoString fcapacidade fadicionar20 fadicionar15 fadicionar8 Systemoutprintlnf toString implícito Systemoutprintlnremovido fremover Systemoutprintlnremovido fremover Systemoutprintlnf fcomprimento 06032022 C 20132022 JANDL 16 FILATESTAFILA02 public class TestaFila02 public static void mainString a FilaInt f new FilaInt5 SystemoutprintlnftoString fcapacidade int elem 0 whilefcheia fadicionarelem Systemoutprintlnf whilefvazia elem fremover Systemoutprintlnf elem 06032022 C 20132022 JANDL 17 FILAAPLICAÇÃO DE UM TAD Observe que nos programas TestaFila01 e TestaFila02 foram utilizadas filas por meio de classes que implementam um TAD Com isso As regras de utilização da fila foram observadas sem que o programador tenha ciência ou se esforce para tal Não é possível burlar as regras de utilização da fila garantindo consistência e robustez dos programas As técnicas de implementação da fila não são expostas e portanto não são conhecidas no programa Apenas os conceitos abstratos de fila são conhecidos 06032022 C 20132022 JANDL 18 FILAS Como consequência dos elementos de uma fila serem movimentados pelas duas extremidades da estrutura A ordem de remoção retirada dos elementos é mesma da ordem de adição inserção Assim o primeiro elemento que entra na pilha é o primeiro que sai ou FIFO Fifo In First Out Filas são estruturas comuns que ocorrem em muitos problemas reais relacionados com produçãoconsumo e atendimento 06032022 C 20132022 JANDL 19 EXERCÍCIOS 1 Escreva um programa que utilize uma fila para armazenar 10 valores inteiros dados pelo usuário apresentandoos após sua entrada 2 Escreva um programa que armazene até 10 inteiros dados pelo usuário positivos e negativos em filas separadas Um valor 0 zero finaliza a sequência Exiba os valores após sua entrada Nestes exercícios utilize a classe FilaInt dada 06032022 C 20132022 JANDL 20 EXERCÍCIOS 3 Escreva um programa que armazene em uma fila para 12 valores inteiros dados pelo usuário Depois da entrada exibir os valores remover todos os elementos pares existentes e exibir novamente a fila 4 Escreva um programa que simule o atendimento prestado por caixas de um banco consumindo as senhas de uma fila normal e outra preferencial Um menu deve prover as operações de emissão de senhas normal e preferencial além da chamada para atendimento Nestes exercícios utilize a classe FilaInt dada 06032022 C 20132022 JANDL 21 EXERCÍCIOS EXTRA 5 Reescreva a classe FilaInt para que possa armazenar valores reais elementos do tipo double Denomine tal classe de FilaDouble Teste esta classe refazer os Exercícios de 1 a 4 6 Reescreva a classe FilaInt para que possa armazenar elementos de qualquer tipo classe Object Denomine esta nova classe de Fila Teste esta classe refazer os Exercícios de 1 a 4 Nestes exercícios você criará novos tipos de fila 06032022 C 20132022 JANDL 22