Baixe algoritmos - estruturas - dados - java e outras Notas de estudo em PDF para Algoritmos, somente na Docsity! Pg Cselum S&S Ensino e Soluções em Java q o» (S-14 Algoritmos e Estruturas S 4 : de Dados em Java APAC [Pop M oligo Índice 1 Prefácio 1 2 Introdução 2 2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Algoritmo e Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 Estrutura de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 Sobre este texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Armazenamento Sequencial 5 3.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 O problema da listagem de alunos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 Modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Exercícios: Armazenamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Vetores 11 4.1 Os testes primeiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Operações em vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.3 Adicionar no fim da Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 O método toString() para o Vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.5 Informar o tamanho da Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.6 Verificar se um aluno está presente no vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.7 Pegar o aluno de uma dada posição do array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 i 9.5 Adicionar uma palavra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 9.6 Remover uma palavra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.7 Verificar se uma palavra está ou não no Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.8 Recuperar todas as palavras do Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 9.9 Informar o tamanho do Conjunto de palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 9.10 Exercícios: Tabela de Espalhamento 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 9.11 Diminuindo Colisões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 9.12 Espalhando Melhor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 9.13 Exercícios: Tabela de Espalhamento 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 9.14 Tabela Dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9.15 Exercícios: Tabela de Espalhamento 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 9.16 Generalização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 9.17 equals e hashCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 9.18 Parametrizando o Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.19 API do Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9.20 Exercícios: Tabela de Espalhamento 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 10 Armazenamento Associativo 117 10.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.2 Mapa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 10.3 Exercícios: Armazenamento Associativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 11 Mapas com Lista 120 11.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11.2 Operações em mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11.3 Adicionar uma associação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 11.4 Recuperar o valor associado a uma dada chave . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 11.5 Remover a associação que contem uma determinada chave . . . . . . . . . . . . . . . . . . . . . 121 11.6 Verificar se uma dada chave está em alguma associação . . . . . . . . . . . . . . . . . . . . . . 122 11.7 Informar o tamanho do Mapa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 11.8 Exercícios: Mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 iv 12 Mapas com Espalhamento 125 12.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 12.2 Operações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12.3 Verificando se uma chave existe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12.4 Removendo uma associação dado uma chave . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12.5 Adicionando uma associação dado uma chave . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 12.6 Recuperando o valor associado a uma determinada chave . . . . . . . . . . . . . . . . . . . . . . 127 12.7 Performance das operações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 12.8 Generalização e Parametrização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 12.9 API do Java . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Versão: 9.7.19 v CAPÍTULO 1 Prefácio Este material foi escrito por Paulo Eduardo Azevedo Silveira e Rafael Antonio Cosentino para ser utilizado no curso de verão Introdução a Estrutura de dados e Algoritmos em Java, do Instituto de Matemática e Estatística da Universidade de São Paulo. Paulo Silveira é bacharel e mestre em ciência da computação pelo Instituto de Matemática e Estatística da Universidade de São Paulo (IME-USP). É um dos fundadores do Grupo de Usuários Java (http://www.guj. com.br) e trabalha atualmente na Caelum (http://www.caelum.com.br). Rafael Cosentino é bacharel em ciência da computação pelo Instituto de Matemática e Estatística da Uni- versidade de São Paulo (IME-USP), é mestrando em Ciência da Computação também pelo IME-USP e trabalha atualmente na Caelum. As experiências como alunos e professores mostrou aos autores desta apostila os principais pontos de dificuldades no aprendizado. Isso motivou uma abordagem um pouco diferente para esta apostila em relação ao que é comum na maioria dos livros sobre o assunto A cada capítulo, apresentaremos diversos problemas que servirão de motivação para os principais conceitos de estrutura de dados. Os exercícios complementarão o apredizado pois ajudam a fixar os conceitos vistos na apostila e estimulam o aluno para conceitos avançados que fogem do escopo deste material. Além disso, no fim de cada capítulo, apresentaremos as bibliotecas do Java que modelam as estruturas de dados apresentadas nesta apostila. 1 Material do Treinamento Algoritmos e Estruturas de Dados em Java A única coisa que precisa ser mostrada para o usuário são as operações que ele pode fazer na agenda (inserir, recuperar, atualizar, remover contato, saber quantos contatos estão na agenda, etc). Este conjunto de operações é a interface que o usuário tem com a agenda. Cada celular pode implementar a sua agenda de contatos de uma forma totalmente diferente um do outro, na tentativa de obter mais performance, ser mais confiável ou gastar menos memória. Porém o conjunto básico de operações oferecidas pelas agendas é sempre o mesmo. Isso facilita a vida do usuário pois se ele tiver que trocar de celular não vai ter que aprender novamente como usar uma agenda de contatos. Essa é a grande vantagem em se pensar em interface. Mantida a interface, podemos trocar uma agenda que não é tão eficiente ou que já não atende mais as nossas necessidades por outra mais eficiente ou adequada, sem problemas em ter de aprender a usar a nova agenda: troca-se a implementação, mas não mudamos a interface. Uma agenda de celular pode ser vista como uma estrutura de dados. Uma estrutura de dados mantém os dados organizados seguindo alguma lógica e disponibiliza operações para o usuário manipular os dados. É importante, quando programar, não misturar dado e estrutura de dados em uma coisa só. Um dado é uma informação armazenada e estrutura de dados é quem administra os dados. O ideal é que a estrutura de dados seja o mais independente possível dos dados que ela vai armazenar. Desta forma pode-se aproveitar a mesma estrutura de dados para diversos tipos de dados. Por exemplo, é melhor ter uma agenda genérica do que uma agenda de telefones. Uma agenda genérica pod ser utilizada para guardar telefones, ou emails, ou até mesmo guardar uma outra estrutura dentro dela: contatos, que seriam compostos por nome, telefone e email. Algumas estruturas de dados são apenas agrupamentos de dados sem um objetivo de aplicar algum algo- ritmo ou tirar proveito de sua estrutura. Um exemplo seria a estrutura Contato. Algumas outras estruturas são mais espertas e trabalhosas, como a Agenda, assim como Listas Ligadas, Vetores, Tabelas de Espalhamento e outras que veremos no decorrer do texto. Estas estruturas, por sua característica mais complexa e de poder ser reutilizada em outros contextos, devem ser criadas da forma mais independente possível dos dados que estarão dentro dela. Em outras palavras, não devemos misturar a Agenda e o Contato de maneira rígida, para que com isso possamos criar outras Agendas, como por exemplo uma Agenda de Fornecedor. 2.4 - Sobre este texto Este texto vai mostrar a você diversas estruturas de dados, suas vantagens e desavantagens, assim como suas implementações básicas e classes já existentes na bibilioteca padrão do Java. Vamos usar recursos do Java como interfaces, generics, exceptions, pacotes e outros. É bom já ter um conhecimento razoável da linguagem e um pouco de orientação a objetos. Capítulo 2 - Introdução - Sobre este texto - Página 4 CAPÍTULO 3 Armazenamento Sequencial “A morte do homem começa no instante em que ele desiste de aprender” – Albino Teixeira 3.1 - Motivação Todo mundo já experimentou sopa de letrinhas quando criança. Aliás, quando as crianças tomam sopa de letrinhas, elas ficam muito mais interessadas em formar as palavras do que em tomar a sopa. O que chama mais a atenção é que nesta brincadeira de criança aparece um conceito bem interessante de estrutura de dados. Quando a sopa é servida, as letras estão todas espalhadas sem ordem alguma e sem nenhum significado. Quando você escolhe um grupo de letras e as coloca em seqüência formando uma palavra, este grupo de letras ganha um valor semântico, ou seja, ganha um significado. O grupo de letrinhas que você escolhe para formar uma palavra pode conter letras repetidas sem problema nenhum. A única regra é que as letras postas em seqüência devem formar uma palavra existente em alguma língua. Fig.: Sopa de Letrinhas As músicas também são exemplos em que a definição de uma seqüência dos elementos agrega valor semântico. Uma música é composta de notas musicais. Quando estas notas estão “espalhadas”, elas não sigi- nificam muita coisa. Já quando colocadas em uma seqüência adequada, formam uma música que as pessoas podem apreciar. Além disso, uma mesma nota musical pode aparecer mais de uma vez em uma única música. 5 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Música Outro exemplo em que a seqüência dos elementos é importante são as rotas de avião. Imagine o nome de várias cidades sem nehuma ordem. Desta maneira, estes nomes não significam muita coisa. Mas, se eles forem colocados em alguma seqüência então poderiam formar a rota de uma aeronave. Fig.: Rota de avião 3.2 - O problema da listagem de alunos Uma certa instituição de ensino está incentivando os seus alunos a participarem de eventos acadêmicos em troca de créditos para obter desconto nas mensalidades. Para participar, o aluno deve comparecer em algum dos eventos cadastrados na instituição e depois escrever um relatório sobre o conteúdo apresentado no evento. Este relatório será avaliado por um professor e receberá uma pontuação de 0 a 100. A instituição quer manter uma listagem dos alunos que entregaram relatórios. Cada relatório entregue por um aluno corresponde a uma entrada na lista. Então, os alunos que entregarem mais de um relatório irão aparecer mais de uma vez na listagem. Capítulo 3 - Armazenamento Sequencial - O problema da listagem de alunos - Página 6 Material do Treinamento Algoritmos e Estruturas de Dados em Java Seria interessante que a Lista tivesse também uma operação Para verificar se um dado elemento está contido na Lista. Por fim, uma operação que será bastante útil é uma que informe a quantidade de elementos da Lista. Uma vez definidas todas as operações temos então a interface de uso da nossa estrura de dados. Interface da Lista: 1) Adiciona um dado elemento no fim da Lista. 2) Adiciona um dado elemento em um dada posição. 3) Pega o elemento de uma dada posição. 4) Remove o elemento de uma dada posição. 5) Verifica se um dado elemento está contido na Lista. 6) Informa a quantidade de elementos da Lista. Um fato bem interessante que ocorre quando programamos pensando primeiro na interface, como estamos fazendo aqui, é que após a definicão da interface já sabemos como usar a estrutura que ainda nem desenvol- vemos. Se sabemos como usar a estrutura já sabemos como testá-la. Estes testes poderão ser executados durante o desenvolvimento e não somente no fim. Isso é interessante pois possibilita a eliminar erros mais rápido, logo que eles apareçem, e pode evitar erros em cascata (erros que são causados por outros erros). 3.4 - Modelagem Queremos desenvolver um sistema para resolver o problema da listagem de alunos. Este sistema deve ser orientado a objetos e deve de alguma forma representar os alunos. Em um sistema orientado a OBJETOS, um aluno será representado por um objeto. Para criar objetos, precisamos definir como ele deve ser e o que ele deve fazer, ou seja, devemos criar uma “receita de construir objetos”. Em termos técnicos esta “receita” é uma Classe. public class Aluno { private String nome; public String getNome() { return nome; } public void setNome(String nome) { this.nome = nome; } public String toString() { return this.nome; } Capítulo 3 - Armazenamento Sequencial - Modelagem - Página 9 Material do Treinamento Algoritmos e Estruturas de Dados em Java public boolean equals(Object o) { Aluno outro = (Aluno)o; return this.nome.equals(outro.nome); } } Com a classe Aluno, o sistema é capaz de criar objetos para representar os alunos da instituição. Teremos apenas alguns poucos atributos nessa classe, e alguns pares de getters e setters. Vale lembrar que não é boa prática ter classes que apenas carregam dados: seria mais interessante que Aluno também tivesse métodos de negócio. Perceba que reescrevemos os métodos toString() e equals(Object). O primeiro será útil para imprimir os alunos na tela. O segundo servirá para comparar dois objetos do tipo Aluno, o critério de comparação será os nomes dos alunos. Devemos tomar cuidado no método equals(Object) pois estamos correndo o risco de dois tipos de erro. O primeiro acontece quando a referência recebida no parâmetro não está apontando para um objeto do tipo Aluno. O segundo ocorre quando ou a referência do parâmetro é null ou o atributo nome está null. 3.5 - Exercícios: Armazenamento 1) Crie um projeto no eclipse chamado ed. Não esqueça de selecionar a opção que separa o código fonte do binário. 2) Crie um pacote no projeto ed com o nome br.com.caelum.ed. 3) Faça a classe Aluno no pacote br.com.caelum.ed para poder criar objetos que representarão os alunos. Capítulo 3 - Armazenamento Sequencial - Exercícios: Armazenamento - Página 10 CAPÍTULO 4 Vetores “A melhor maneira de fugir do seu problema é resolvê-lo” – Robert Anthony Vamos implementar uma Lista para resolver o problema da listagem de alunos. Lembrando que a inter- face da Lista já foi definida no capítulo de armazenamento sequencial, seguem as operações que devemos implementar: 1) Adiciona um dado aluno no fim da Lista. 2) Adiciona um dado aluno em uma dada posição. 3) Pega o aluno de dada posicão. 4) Remove o aluno de dada posicão. 5) Verifica se um dado aluno está armazenado. 6) Informa o número de alunos armazenados. Ainda falta definir como os alunos serão armazenados. Como queremos manter muitos alunos vamos alocar um grande espaço de memória sequencial com capacidade para guardar uma certa quantidade de alunos, talvez 100 alunos por enquanto seja razoável. Para facilitar o acesso aos alunos, dividiremos o espaço de memória alocado em pequenos pedaços idênti- cos. Cada pedaço armazenará um aluno. Além disso, vamos indexar (numerar) os pequenos pedaços para ser fácil recuperar um aluno. Fig.: Array Praticamente todas as linguagens de programação têm um recurso similar ao que descrevemos acima. Em Java, este recurso é chamado de Array. Um array é uma porção de memória fixa e sequencial dividida em pedaços idênticos indexados a partir do 0. Em cada posição do array, podemos guardar um aluno. Na verdade, cada posição pode guardar uma referência para um objeto do tipo Aluno. A capacidade de um array é fixa e deve ser informada no momento da criação do array. Não é possível redimensionar um array em Java, teremos de contornar isso mais adiante. 11 Material do Treinamento Algoritmos e Estruturas de Dados em Java } } Saída: [Paulo, Ana, Rafael] Pegar um aluno por posição Teste: public class TestePegaPorPosicao { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); lista.adiciona(a1); lista.adiciona(a2); Aluno aluno1 = lista.pega(0); Aluno aluno2 = lista.pega(1); System.out.println(aluno1); System.out.println(aluno2); } } Saída: Rafael Paulo Remover um aluno por posição Teste: public class TesteRemovePorPosicao { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); Capítulo 4 - Vetores - Os testes primeiro - Página 14 Material do Treinamento Algoritmos e Estruturas de Dados em Java lista.adiciona(a1); lista.adiciona(a2); lista.remove(0); System.out.println(lista); } } Saída: [Paulo] Verificar se a lista contem um dado aluno Teste: public class TesteContemAluno { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); lista.adiciona(a1); lista.adiciona(a2); System.out.println(lista.contem(a1)); System.out.println(lista.contem(a2)); Aluno aluno = new Aluno(); aluno.setNome("Ana"); System.out.println(lista.contem(aluno)); } } Saída: true true false Informar o tamanho da lista Teste: Capítulo 4 - Vetores - Os testes primeiro - Página 15 Material do Treinamento Algoritmos e Estruturas de Dados em Java public class TesteTamanhoLista { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); Aluno a3 = new Aluno(); a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); lista.adiciona(a1); lista.adiciona(a2); System.out.println(lista.tamanho()); lista.adiciona(a3); System.out.println(lista.tamanho()); } } Saída: 2 3 Estes testes podem ser rodados a medida que preenchemos nosso Vetor com sua respectiva implementa- ção. Em uma aplicação profissional Java, criaríamos testes unitários, utilizando bibliotecas auxiliares, como JUnit ou TestNG, para faciliar a escrita destes mesmos testes. O desenvolvimento dirigido a testes (Test Driven Devlopment, TDD) é uma prática que ganha cada vez mais força, onde escreveríamos primeiro os testes das nossas classes, antes mesmo de começar a escrever a sua classe. O intuito disso é que você acaba apenas criando as classes e os métodos que realmente necessita, e eles já estão testados! O design da classe também costuma sair mais simples, pois uma classe com muitas dependências e acoplamento é difícil ser testada. 4.2 - Operações em vetores Na seqüência, implementaremos cada uma das operações de uma Lista. 4.3 - Adicionar no fim da Lista Esta operação receberá um aluno e irá guardá-lo no fim da Lista. Então, precisamos saber onde é o fim da Lista. A dificuldade em descobrir a última posição depende de como os alunos serão armazenados no array. Há duas possibilidades: ou guardamos os alunos compactados a esquerda do array ou não. No primeiro caso, será bem mais fácil achar a última posição da Lista. Além disso, o índice do array será o mesmo índice da Lista. Capítulo 4 - Vetores - Operações em vetores - Página 16 Material do Treinamento Algoritmos e Estruturas de Dados em Java } Agora, o consumo de tempo do método é sempre o mesmo não importa quantos alunos estejam armazena- dos. Neste caso, dizemos que o consumo é constante. Fig.: Consumo Linear VS Consumo Constante Um ponto interessante de enxergar aqui é que modificamos nossa implementação sem alterar nossa inter- face, e conseguimos deixar o método adiciona mais rápido. Com isso, se alguém já estivesse usando nossa classe Vetor antiga, poderia substituir pela nova sem alterar nenhuma outra linha de código. Se o acesso a nossa array fosse público, teríamos problemas nos códigos das pessoas que estão usando a nossa classe. Graças ao encapsulamento e a boa definição de nossa interface, evitamos ter de reescrever uma quantidade grande de código. Para verificar se o método continua funcionando devemos executar novamente o TesteAdicionaNoFim. 4.4 - O método toString() para o Vetor Vamos reescrever o método toString() para visualizar facilmente o conteúdo da Lista. Utilizamos a classe StringBuilder para construir a String que mostrará os elementos da Lista. public String toString() { if (this.totalDeAlunos == 0) { return "[]"; } StringBuilder builder = new StringBuilder(); builder.append("["); for (int i = 0; i < this.totalDeAlunos - 1; i++) { builder.append(this.alunos[i]); builder.append(", "); } Capítulo 4 - Vetores - O método toString() para o Vetor - Página 19 Material do Treinamento Algoritmos e Estruturas de Dados em Java builder.append(this.alunos[this.totalDeAlunos - 1]); builder.append("]"); return super.toString(); } 4.5 - Informar o tamanho da Lista Esta operação ficou muito simples de ser implementada porque a classe Vetor tem um atributo que guarda a quantidade de alunos armazenados. Então, basta devolver o valor do totalDeAlunos. Perceba que o consumo de tempo será constante: não há laços. public class Vetor { ... private int totalDeAlunos = 0; ... public int tamanho() { return this.totalDeAlunos; } } Se não tivessemos criado o atributo totalDeAlunos o método tamanho() teria que fazer um laço para percor- rer o array inteiro e contar quantas posições estão ocupadas. Ou seja, o desempenho seria linear que é muito pior que constante. Não podemos esquecer de rodar o teste para o tamanho da Lista. 4.6 - Verificar se um aluno está presente no vetor Nesta operação, precisamos comparar o aluno dado com todos os alunos existentes na Lista. Para imple- mentar esta funcionalidade faremos um laço. public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public boolean contem(Aluno aluno) { for (int i = 0; i < this.alunos.length; i++) { if (aluno == this.alunos[i]) { return true; } } return false; } } Capítulo 4 - Vetores - Informar o tamanho da Lista - Página 20 Material do Treinamento Algoritmos e Estruturas de Dados em Java Neste método, se o aluno procurado for encontrado então o valor true é devolvido. Se a array acabar e o aluno não for encontrado, significa que ele não está armazenado logo o método deve devolver falso. A capacidade do array é obtida pelo atributo length. O nosso método é ineficiente quando a Lista tem poucos elementos. Perceba que ele sempre percorre o array todo. Não é necessário percorrer o array inteiro basta percorrer as posições ocupadas, ou seja, o laço tem que ir até a última posição ocupada. Nós podemos obter a última posição ocupada através do atributo totalDeAlunos. public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public boolean contem(Aluno aluno) { for (int i = 0; i < this.totalDeAlunos; i++) { if (aluno == this.alunos[i]) { return true; } } return false; } } Nós estamos comparando os alunos com o operador ==. Este operador compara o conteúdo das variáveis. No Java, as variáveis de tipos não primitivos, como o tipo Aluno, guardam referências para objetos. Então, na verdade, estamos comparando a referências e não os objetos propriamente. Para comparar objetos devemos usar o método equals(Object). Lembrando que reescrevemos este método para considerar que dois objetos do tipo Aluno são iguais quando os seus atributos nome são iguais. public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public boolean contem(Aluno aluno) { for (int i = 0; i < this.totalDeAlunos; i++) { if (aluno.equals(this.alunos[i])) { return true; } } return false; } } Aqui deveríamos executar o teste do contem. Capítulo 4 - Vetores - Verificar se um aluno está presente no vetor - Página 21 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Posições válidas Após verificar se podemos adicionar o aluno na posição dada, devemos tomar cuidado para não colocar um aluno sobre outro. É preciso deslocar todos os alunos a “direita” da posição onde vamos inserir uma vez para a “frente”. Isso abrirá um espaço para guardar a referência para o aluno novo. Fig.: Deslocamento para a direita public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public void adiciona(int posicao, Aluno aluno) { if (!this.posicaoValida(posicao)) { throw new IllegalArgumentException("Posicao inválida"); } for (int i = this.totalDeAlunos - 1; i >= posicao; i) { this.alunos[i + 1] = this.alunos[i]; } this.alunos[posicao] = aluno; this.totalDeAlunos++; } private boolean posicaoValida(int posicao) { return posicao >= 0 && posicao <= this.totalDeAlunos; } } Quanto este método consome de tempo? Depende! Se for a última posição, consumirá tempo contante. No caso de ser a primeira posição, ele terá de deslocar todos os elementos para a direita, consumindo tempo linear em relação ao número de elementos distantes. É comum calcularmos o tempo consumido de um método pensando sempre no pior caso, então diremos que o método que adiciona em qualquer posição de nosso Vetor consome tempo linear. Agora é um ótimo momento para testar. Podemos rodar o teste de adicionar por posição. Capítulo 4 - Vetores - Adicionar um aluno em uma determinada posição do array - Página 24 Material do Treinamento Algoritmos e Estruturas de Dados em Java 4.9 - Remover um aluno de uma dada posição Inicialmente, precisamos verificar se a posição está ocupada ou não. Afinal, não faz sentido remover algo que não existe. Para saber se a posição está ocupada ou não podemo usar o método posicaoOcupada(int). Se a posição estiver ocupada então podemos remover o aluno. Além disso, precisamos deslocar os alunos que estavam a direita daquele que removemos uma vez para esquerda para fechar o “buraco” aberto pela remoção. Fig.: Deslocamento para a esquerda public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public void remove(int posicao) { if (!this.posicaoOcupada(posicao)) { throw new IllegalArgumentException("Posicao inválida"); } for (int i = posicao; i < this.totalDeAlunos - 1; i++) { this.alunos[i] = this.alunos[i + 1]; } this.totalDeAlunos; } private boolean posicaoOcupada(int posicao) { return posicao < this.alunos.length && posicao >= 0; } } Você sabe dizer quanto tempo este método consome? E agora falta executar o teste para esta operação. Capítulo 4 - Vetores - Remover um aluno de uma dada posição - Página 25 Material do Treinamento Algoritmos e Estruturas de Dados em Java 4.10 - Alocação Dinâmica Há um grande problema na implementação apresentada até o momento. Imagine que o vetor já contenha 100 alunos. Ao adicionar mais um aluno ocorreria um erro pois o array foi criado com 100 posições e o método adiciona() tentaria inserir um aluno em uma posição que não existe: o java lançará um exceção. Para resolver isso, podemos tentar inicializar o array com um tamanho maior. Isso não resolveria problema. Por exemplo, se o tamanho da array fosse 200 em vez de 100, no momento que fosse inserido o aluno número 201, ocorreria novamente um erro. Uma abordagem mais eficiente seria cada vez que o array ficar cheio alguma providência seja tomada, como, por exemplo, dobrar o tamanho dele. Vamos criar um método que tem como tarefa verificar se o array está cheio. Caso estiver cheio, ele criará um novo array com o dobro do tamanho do antigo e moverá os alunos do array antigo para o novo. public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... private void garantaEspaco() { if (this.totalDeAlunos == this.alunos.length) { Aluno[] novaArray = new Aluno[this.alunos.length * 2]; for (int i = 0; i < this.alunos.length; i++) { novaArray[i] = this.alunos[i]; } this.alunos = novaArray; } } } O risco de tentar adicionar um aluno sem ter posição disponível só ocorre, evidentemente, nos métodos de adicionar aluno. Então, para evitar este problema, vamos verificar se existe espaço disponível antes de adicionar um aluno. public class Vetor { private Aluno[] alunos = new Aluno[100]; private int totalDeAlunos = 0; ... public void adiciona(Aluno aluno) { this.garantaEspaco(); this.alunos[this.totalDeAlunos] = aluno; this.totalDeAlunos++; } public void adiciona(int posicao, Aluno aluno) { this.garantaEspaco(); if (!this.posicaoValida(posicao)) { throw new IllegalArgumentException("Posicao inválida"); } Capítulo 4 - Vetores - Alocação Dinâmica - Página 26 Material do Treinamento Algoritmos e Estruturas de Dados em Java // Inserindo uma String lista.adiciona("Rafael"); // Fazendo um casting de String para Aluno. Erro de EXECUÇÃO. Aluno aluno = (Aluno)lista.pega(0); Existe uma outra maneira de fazer a mesma classe sem essa desvantagem de usar castings, que é criar uma classe parametrizada, um recurso existente no Java a partir da versão 5. 4.12 - API do Java Na biblioteca do Java, há uma classe que implementa a estrutura de dados que foi vista neste capítulo, esta classe chama-se ArrayList e será testada pelo código abaixo. public class Teste { public static void main(String[] args) { ArrayList vetor = new ArrayList(); Aluno aluno1 = new Aluno(); Aluno aluno2 = new Aluno(); Aluno aluno3 = new Aluno(); vetor.add(aluno1); vetor.add(aluno2); vetor.add(0, aluno3); int tamanho = vetor.size(); if (tamanho != 3) { System.out.println("Erro: O tamanho da lista está errado."); } if (!vetor.contains(aluno1)) { System.out .println("Erro: Não achou um aluno que deveria estar na lista"); } vetor.remove(0); tamanho = vetor.size(); if (tamanho != 2) { System.out.println("Erro: O tamanho da lista está errado."); } if (vetor.contains(aluno3)) { System.out .println("Erro: Achou um aluno que não deveria estar na lista"); } } } Capítulo 4 - Vetores - API do Java - Página 29 Material do Treinamento Algoritmos e Estruturas de Dados em Java A classe Vector é muito similar a ArrayList, a grande diferença é que ArrayList não é segura para ser compartilhada entre várias threads simultâneamente sem o devido cuidado. Dizemos que Vector é thread safe, mas isso tem um custo, e é por isso que evitamos usar Vector e preferimos usar ArrayList sempre que possível. Para evitar fazer casting de objetos, podemos utilizar o recurso de generics do Java 5. A utilização de generics é bem simples, a gente deve informar que o nossa Lista irá guardar alunos. Isso é feito como mostra o código a seguir: public class Teste { public static void main(String[] args) { ArrayList vetorSemGenerics = new ArrayList(); ArrayList<Aluno> vetorComGenerics = new ArrayList<Aluno>(); Aluno aluno = new Aluno(); vetorSemGenerics.add(aluno); vetorComGenerics.add(aluno); Aluno a1 = (Aluno) vetorSemGenerics.get(0); Aluno a2 = vetorComGenerics.get(0); } } Com o generics temos uma segurança em tempo de compilação em relação a tipagem dos objetos. Se tentarmos adicionar um objeto que não é do tipo Aluno um erro de compilação acontecerá. ArrayList<Aluno> vetorComGenerics = new ArrayList<Aluno>(); vetorComGenerics.add("Rafael"); // erro de compilação Qual a vantagem de um erro de compilação sobre um erro de execução? O de execução acontece quando o usuário está do lado do computador. O de compilação acontece quando o programador está no computador. 4.13 - Exercícios: Vetores 1) Crie a classe Vetor no pacote br.com.caelum.ed.vetores com as assinaturas dos métodos vistos neste capítulo e com um atributo do tipo array de Aluno inicializado com 100000 posições. package br.com.caelum.ed.vetores; import br.com.caelum.ed.Aluno; public class Vetor { // Declarando e Inicializando um array de Aluno com capacidade 100. private Aluno[] alunos = new Aluno[100000]; public void adiciona(Aluno aluno) { // implementação } public void adiciona(int posicao, Aluno aluno) { Capítulo 4 - Vetores - Exercícios: Vetores - Página 30 Material do Treinamento Algoritmos e Estruturas de Dados em Java // implementação } public Aluno pega(int posicao) { // implementação return null; } public void remove(int posicao) { // implementação } public boolean contem(Aluno aluno) { // implementação return false; } public int tamanho() { // implementação return 0; } } 2) Escreva os testes unitários vistos neste capítulo. Coloque os testes no pacote br.com.caelum.ed.vetores.testes. Teste: public class TesteAdicionaNoFim { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); lista.adiciona(a1); lista.adiciona(a2); System.out.println(lista); } } Saída: [Rafael, Paulo] Teste: public class TesteAdicionaPorPosicao { public static void main(String[] args) { Aluno a1 = new Aluno(); Aluno a2 = new Aluno(); Aluno a3 = new Aluno(); Capítulo 4 - Vetores - Exercícios: Vetores - Página 31 Material do Treinamento Algoritmos e Estruturas de Dados em Java a1.setNome("Rafael"); a2.setNome("Paulo"); Vetor lista = new Vetor(); lista.adiciona(a1); lista.adiciona(a2); System.out.println(lista.tamanho()); lista.adiciona(a3); System.out.println(lista.tamanho()); } } Saída: 2 3 3) Uma vez definida a interface do Vetor poderíamos programar os testes. Para os testes vamos reescrever o toString(). public String toString() { if (this.totalDeAlunos == 0) { return "[]"; } StringBuilder builder = new StringBuilder(); builder.append("["); for (int i = 0; i < this.totalDeAlunos - 1; i++) { builder.append(this.alunos[i]); builder.append(", "); } builder.append(this.alunos[this.totalDeAlunos - 1]); builder.append("]"); return super.toString(); } 4) Implemente o método adiciona(Aluno) da primeira maneira vista neste capítulo. public void adiciona(Aluno aluno) { for (int i = 0; i < this.alunos.length; i++) { if (this.alunos[i] == null) { this.alunos[i] = aluno; break; } } } Capítulo 4 - Vetores - Exercícios: Vetores - Página 34 Material do Treinamento Algoritmos e Estruturas de Dados em Java Faça um teste para calcular o tempo gasto. Este teste deve adicionar 100000 alunos. Execute e marque o tempo. package br.com.caelum.ed.vetores; import br.com.caelum.ed.Aluno; public class TesteLinearVSConstante { public static void main(String[] args) { Vetor vetor = new Vetor(); long inicio = System.currentTimeMillis(); for (int i = 1; i < 100000; i++) { Aluno aluno = new Aluno(); vetor.adiciona(aluno); } long fim = System.currentTimeMillis(); double tempo = (fim - inicio) / 1000.0; System.out.println("Tempo em segundos = " + tempo); } } Implemente o método adiciona(Aluno) da segunda maneira vista neste capítulo. Não esqueça de acres- centar o atributo totalDeAlunos. public class Vetor { private Aluno[] alunos = new Aluno[100000]; private int totalDeAlunos = 0; public void adiciona(Aluno aluno) { this.alunos[this.totalDeAlunos] = aluno; this.totalDeAlunos++; } } Execute a classe TesteLinearVSConstante e veja o tempo agora. A diferença de tempo é bem considerável. 5) Implemete o método tamanho() na classe Vetor como visto neste capítulo. public int tamanho() { return this.totalDeAlunos; } Execute o teste apropriado feito anteriormente. 6) Implemente o método contem() na classe Vetor da primeira maneira mostrada neste capítulo. public boolean contem(Aluno aluno) { for (int i = 0; i < this.alunos.length; i++) { if (aluno == this.alunos[i]) { return true; } } return false; Capítulo 4 - Vetores - Exercícios: Vetores - Página 35 Material do Treinamento Algoritmos e Estruturas de Dados em Java } Verifique este método com o teste do contem aluno. Faça outro teste para calcular o tempo gasto. package br.com.caelum.ed.vetores; import br.com.caelum.ed.Aluno; public class TesteDeTempoDoContem { public static void main(String[] args) { Vetor vetor = new Vetor(); long inicio = System.currentTimeMillis(); // Adicionado 100000 alunos e // Verificando se eles foram realmente adicionados. for (int i = 1; i < 30000; i++) { Aluno aluno = new Aluno(); vetor.adiciona(aluno); if(!vetor.contem(aluno)){ System.out.println("Erro: aluno " + aluno + " não foi adicionado."); } } // Verificando se o Vetor não encontra alunos não adicionados. for (int i = 1; i < 30000; i++) { Aluno aluno = new Aluno(); if(vetor.contem(aluno)){ System.out.println("Erro: aluno " + aluno + " foi adicionado."); } } long fim = System.currentTimeMillis(); double tempo = (fim - inicio) / 1000.0; System.out.println("Tempo = " + tempo); } } Implemente o método contem() na classe Vetor da segunda maneira mostrada neste capítulo. public boolean contem(Aluno aluno) { for (int i = 0; i < this.totalDeAlunos; i++) { if (aluno == this.alunos[i]) { return true; } } return false; } Execute o teste novamente e veja a diferença de tempo. 7) Implemente o método pega(int) na classe Vetor da primeira maneira vista neste capítulo. public Aluno pega(int posicao) { return this.alunos[posicao]; } Capítulo 4 - Vetores - Exercícios: Vetores - Página 36 Material do Treinamento Algoritmos e Estruturas de Dados em Java 12) Utilize a classe Vetor que foi implementada nos exercícios anteriores e as classes da API do Java Vector ou ArrayList. Para saber os métodos das classes da API, utilize a documentação do Java (http://java.sun. com/j2se/1.5.0/docs/api/index.html). 1) Crie um vetor usando a classe Vetor; guarde nele 1000 alunos; 2) Imprima o tamanho do vetor antes e depois de adicionar os 1000 alunos. 3) Crie um vetor usando a classe Vector; passe os alunos do vetor anterior para este novo vetor; imprima o tamanho do novo vetor antes e depois de adicionar os alunos. 4) Crie um vetor usando a classe \classe{ArrayList}; passe os alunos do vetor criado no item anterior para este novo vetor; imprima o tamanho do novo vetor antes e depois de adiciomar os alunos. 4.14 - Exercícios opcionais 1) Use o recurso de generics do Java 5 e crie um Vetor usando a classe ArrayList para guardar objetos do tipo String. Teste adicionar neste vetor algumas Strings; e também tente adicionar Alunos (O que acontecerá quando você tentar adicionar alunos?). Retire elementos deste vetor (você presisa fazer casting para String nestes elementos?). 2) Acrescente uma operação na Lista, para isso, implemente um novo método. A nova operação deve remover da Lista todas as ocorrências de um elemento que é passado com parametro. Não esqueça de rearranjar os elementos do vetor após a remoção. public void remove(Object objeto) { // implementação } 3) Acrescente uma operação na Lista, para isso, implemente um novo método. A nova operação deve limpar a lista, ou seja, remover todos os elementos. public void clear() { // implementação } 4) Acrescente uma operação na Lista, para isso, implemente um novo método. A nova operação deve procurar o índice da primeira ocorrência de um elemento passado como parâmetro. public void indexOf(Object objeto) { // implementação } 5) Acrescente uma operação na Lista, para isso, implemente um novo método. A nova operação deve procurar o índice da última ocorrência de um elemento passado como parâmetro. public void lastIndexOf(Object objeto) { // implementação } 6) (Desafio) Pesquise sobre análise amortizada para saber porque é mais eficiente dobrar a capacidade da array quando o vetor fica cheio. A outra opção seria incrementar. Por exemplo, quando acaba o espaço na Capítulo 4 - Vetores - Exercícios opcionais - Página 39 Material do Treinamento Algoritmos e Estruturas de Dados em Java array, criaríamos uma com o mesmo tamanho + 10. É incrível a diferença de uma estratégia e de outra, ao você tentar adicionar uma enorme quantidade de elementos. Capítulo 4 - Vetores - Exercícios opcionais - Página 40 CAPÍTULO 5 Listas Ligadas “É impossível para um homem aprender aquilo que ele acha que já sabe” – Epíteto Vetores (listas implementadas com array) são uma excelente alternativa ao uso direto de arrays em Java, porém para algumas tarefas eles podem não ser eficientes, justamente por esse fato. Adicionar um elemento na primeira posição de um Vetor, por exemplo, consome muito tempo, pois temos de deslocar todos os outros elementos uma posição para a frente. A performance dessa operação degrada a medida que a quantidade de elementos do nosso vetor cresce: ela consome tempo linear em relação ao número de elementos. Analogamente, remover um elemento da primeira posição implica em deslocar todos os outros elementos que estão na sua frente para tras. Em alguns casos, queremos uma implementação de Lista na qual a operação de adicionar ou a de remover um aluno na primeira posição seja computacionalmente eficiente. Conseguiremos isso através de uma Lista Ligada1. Esta estrutura que vamos criar terá a inserção e remoção nas “pontas” da lista computacionalmente eficien- tes. Lembrando que as operações da Lista para o nosso sistema de gerenciamento de alunos são: 1) Adiciona um dado aluno no fim da Lista. 2) Adiciona um dado aluno em uma dada posição. 3) Pega o aluno de dada posicão. 4) Remove o aluno de dada posicão. 5) Verifica se um dado aluno está armazenado. 6) Informar o número de alunos armazenados. 1alguns textos se referem a essa estrutura como lista encadeada 41 Material do Treinamento Algoritmos e Estruturas de Dados em Java public void setProxima(Celula proxima) { this.proxima = proxima; } public Celula getProxima() { return proxima; } public Object getElemento() { return elemento; } } Essa classe Celula nunca será acessada diretamente por quem usar a classe ListaLigada, dessa forma estamos escondendo como a nossa classe funciona e garantindo que ninguém mexa na estrutura interna da nossa Lista. A classe ListaLigada possui inicialmente apenas uma referência para a primeira 2 célula e outra para a última. Através da primeira conseguimos iterar até chegar em qualquer posição necessária. Já a referência à úlitma irá facilitar a inserção no fim da Lista. public class ListaLigada { private Celula primeira; private Celula ultima; } 5.3 - Definindo a interface Com as operações definidas podemos esboçar a classe ListaLigada. public class ListaLigada { private Celula primeira; private Celula ultima; public void adiciona(Object elemento) {} public void adiciona(int posicao, Object elemento) {} public Object pega(int posicao) {return null;} public void remove(int posicao){} public int tamanho() {return 0;} public boolean contem(Object o) {return false;} } Estamos discutindo sobre Lista Ligada especialmente porque queremos um tipo de Lista que as operações de adicionar e remover da primeira e da última posição sejam computacionalmente eficientes. Então, vamos acrescentar mais três métodos na classe ListaLigada. 2alguns gostam de denominar essa célula de cabeça da lista Capítulo 5 - Listas Ligadas - Definindo a interface - Página 44 Material do Treinamento Algoritmos e Estruturas de Dados em Java public void adicionaNoComeco(Object elemento) {} public void removeDoComeco() {} public void removeDoFim() {} O método adiciona() insere no fim da Lista então não adicionaremos mais um método para realizar essa mesma tarefa. 5.4 - Testes public class TesteAdicionaNoFim { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona("Paulo"); System.out.println(lista); } } Saída esperada: [Rafael, Paulo] public class TesteAdicionaPorPosicao { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona(0, "Paulo"); lista.adiciona(1, "Camila"); System.out.println(lista); } } Saída esperada: [Paulo, Camila, Rafael] public class TestePegaPorPosicao { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona("Paulo"); System.out.println(lista.pega(0)); System.out.println(lista.pega(1)); } } Saída esperada: Capítulo 5 - Listas Ligadas - Testes - Página 45 Material do Treinamento Algoritmos e Estruturas de Dados em Java Rafael Paulo public class TesteRemovePorPosicao { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona("Paulo"); lista.adiciona("Camila"); lista.remove(1); System.out.println(lista); } } Saída esperada: [Rafael, Camila] public class TesteTamanho { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona("Paulo"); System.out.println(lista.tamanho()); lista.adiciona("Camila"); System.out.println(lista.tamanho()); } } Saída esperada: 2 3 public class TesteContemElemento { public static void main(String[] args) { ListaLigada lista = new ListaLigada(); lista.adiciona("Rafael"); lista.adiciona("Paulo"); System.out.println(lista.contem("Rafael")); System.out.println(lista.contem("Camila")); } } Capítulo 5 - Listas Ligadas - Testes - Página 46 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Os dois casos para adicionar no começo public class ListaLigada { private Celula primeira; private Celula ultima; private int totalDeElementos; public void adicionaNoComeco(Object elemento) { Celula nova = new Celula(this.primeira, elemento); this.primeira = nova; if(this.totalDeElementos == 0){ // caso especial da lista vazia Capítulo 5 - Listas Ligadas - Adicionando no começo da Lista - Página 49 Material do Treinamento Algoritmos e Estruturas de Dados em Java this.ultima = this.primeira; } this.totalDeElementos++; } } 5.7 - Adicionando no fim da Lista Se não tivessemos guardado a referência para a última célula precisaríamos percorrer célula a célula até o fim da Lista para alterar a referência proxima da última célula! Com um grande número de elementos isso ficaria lento, pois leva tempo linear. No caso especial da Lista estar vazia, adicionar no começo ou no fim dessa lista dá o mesmo efeito. Então, se a Lista estiver vazia, chamaremos o método adicionaNoComeco(Object). Fig.: Adicionando no fim public class ListaLigada { private Celula primeira; private Celula ultima; private int totalDeElementos; public void adiciona(Object elemento) { if (this.totalDeElementos == 0) { this.adicionaNoComeco(elemento); } else { Celula nova = new Celula(elemento); this.ultima.setProxima(nova); this.ultima = nova; this.totalDeElementos++; } Capítulo 5 - Listas Ligadas - Adicionando no fim da Lista - Página 50 Material do Treinamento Algoritmos e Estruturas de Dados em Java } } Repare que aqui estamos fazendo que haja n células para n elementos, isto é, uma célula para cada ele- mento. Uma outra implementação clássica de lista ligada é usar uma célula sentinela a mais para indicar o começo da Lista, e outra para o fim, assim poderíamos simplificar um pouco alguns desses métodos, como ocaso particular de inserir um elemento quando não há ainda elemento algum. Vale sempre lembrar que aqui estamos estudando uma implementação de uma estrutura de dados, e que há sempre outras formas de codifica- las, que podem ser mais ou menos elegantes. 5.8 - Percorrendo nossa Lista Para poder rodar alguns testes, precisamos imprimir o conteúdo da nossa Lista. Como ainda não temos como acessar um elemento pela sua posição, vamos reescrever o método toString() da classe ListaLigada para que ele concatene todos os elementos de dentro da Lista Ligada em uma única String. O nosso método utiliza-se de uma referência temporátia para uma célula chamada atual, que vai apontando para a próxima a cada iteração, concatenando o elemento dessa célula: public String toString() { // Verificando se a Lista está vazia if(this.totalDeElementos == 0){ return "[]"; } StringBuilder builder = new StringBuilder("["); Celula atual = primeira; // Percorrendo até o penúltimo elemento. for (int i = 0; i < this.totalDeAlunos - 1; i++) { builder.append(atual.getElemento()); builder.append(", "); atual = atual.getProxima(); } // último elemento builder.append(atual.getElemento()); builder.append("]"); return builder.toString(); } Aqui estamos utilizando a classe StringBuilder que é muito útil para criar Strings potencialmente grandes, em vez de concatenar Strings pelo operador +[label o fato da classe String do java ser imutável acarreta num grande gasto de memória temporária no caso de você concatenas muitas Strings, vale a pena consultar a documentação da mesma][/label]. Também poderíamos ter utilizado um while(atual != null) em vez do for dentro do método toString, que as vezes pode ser mais legível. Capítulo 5 - Listas Ligadas - Percorrendo nossa Lista - Página 51 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Os dois casos de remover do começo public void removeDoComeco() { if (!this.posicaoOcupada(0)) { throw new IllegalArgumentException("Posição não existe"); } this.primeira = this.primeira.getProxima(); this.totalDeElementos; if (this.totalDeElementos == 0) { this.ultima = null; } } Capítulo 5 - Listas Ligadas - Removendo do começo da Lista - Página 54 Material do Treinamento Algoritmos e Estruturas de Dados em Java 5.12 - Removendo do fim da Lista A primeira verificação a ser feita é se a última posição existe. Podemos fazer isso através do método já criado posicaoOcupada(int). Se a Lista estiver com apenas um elemento então remover do fim é a mesma coisa que remover do começo. Logo, podemos reutilizar o método removeDoComeco() para este caso. Agora, se a Lista tem mais que um elemento então devemos pegar a penúltima célula; fazer a próxima da penúltima ser null; e fazer o atributo ultima apontar para a penúltima. O problema aqui é como pegar a penúltima célula. Podemos fazer isso usando o pegaCelula(int) mas isso consumiria tempo linear. Como queremos consumo constate teremos que achar outra solução. Então, em vez de fazer uma Lista Ligada simples vamos fazer uma Lista Duplamente Ligada. Ou seja, cada célula aponta para a sua anterior além de apontar para a próxima: public class Celula { ... private Celula anterior; ... public Celula getAnterior() { return anterior; } public void setAnterior(Celula anterior) { this.anterior = anterior; } } Com cada célula sabendo também quem é a sua anterior, fica fácil escrever o método removeDoFim() Capítulo 5 - Listas Ligadas - Removendo do fim da Lista - Página 55 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Removendo do fim da Lista public void removeDoFim() { if (!this.posicaoOcupada(this.totalDeElementos - 1)) { throw new IllegalArgumentException("Posição não existe"); } if (this.totalDeElementos == 1) { this.removeDoComeco(); } else { Celula penultima = this.ultima.getAnterior(); penultima.setProxima(null); this.ultima = penultima; this.totalDeElementos; } } A modificação para Lista Duplamente Ligada implicará em pequenas modificações nos outros métodos que já tinhamos implementado. As modificações serão apresentadas na seção de Lista Duplamente Ligada. 5.13 - Removendo de qualquer posição Inicialmente, devemos verificar se a posição está ou não ocupada. Se não estiver devemos lançar uma exceção. Caso contrário, devemos verificar se a remoção é do começo ou do fim da Lista se for um destes casos simplesmente chamamos os métodos que já fizemos. Por fim, se a remoção é no interior da Lista devemos atualizar as referências das células relacionadas a célula que vamos remover (anterior e próxima). A próxima da anterior deve ser a proxima e a anterior da proxima deve ser a anterior. Fig.: Removendo do interior da Lista public void remove(int posicao) { if (!this.posicaoOcupada(posicao)) { throw new IllegalArgumentException("Posição não existe"); } if (posicao == 0) { Capítulo 5 - Listas Ligadas - Removendo de qualquer posição - Página 56 Material do Treinamento Algoritmos e Estruturas de Dados em Java this.primeira = nova; this.ultima = nova; } else { Celula nova = new Celula(this.primeira, elemento); this.primeira.setAnterior(nova); this.primeira = nova; } this.totalDeElementos++; } 5.18 - Adicionando no fim da Lista No caso em que a Lista está vazia, adicionar no fim é a mesma coisa que adicionar no começo. Agora, caso a Lista não esteja vazia então devemos ajustar as referências de tal forma que a nova última célula aponte para a nova penúltima (antiga última) e vice versa. Fig.: Adicionado no fim da Lista Duplamente Ligada public void adiciona(Object elemento) { if (this.totalDeElementos == 0) { this.adicionaNoComeco(elemento); } else { Celula nova = new Celula(elemento); this.ultima.setProxima(nova); nova.setAnterior(this.ultima); this.ultima = nova; this.totalDeElementos++; } } Capítulo 5 - Listas Ligadas - Adicionando no fim da Lista - Página 59 Material do Treinamento Algoritmos e Estruturas de Dados em Java 5.19 - Adicionando em qualquer posição da Lista Separamos os casos em que a inserção é no começo ou no fim porque podemos reaproveitar os métodos já implementados. Sobra o caso em que a inserção é no meio da Lista, ou seja, entre duas células existentes. Neste caso, devemos ajustar as referências para a nova célula ser apontada corretamente pela duas células relacionadas a ela (a anterior e a proxima). E também fazer a nova célula apontar para a anterior e a próxima. Fig.: Adicionado no fim da Lista Duplamente Ligada public void adiciona(int posicao, Object elemento) { if(posicao == 0){ // No começo. this.adicionaNoComeco(elemento); } else if(posicao == this.totalDeElementos){ // No fim. this.adiciona(elemento); } else { Celula anterior = this.pegaCelula(posicao - 1); Celula proxima = anterior.getProxima(); Celula nova = new Celula(anterior.getProxima(), elemento); nova.setAnterior(anterior); anterior.setProxima(nova); proxima.setAnterior(nova); this.totalDeElementos++; } } 5.20 - Removendo do começo da Lista Esta operação é idêntica em ambos os tipos de Lista Ligada (simple ou dupla). Ela apenas deve avançar a referência primeira para a segunda célula e tomar cuidado com a caso da Lista ficar vazia pois, neste caso, a Capítulo 5 - Listas Ligadas - Adicionando em qualquer posição da Lista - Página 60 Material do Treinamento Algoritmos e Estruturas de Dados em Java referência ultima deve ser atualizada também. Fig.: Removendo do começo da Lista Duplamente Ligada 5.21 - Removendo do fim da Lista ou de qualquer posição Estas duas operações já foram tratadas e implementadas anteriormente usando o esquema de Lista Dupla- mente Ligada. Capítulo 5 - Listas Ligadas - Removendo do fim da Lista ou de qualquer posição - Página 61 Material do Treinamento Algoritmos e Estruturas de Dados em Java } } 2) Implemente a classe ListaLigada com o “esqueleto” das operações. Utilize o pacote br.com.caelum.ed.listasligadas. package br.com.caelum.ed.listasligadas; public class ListaLigada { private Celula primeira; private Celula ultima; private int totalDeElementos; public void adiciona(Object elemento) { } public void adiciona(int posicao, Object elemento) { } public Object pega(int posicao) { return null; } public void remove(int posicao) { } public int tamanho() { return 0; } public boolean contem(Object o) { return false; } public void adicionaNoComeco(Object elemento) { } public void removeDoComeco() { } public void removeDoFim() { } } 3) Implemente todos os testes feito na seção Teste. Coloque as classes no pacote br.com.caelum.ed.listasligadas. 4) Para testar as operações precisamos reescrever o método toString() para devolver os elementos da Lista em uma String. public String toString() { Capítulo 5 - Listas Ligadas - Exercícios: Lista Ligada - Página 64 Material do Treinamento Algoritmos e Estruturas de Dados em Java // Verificando se a Lista está vazia if(this.totalDeElementos == 0){ return "[]"; } StringBuilder builder = new StringBuilder("["); Celula atual = primeira; // Percorrendo até o penúltimo elemento. for (int i = 0; i < this.totalDeElementos - 1; i++) { builder.append(atual.getElemento()); builder.append(", "); atual = atual.getProxima(); } // último elemento builder.append(atual.getElemento()); builder.append("]"); return builder.toString(); } 5) Implemente todos métodos para a Lista Ligada. A cada método implementado não esqueça de executar o teste apropriado. • Adiciona no começo. public void adicionaNoComeco(Object elemento) { if(this.totalDeElementos == 0){ Celula nova = new Celula(elemento); this.primeira = nova; this.ultima = nova; } else { Celula nova = new Celula(this.primeira, elemento); this.primeira.setAnterior(nova); this.primeira = nova; } this.totalDeElementos++; } • Adiciona no fim. public void adiciona(Object elemento) { if (this.totalDeElementos == 0) { this.adicionaNoComeco(elemento); } else { Celula nova = new Celula(elemento); this.ultima.setProxima(nova); nova.setAnterior(this.ultima); this.ultima = nova; this.totalDeElementos++; } } Capítulo 5 - Listas Ligadas - Exercícios: Lista Ligada - Página 65 Material do Treinamento Algoritmos e Estruturas de Dados em Java • Adiciona em qualquer posição. Esta operação depende do método pegaCelula(int) que por sua vez depende do método posicaoOcupada(int). private boolean posicaoOcupada(int posicao){ return posicao >= 0 && posicao < this.totalDeElementos; } private Celula pegaCelula(int posicao) { if(!this.posicaoOcupada(posicao)){ throw new IllegalArgumentException("Posição não existe"); } Celula atual = primeira; for (int i = 0; i < posicao; i++) { atual = atual.getProxima(); } return atual; } public void adiciona(int posicao, Object elemento) { if(posicao == 0){ // No começo. this.adicionaNoComeco(elemento); } else if(posicao == this.totalDeElementos){ // No fim. this.adiciona(elemento); } else { Celula anterior = this.pegaCelula(posicao - 1); Celula proxima = anterior.getProxima(); Celula nova = new Celula(anterior.getProxima(), elemento); nova.setAnterior(anterior); anterior.setProxima(nova); proxima.setAnterior(nova); this.totalDeElementos++; } } • Remove do começo. public void removeDoComeco() { if (!this.posicaoOcupada(0)) { throw new IllegalArgumentException("Posição não existe"); } this.primeira = this.primeira.getProxima(); this.totalDeElementos; if (this.totalDeElementos == 0) { this.ultima = null; } } • Remove do fim. public void removeDoFim() { if (!this.posicaoOcupada(this.totalDeElementos - 1)) { throw new IllegalArgumentException("Posição não existe"); Capítulo 5 - Listas Ligadas - Exercícios: Lista Ligada - Página 66 Material do Treinamento Algoritmos e Estruturas de Dados em Java fim = System.currentTimeMillis(); System.out.println("Lista Ligada percorrendo: " + (fim - inicio) / 1000.0); // REMOVENDO DO COMEÇO inicio = System.currentTimeMillis(); for (int i = 0; i < numeroDeElementos; i++) { vetor.remove(0); } fim = System.currentTimeMillis(); System.out .println("Vetor remove do começo: " + (fim - inicio) / 1000.0); inicio = System.currentTimeMillis(); for (int i = 0; i < numeroDeElementos; i++) { lista.remove(0); } fim = System.currentTimeMillis(); System.out.println("Lista Ligada remove do começo: " + (fim - inicio) / 1000.0); } } Capítulo 5 - Listas Ligadas - Exercícios: Lista Ligada - Página 69 CAPÍTULO 6 Pilhas “O pessimista queixa-se do vento, o otimista espera que ele mude e o realista ajusta as velas. “ – Willian George Ward 6.1 - Introdução Um determinado produto é composto por diversas peças (digamos p1, p2, ...,pn). O processo de monta- gem deste produto é automático (executado por uma máquina) e exige que as peças sejam colocadas em uma ordem específica (primeiro a p1, depois a p2, depois a p3 e assim por diante). As peças são empilhadas na ordem adequada e a máquina de montagem vai retirando peça por peça do topo desta pilha para poder montar o produto final. A mesma máquina que faz a montagem é capaz de trocar uma peça quebrada de um produto já montado. O que a máquina faz é desmontar o produto até chegar na peça defeituosa, trocá-la e então depois recolocar as peças que foram retiradas. Isso também é feito com o uso da pilha de peças. Veja a seguir o algoritmo que a máquina montadora implementa para fazer a manutenção de um produto com defeito. 1) Retirar e empilhar peça por peça do produto até chegar na peça defeituosa. 2) Retirar a peça defeituosa 3) Colocar uma peça nova sem defeitos 4) Desempilhar e montar peça por peça do topo da pilha até a pilha ficar vazia. 70 Material do Treinamento Algoritmos e Estruturas de Dados em Java Fig.: Consertando o ventilador De alguma forma uma peça precisa ser representada em nosso programa. Como estamos usando orienta- ção a objetos as peças serão representadas por objetos. Uma classe Java será criada somente para modelar as peças, algo similar ao código a seguir: public class Peca { Capítulo 6 - Pilhas - Introdução - Página 71 Material do Treinamento Algoritmos e Estruturas de Dados em Java 6.4 - Inserir uma peça As peças são sempre inseridas no topo da Pilha. Ainda não definimos onde fica o topo da Pilha. Como estamos utilizando uma Lista para guardar os elementos então o topo da Pilha poderia ser tanto o começo ou o fim da Lista. Aqui escolheremos o fim da Lista. Então, inserir na Pilha é simplesmente adicionar no fim da Lista. public class Pilha { private List<Peca> pecas = new LinkedList<Peca>(); public void insere(Peca peca) { this.pecas.add(peca); } } Recordando que o método add(Object) adiciona no fim da Lista. 6.5 - Remover uma peça A remoção também é bem simples, basta retirar o último elemento da Lista. public class Pilha { private List<Peca> pecas = new LinkedList<Peca>(); ... public Peca remove() { return this.pecas.remove(this.pecas.size() - 1); } } É bom observar que se o método remove() for usado com a Pilha vazia então uma exceção será lançada pois o método remove(int) da List lança IndexOutOfBoundsException quando não existir elemento para remover. 6.6 - Informar se a pilha está vazia Para implementar esta operação basta verificar se o tamanho da Lista é zero. public class Pilha { private List<Peca> pecas = new LinkedList<Peca>(); ... public boolean vazia() { return this.pecas.size() == 0; } } Capítulo 6 - Pilhas - Inserir uma peça - Página 74 Material do Treinamento Algoritmos e Estruturas de Dados em Java Na classe LinkedList existe também o método isEmpty() que poderia ter sido usado aqui mais convenien- temente. 6.7 - Generalização Nossa Pilha só funciona para guardar objetos da classe Peca. Vamos generalizar a Pilha para poder arma- zenar qualquer tipo de objeto. Isso será feito utilizando a classe Object da qual todas as classe derivam direta ou indiretamente. Criaremos uma LinkedList de Object em vez de uma LinkedList de Peca. public class Pilha { private List<Object> objetos = new LinkedList<Object>(); public void insere(Object objeto) { this.objetos.add(objeto); } public Object remove() { return this.objetos.remove(this.objetos.size() - 1); } public boolean vazia() { return this.objetos.size() == 0; } } Agora, podemos guardar qualquer tipo de objeto na Pilha. Isso é uma grande vantagem pois a classe Pilha poderá ser reaproveitada em diversas ocasiões. Mas, há uma desvantagem, quando removemos um elemento da Pilha não podemos garantir qual é o tipo de objeto que virá. No Java 5, poderíamos usar Generics para solucionar este problema. A nossa classe Pilha poderia ser uma classe parametrizada. Na criação de um objeto de uma classe parametrizada é possível dizer com qual tipo de objeto que queremos trabalhar. Algo deste tipo: Pilha de Peças pilha = new Pilha de Peças(); Traduzindo este código para Java 5 de verdade, ficaria assim: Pilha<Peca> pilha = new Pilha<Peca>(); Só que para utilizar o recurso do Generics devemos parametrizar a class Pilha. public class Pilha<T> { private LinkedList<T> objetos = new LinkedList<T>(); public void insere(T t) { this.objetos.add(t); } public T remove() { Capítulo 6 - Pilhas - Generalização - Página 75 Material do Treinamento Algoritmos e Estruturas de Dados em Java return this.objetos.remove(this.objetos.size() - 1); } public boolean vazia() { return this.objetos.size() == 0; } } Poderíamos também adicionar outros método provavelmente úteis a manipulação de uma pilha, como saber o tamanho da pilha, espiar um elemento em determinada posição, entre outros. Vamos testar a classe Pilha que usa Generics. public class Teste { public static void main(String[] args) { Pilha<Peca> pilha = new Pilha<Peca>(); Peca peca = new Peca(); pilha.insere(peca); Peca pecaRemove = pilha.remove(); if (pilha.vazia()) { System.out.println("A pilha está vazia"); } Pilha<String> pilha2 = new Pilha<String>(); pilha2.insere("Rafael Cosentino"); pilha2.insere("Paulo Silvera"); String paulo = pilha2.remove(); String rafael = pilha2.remove(); System.out.println(paulo); System.out.println(rafael); } } Neste exemplo, criamos duas Pilhas. A primeira vai armazenar só objetos do tipo Peca e a segunda só String. Se você tentar adicionar um tipo de objeto que não corresponde ao que as Pilhas estão guardando então um erro de compilação será gerado para evitar que o programador cometa um erro lógico. 6.8 - API do Java Na biblioteca do Java existe uma classe que implementa a estrutura de dados que foi vista neste capítulo, esta classe chama-se Stack e será testada pelo código abaixo. public class Teste { public static void main(String[] args) { Stack pilha = new Stack(); Capítulo 6 - Pilhas - API do Java - Página 76 Material do Treinamento Algoritmos e Estruturas de Dados em Java } Faça alguns testes. package br.com.caelum.ed.pilhas; import br.com.caelum.ed.Peca; public class Teste { public static void main(String[] args) { Pilha pilha = new Pilha(); Peca peca = new Peca(); pilha.insere(peca); Peca pecaRemovida = pilha.remove(); if(peca != pecaRemovida){ System.out.println("Erro: a peça removida não é igual a que foi inserida"); } if (!pilha.vazia()) { System.out.println("Erro: A pilha não está vazia"); } } } Se não for impresso nenhuma mensagem de erro significa que a Pilha está funcionando. 3) Implemente a classe PilhaGenerica para objetos (genérica) vista neste capítulo. Coloque a classe no pacote br.com.caelum.ed.pilhas package br.com.caelum.ed.pilhas; import java.util.LinkedList; import java.util.List; public class PilhaGenerica { private List<Object> objetos = new LinkedList<Object>(); public void insere(Object objeto) { this.objetos.add(objeto); } public Object remove() { return this.objetos.remove(this.objetos.size() - 1); } public boolean vazia() { return this.objetos.size() == 0; } } Capítulo 6 - Pilhas - Exercícios: Pilha - Página 79 Material do Treinamento Algoritmos e Estruturas de Dados em Java Faça alguns testes. package br.com.caelum.ed.pilhas; import br.com.caelum.ed.Peca; public class TestePilhaGenerica { public static void main(String[] args) { PilhaGenerica pilhaDePecas = new PilhaGenerica(); Peca peca = new Peca(); pilhaDePecas.insere(peca); Peca pecaRemovida = pilhaDePecas.remove(); if(peca != pecaRemovida){ System.out.println("Erro: a peça removida não é igual a que foi inserida"); } if (!pilhaDePecas.vazia()) { System.out.println("Erro: A pilha não está vazia"); } } } Perceba que a classe TestePilhaGenerica contém um erro de compilção. Quando você remove um elemento da PilhaGenerica você recebe uma referência do tipo Object e não do tipo Peca. Altere a linha: Peca pecaRemovida = pilhaDePecas.remove(); Por: Object pecaRemovida = pilhaDePecas.remove(); Isso faz o código compilar mas agora você não tem mais a garantia de tipo. Não sabe se a referência que você recebeu realmente está apontado para um objeto do tipo Peca. 4) Implemente a classe PilhaParametrizada utilizando o recurso do Generics. Coloque a classe no pacote br.com.caelum.ed.pilhas package br.com.caelum.ed.pilhas; import java.util.LinkedList; import java.util.List; public class PilhaParametrizada<T> { private List<T> objetos = new LinkedList<T>(); public void insere(T t) { this.objetos.add(t); } Capítulo 6 - Pilhas - Exercícios: Pilha - Página 80 Material do Treinamento Algoritmos e Estruturas de Dados em Java public T remove() { return this.objetos.remove(this.objetos.size() - 1); } public boolean vazia() { return this.objetos.size() == 0; } } Faça alguns testes: package br.com.caelum.ed.pilhas; import br.com.caelum.ed.Peca; public class TestePilhaGenerica { public static void main(String[] args) { PilhaParametrizada<Peca> pilhaDePecas = new PilhaParametrizada<Peca>(); Peca peca = new Peca(); pilhaDePecas.insere(peca); Peca pecaRemovida = pilhaDePecas.remove(); if(peca != pecaRemovida){ System.out.println("Erro: a peça removida não é igual a que foi inserida"); } if (!pilhaDePecas.vazia()) { System.out.println("Erro: A pilha não está vazia"); } PilhaParametrizada<String> pilhaDeString = new PilhaParametrizada<String>(); pilhaDeString.insere("Rafael Cosentino"); pilhaDeString.insere("Paulo Silveira"); System.out.println(pilhaDeString.remove()); System.out.println(pilhaDeString.remove()); } } 5) (opcional) É possível implementar a nossa Pilha utilizando internamente uma ArrayList em vez de LinkedList? Teremos algum ganho ou perda no consumo de tempo de alguma das operações? 6) (opcional) Uma mensagem é criptografada invertando cada palavra do texto. O texto “Uma mensagem confidencial” criptografado fica “amU megasnem laicnedifnoc”. Implemente a criptografia e a decriptografia de mensagem. Faça isso utilizando Pilha. Para pegar caracteres específicos de uma String, utilize seu método chatAt(int). Quando for colocar o caractere na Pilha, você vai perceber que não pode usar tipos primitivos como tipo parametrizado, então em vez de declarar uma pilha de char crie uma pilha do tipo wrapper Character. Capítulo 6 - Pilhas - Exercícios: Pilha - Página 81 Material do Treinamento Algoritmos e Estruturas de Dados em Java public class Fila { private List<Aluno> alunos = new LinkedList<Aluno>(); } 7.3 - Operações em Fila Em seguida, implemetaremos as operações da Fila de aluno. 7.4 - Inserir uma aluno Os alunos que entram na Fila devem sempre se colocar no fim da mesma. Vamos definir que o fim da Fila é o fim da Lista que estamos utilizando para implementar. Então, entrar na Fila e adicionar no fim da Lista. public class Fila { private List<Aluno> alunos = new LinkedList<Aluno>(); public void insere(Aluno aluno) { this.alunos.add(aluno); } } 7.5 - Remover um aluno O próximo aluno a ser atendido é sempre o que está no início da Fila. No nosso caso, quem está no início da Fila é o aluno que está no início da Lista. Então, basta remover o primeiro aluno. public class Fila { private List<Aluno> alunos = new LinkedList<Aluno>(); ... public Aluno remove() { return this.alunos.remove(0); } } É bom observar que se o método remove() for usado com a Fila vazia então uma exceção será lançada pois o método removeFirst() lança IndexOutOfBoundsException quando não existir elemento para remover. 7.6 - Informar se a Fila está vazia Para implementar esta operação basta verificar se o tamanho da Lista é zero. Capítulo 7 - Filas - Operações em Fila - Página 84 Material do Treinamento Algoritmos e Estruturas de Dados em Java public class Fila { private List<Fila> alunos = new LinkedList<Fila>(); ... public boolean vazia() { return this.alunos.size() == 0; } } 7.7 - Generalização Nossa Fila só funciona para guardar objetos da classe Aluno. Vamos generalizá-la para poder armazenar qualquer tipo de objeto. Isso será feito utilizando a classe Object da qual todas as classe derivam direta ou indiretamente. Criaremos uma LinkedList de Object em vez de uma LinkedList de Aluno. public class Fila { private List<Object> objetos = new LinkedList<Object>(); public void insere(Object objeto) { this.objetos.add(objeto); } public Object remove() { return this.objetos.remove(0); } public boolean vazia() { return this.objetos.size() == 0; } } Agora, podemos guardar qualquer tipo de objeto na Fila. Isso é uma grande vantagem pois a classe Fila poderá ser reaproveitada em diversas ocasiões. Mas, há uma desvantagem, quando removemos um elemento da Fila não podemos garantir qual é o tipo de objeto que virá. A solução para este problema é utilizar o recurso do Generics. A nossa classe Fila vai ser uma classe parametrizada. Assim, quando criarmos uma Fila poderemos definir com qual tipo de objetos ela deve trabalhar. Algo deste tipo: Fila de alunos fila = new Fila de alunos(); Traduzindo este código para Java, ficaria assim: Fila<Aluno> fila = new Fila<Aluno>(); Agora, precisamos parametrizar a classe Fila. public class Fila<T> { Capítulo 7 - Filas - Generalização - Página 85 Material do Treinamento Algoritmos e Estruturas de Dados em Java private List<T> objetos = new LinkedList<T>(); public void insere(T t) { this.objetos.add(t); } public T remove() { return this.objetos.remove(0); } public boolean vazia() { return this.objetos.size() == 0; } } Vamos criar duas Filas, uma para Aluno e outra para String. public class Teste { public static void main(String[] args) { Fila<Aluno> fila = new Fila<Aluno>(); Aluno aluno = new Aluno(); fila.insere(aluno); Aluno alunoRemovido = fila.remove(); if (fila.vazia()) { System.out.println("A fila está vazia"); } Fila<String> filaDeString = new Fila<String>(); filaDeString.insere("Rafael Cosentino"); filaDeString.insere("Paulo Silvera"); String paulo = filaDeString.remove(); String rafael = filaDeString.remove(); System.out.println(paulo); System.out.println(rafael); } } Em tempo de compilação, é verificado o tipo de objetos que estão sendo adicionados na Fila. Portanto, se você tentar inserir um objeto do tipo Aluno em uma Fila de String um erro de compilação será gerado. public class Teste { public static void main(String[] args) { Aluno aluno = new Aluno(); Fila<String> filaDeString = new Fila<String>(); // este código não compila filaDeString.insere(aluno); } Capítulo 7 - Filas - Generalização - Página 86 Material do Treinamento Algoritmos e Estruturas de Dados em Java public class FilaGenerica { private List<Object> objetos = new LinkedList<Object>(); public void insere(Object objeto) { this.objetos.add(objeto); } public Object remove() { return this.objetos.remove(0); } public boolean vazia() { return this.objetos.size() == 0; } } Faça alguns testes. package br.com.caelum.ed.filas; import br.com.caelum.ed.Aluno; public class TesteFilaGenerica { public static void main(String[] args) { FilaGenerica filaDeAlunos = new FilaGenerica(); Aluno aluno = new Aluno(); filaDeAlunos.insere(aluno); Aluno alunoRemovido = filaDeAlunos.remove(); if (aluno != alunoRemovido) { System.out .println("Erro: o aluno removido não é igual ao que foi inserido"); } if (!filaDeAlunos.vazia()) { System.out.println("Erro: A fila não está vazia"); } } } Perceba que a classe TesteFilaGenerica contém um erro de compilção. Quando você remove um elemento da FilaGenerica você recebe uma referência do tipo Object e não do tipo Aluno. Altere a linha: Aluno alunoRemovido = filaDeAlunos.remove(); Por: Object alunoRemovido = filaDeAlunos.remove(); Capítulo 7 - Filas - Exercícios: Fila - Página 89 Material do Treinamento Algoritmos e Estruturas de Dados em Java Isso faz o código compilar mas agora você não tem mais a garantia de tipo. Não sabe se a referência que você recebeu realmente está apontado para um objeto do tipo Aluno. 3) Implemente a classe FilaParametrizada utilizando o recurso do Generics. Coloque a classe no pacote br.com.caelum.ed.filas package br.com.caelum.ed.filas; import java.util.LinkedList; import java.util.List; public class FilaParametrizada<T> { private List<T> objetos = new LinkedList<T>(); public void insere(T t) { this.objetos.add(t); } public T remove() { return this.objetos.remove(0); } public boolean vazia() { return this.objetos.size() == 0; } } Faça alguns testes: package br.com.caelum.ed.filas; import br.com.caelum.ed.Aluno; public class TesteFilaGenerica { public static void main(String[] args) { FilaParametrizada<Aluno> filaDeAlunos = new FilaParametrizada<Aluno>(); Aluno aluno = new Aluno(); filaDeAlunos.insere(aluno); Aluno alunoRemovido = filaDeAlunos.remove(); if (aluno != alunoRemovido) { System.out .println("Erro: o aluno removido não é igual ao que foi inserido"); } if (!filaDeAlunos.vazia()) { System.out.println("Erro: A fila não está vazia"); } FilaParametrizada<String> filaDeString = new FilaParametrizada<String>(); Capítulo 7 - Filas - Exercícios: Fila - Página 90 Material do Treinamento Algoritmos e Estruturas de Dados em Java filaDeString.insere("Rafael Cosentino"); filaDeString.insere("Paulo Silveira"); System.out.println(filaDeString.remove()); System.out.println(filaDeString.remove()); } } 4) (opcional) É possível implementar a nossa Fila utilizando internamente uma ArrayList em vez de LinkedList? Teremos algum ganho ou perda no consumo de tempo de alguma das operações? Mostre a diferença através de um código que adiciona e remova muita gente da fila. Capítulo 7 - Filas - Exercícios: Fila - Página 91