Digamos que você está desenvolvendo uma aplicação. Depois de longas horas programando, você consegue criar algumas funcionalidades legais. Agora, você quer ter certeza de que as funcionalidades estão do jeito que você quer.

Isso envolve testar se cada parte do código funciona como esperado. Esse procedimento é conhecido como teste unitário. Diferentes linguagens fornecem seus próprios frameworks para testes.

Neste artigo, vou mostrar como escrever testes unitários em Java. Primeiro, explicarei o que o teste envolve e alguns conceitos que você precisará saber. Então, mostrarei alguns exemplos para ajudar você a entender melhor.

Para este artigo, assumo que você esteja familiarizado com o Java e com o IDE IntelliJ.

Configuração do projeto

Para este projeto, usarei o IDE IntelliJ. Se você não o tiver, siga este guia (em inglês) para instalar o IDE.

Neste projeto, usaremos as bibliotecas JUnit e Mockito para testes. Elas são as bibliotecas mais usadas para testes em Java. Você entenderá como essas bibliotecas são usadas à medida que avança pelo artigo.

Para configurar o JUnit, siga as etapas abaixo, conforme descrito neste guia (em inglês):

1. No menu principal, selecione File > New > Project.
2. Selecione New Project. Especifique um nome para o projeto – eu darei o nome de junit-testing-tutorial.
3. Selecione Maven como a ferramenta de build e, na linguagem, selecione Java.
4. Na lista JDK, selecione o JDK que você deseja usar no projeto.
5. Clique em Create.
6. Abra o arquivo pom.xml no diretório raiz do seu projeto.
7. No pom.xml, dentro das tags <dependencies></dependencies>, pressione Alt + Insert (ou Cmd + Insert no macOS), e selecione Generate Dependency.
8. Isso abrirá uma janela de ferramentas. Digite org.junit.jupiter:junit-jupiter no campo de pesquisa. Localize a dependência necessária e clique no botão Add.
9. Agora, clique em Load Maven Changes na notificação que aparece no canto superior direito no editor.

Agora, para configurar o Mockito, adicione essas duas dependências no seu pom.xml:

<dependency>
    <groupId>org.mockito</groupId>
    <artifactId>mockito-inline</artifactId>
    <version>5.2.0</version>
    <scope>compile</scope>
</dependency>
<dependency>
    <groupId>org.mockito</groupId>
    <artifactId>mockito-junit-jupiter</artifactId>
    <version>5.2.0</version>
    <scope>compile</scope>
</dependency>

Observação: a versão pode ser diferente, dependendo da época em que você está lendo este artigo.

Para completar a configuração, crie uma classe Welcome e defina sua função principal lá.

O que é um teste unitário?

Os testes unitários envolvem testar cada componente do seu código para ver se ele funciona como esperado. Eles isolam cada método individual do seu código e executam testes nele. Os testes unitários ajudam a garantir que seu software está funcionando como esperado antes de ser lançado.

Como desenvolvedor, você escreverá testes unitários assim que terminar de escrever um trecho de código. Você pode se perguntar se essa não é a tarefa de um testador. De certo modo, sim. Um testador é responsável por testar o software. No entanto, examinar cada linha de código coloca muita pressão no testador. Portanto, é uma boa prática para os desenvolvedores escreverem testes para seu próprio código também.

O objetivo do teste unitário é garantir que qualquer nova funcionalidade não interrompa a funcionalidade existente. Também ajuda a identificar quaisquer problemas ou bugs mais cedo no processo de desenvolvimento e ajuda a garantir que o código atenda aos padrões de qualidade definidos pela organização.

O que fazer e o que não fazer ao realizar testes unitários

Lembre-se das seguintes diretrizes ao escrever testes para seus métodos:

• Teste se a saída esperada de um método corresponde à saída real.
• Teste se as funções chamadas dentro do método estão ocorrendo o número desejado de vezes.
• Não tente testar código que não faça parte do método que está sendo testado.
• Não faça chamadas de API, conexões de banco de dados ou solicitações de rede ao escrever seus testes.

Agora, vamos ver alguns conceitos que você precisa saber antes de começarmos a escrever testes.

Afirmações

As afirmações (em inglês, assertions) determinam se seu teste é aprovado ou reprovado. Elas comparam o valor de retorno esperado de um método com o valor real. Há uma série de afirmações que você pode fazer no final do seu teste.

A classe Assertions no JUnit consiste em métodos estáticos que fornecem várias condições para decidir se o teste é aprovado ou não. Veremos esses métodos à medida que eu o guie por cada exemplo.

Mocking

A classe cujos métodos você está testando pode ter algumas dependências externas. Como mencionado anteriormente, você não deve tentar testar código que não faça parte da função que está sendo testada.

Nos casos em que sua função usa uma classe externa, porém, é uma boa prática fazer um mock dessa classe, ou seja, ter valores de mock-up (algo como "simulações", em português) em vez dos valores reais. Usaremos a biblioteca Mockito para esse fim.

Stubbing de método

As dependências externas podem não se limitar apenas às classes, mas também a certos métodos. O stubbing de método deve ser feito quando sua função está chamando uma função externa em sua implementação. Nesse caso, você faz com que essa função retorne o valor que você deseja em vez de chamar o método real.

Por exemplo, o método que você está testando (A) está chamando um método externo (B) em sua implementação. B faz uma consulta ao banco de dados, buscando todos os alunos com notas maiores que 80. Fazer uma chamada real ao banco de dados não é uma boa prática aqui. Portanto, você faz um stub do método e o faz retornar uma lista fictícia de alunos que você precisa para testar.

Você entenderá isso melhor com exemplos. Existem muitos outros conceitos que fazem parte dos testes em Java. Por enquanto, esses três são suficientes para você começar.

Passos a serem realizados durante os testes

1. Inicialize os parâmetros necessários que você precisará para executar o teste.
2. Crie objetos de mock-up e faça um stub de qualquer método se necessário.
3. Chame o método que você está testando com os parâmetros que você inicializou na etapa 1.
4. Adicione uma afirmação para verificar o resultado do seu teste. Isso decidirá se o teste é aprovado.

Você entenderá essas etapas melhor com exemplos. Vamos começar com um teste básico primeiro.

Como escrever o primeiro teste

Vamos escrever uma função simples que compara dois números. Ela retorna 1 se o primeiro número for maior que o segundo ou -1, do contrário.

Colocaremos essa função dentro de uma classe Basics:

public class Basics {
    public int compare(int n1, int n2) {
        if (n1 > n2) return 1;
        return -1;
    }
}

Bem simples! Vamos escrever o teste para essa classe. Todos os seus testes devem estar localizados dentro da pasta test.

Dentro da pasta test, crie uma classe BasicTests, onde você escreverá seus testes para essa classe. O nome da classe não importa, mas é uma boa prática segregar os testes de acordo com cada classe. Além disso, siga uma estrutura de pasta semelhante à do seu código principal.

public class BasicTests {
    // Seus testes vêm aqui
}

Os testes unitários são basicamente um conjunto de métodos que você define para testar cada método da sua classe. Dentro da classe acima, crie um método compare(), com um tipo de retorno de void. Novamente, você pode nomear o método como quiser.

@Test
public void compare() {

}

A anotação @Test indica que esse método deve ser executado como um caso de teste.

Agora, para testar o método, você precisa criar o objeto da classe acima e chamar o método passando alguns valores.

Basics basicTests = new Basics();
int value = basicTests.compare(2, 1);

Agora, use o método assertEquals() da classe Assertions para verificar se o valor retornado corresponde ao valor esperado.

Assertions.assertEquals(1, value);

Nosso teste deve ser aprovado, pois o valor retornado pelo método corresponde ao valor esperado. Para verificar, execute o teste clicando com o botão direito na seta verde ao lado do método de teste.

Os resultados do seu teste serão mostrados abaixo.

Mais exemplos de teste

No teste acima, apenas testamos um cenário. Quando há ramificações na função, você precisa escrever testes para cada condição. Vamos introduzir algumas ramificações adicionais na função acima.

public int compare(int n1, int n2) {
    if (n1 > n2) return 1;
    else if (n1 < n2) return -1;
    return 0;
}

Já testamos o primeiro ramo, então vamos escrever testes para os outros dois.

@Test
@DisplayName("Primeiro número é menor que o segundo")
public void compare2() {
    Basics basicTests = new Basics();
    int value = basicTests.compare(2, 3);
    Assertions.assertEquals(-1, value);
}

A anotação @DisplayName exibe o texto em vez do nome do método abaixo. Vamos executar o teste.

Para o caso em que os dois números são iguais:

@Test
@DisplayName("Primeiro número é igual ao segundo")
public void compare3() {
    Basics basicTests = new Basics();
    int value = basicTests.compare(2, 2);
    Assertions.assertEquals(0, value);
}

Ordenando um array

Agora, vamos escrever o teste para o seguinte código que ordena um array.

public void sortArray(int[] array) {
        int n = array.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

Para escrever o teste para isso, seguiremos um procedimento semelhante: chamaremos o método e passaremos um array para ele. Usaremos o assertArrayEquals() para escrever nossa afirmação.

@Test
@DisplayName("Array classificado")
public void sortArray() {
    Basics basicTests = new Basics();
    int[] array = {5, 8, 3, 9, 1, 6};
    basicTests.sortArray(array);
    Assertions.assertArrayEquals(new int[]{1, 3, 5, 6, 8, 9}, array);
}

Um desafio para você: escreva um código que inverta uma string e escreva um caso de teste para esse código.

Como criar mock-ups e stubs para testes

Vimos alguns exemplos básicos de testes unitários onde você fez afirmações simples. No entanto, as funções que você está testando podem conter dependências externas, como classes de modelo e conexões de banco de dados ou de rede.

Você não deve fazer conexões reais em seus testes, pois seria muito demorado. Nesses casos, você faz um mock-up dessas implementações. Vamos ver alguns exemplos de mock-ups.

Fazendo mock-up de uma classe

Vamos ter uma classe User com as seguintes propriedades:

public class User {
    private String username;
    private String password;
    private String role;
    private List<String> posts;    
}

Clique em Alt + Insert (ou Cmd + Insert no macOS) para gerar métodos getters e setters para as propriedades acima.

Vamos gerar uma nova classe Mocking que use o objeto acima.

public class Mocking {
    User user;

    public void setUser(User user) {
        this.user = user;
    }
}

Essa classe possui um método que atribui determinadas permissões com base na função do usuário. Ela retorna 1 se a permissão for atribuída com sucesso. Do contrário, ela retorna -1.

public int assignPermission() {
        if(user.getRole().equals("admin")) {
            String username = user.getUsername();
            System.out.println("Atribuir permissões especiais para o usuário " + username);
            return 1;
        } else {
            System.out.println("Não é possível atribuir permissão");
            return -1;
        }
    }

Para fins de demonstração, adicionei apenas instruções println(). A implementação real pode envolver a configuração de certas propriedades.

No arquivo de testes, adicionaremos uma anotação @ExtendWith no topo, pois estamos usando o Mockito. Não mostrei as importações aqui, pois o IntelliJ as faz automaticamente.

@ExtendWith(MockitoExtension.class)
public class MockingTests {

}

Então, como escrevemos o teste para o método? Precisaremos fazer um mock-up do objeto User. Você pode fazer isso adicionando uma anotação @Mock ao declarar o objeto.

@Mock
User user;

Você também pode usar o método mock(), pois é semelhante.

User user = mock(User.class);

Vamos escrever o método de teste.

@Test
@DisplayName("Permissão atribuída com sucesso")
public void assignPermissions() {
    Mocking mocking = new Mocking();
    Assertions.assertEquals(1, mocking.assignPermission());
}

Quando você executar o teste, ele lançará uma NullPointerException.

Isso ocorre porque o objeto do usuário ainda não foi inicializado. O método que você chamou não conseguiu usar o objeto de mock-up. Para isso, você precisará chamar o método setUser.

mocking.setUser(user);

Agora, o teste fornece o erro abaixo, pois o objeto de mock-up é inicialmente preenchido com valores nulos.

Isso significa que você precisa preencher o objeto de mock-up com valores reais? Não, você só precisa que o método getRole() retorne um valor que não seja null. Para isso, usaremos o stubbing de método.

when(user.getRole()).thenReturn("admin");

Usar when()...thenReturn() diz ao teste para retornar um valor quando um método for chamado. Você deve fazer o stubbing de métodos apenas para objetos de mock-up.

Faremos o mesmo para o método getUsername().

when(user.getUsername()).thenReturn("kunal");

Agora, se você executar o teste, ele será aprovado.

Exemplo de stubbing de método

No exemplo acima, eu simplesmente fiz o stubbing dos métodos getter para demonstrar o stubbing de método. Em vez de fazer stubbing dos getters, você pode definir a função e o nome de usuário com um construtor parametrizado ou métodos setter, se eles estiverem disponíveis.

user.setRole("admin");
user.setUsername("kunal");

O que fazer, contudo, se a classe User tiver um método que retorna todas as publicações (em inglês, posts) contendo uma determinada palavra nelas?

public List<String> getAllPostsContainingWord(String word) {
        List<String> filteredPosts = new ArrayList<>();
        for(String post: posts) {
            if(post.contains(word))
                filteredPosts.add(post);
        }
        return filteredPosts;
    }

Queremos que esse método retorne todas as publicações contendo a palavra "incrível". Se você chamar a implementação real desse método, pode levar muito tempo, pois o número de publicações pode ser enorme. Além disso, se você estiver fazendo mocking do objeto User, o array de publicações será nulo.

Nesse caso, você faz um stub do método e o faz retornar a lista que você deseja.

List<String> filteredPosts = new ArrayList<>();
filteredPosts.add("Dia Incrível");
filteredPosts.add("Este lugar é incrível");
when(user.getAllPostsContainingWord("incrível")).thenReturn(filteredPosts);

Stubbing de método em consultas de banco de dados

Vamos ver como testar métodos que envolvem fazer conexões com banco de dados. Primeiro, crie uma classe ApplicationDao que contenha todos os métodos que executam consultas ao banco de dados.

public class ApplicationDao {  }

Defina um método que busca o usuário por id e retorna null se o usuário não for encontrado.

public User getUserById(String id) {
    // Fazer consulta ao banco de dados aqui        
}

Crie outro método para salvar um usuário no banco de dados. Esse método lança uma exceção se o objeto do usuário que você está tentando salvar for null.

public void save(User user) throws Exception {
    // Fazer consulta ao banco de dados aqui
}

Nossa classe de mock-up usará esses métodos para implementar suas próprias funcionalidades. Implementaremos uma função que atualiza o nome de um usuário.

public int updateUsername(String id, String username) throws Exception{
            ApplicationDao applicationDao = new ApplicationDao();
            User user = applicationDao.getUserById(id);
            if(user!=null)
                user.setUsername(username);
            applicationDao.save(user);
            return 1;
    }

A implementação do método é bastante simples. Primeiro, obtenha o usuário por id, altere seu nome de usuário e salve o objeto do usuário atualizado. Escreveremos os casos de teste para esse método.

Existem dois casos que precisamos testar. O primeiro é quando o usuário é atualizado com sucesso. O segundo é quando a atualização falha, ou seja, quando uma exceção é lançada.

Antes de escrever os testes, crie um mock-up do objeto ApplicationDao, pois não queremos fazer conexões reais com o banco de dados.

@Mock
ApplicationDao applicationDao;

Vamos escrever nosso primeiro teste.

@Test
    @DisplayName("Usuário atualizado com sucesso")
    public void updateUsername() throws Exception {
        ...
    }

Crie um objeto do usuário para testar.

User user = new User();
user.setUsername("kunal");

Como estamos chamando um método externo, vamos fazer um stub do método para que ele retorne o objeto User acima.

when(applicationDao.getUserById(Mockito.anyString())).thenReturn(user);

Passe Mockito.anyString() para o método, pois queremos que o stub funcione para qualquer parâmetro de string. Agora, adicione uma afirmação para verificar se o método está funcionando corretamente.

Assertions.assertEquals(1, mocking.updateUsername("3211", "allan"));

O método retorna 1 em caso de atualização bem-sucedida. O teste, então, é aprovado.

Agora, vamos testar outro cenário em que o método falha e lança uma exceção. Simule esse cenário fazendo com que o método getUserById() retorne null.

lenient().when(applicationDao.getUserById(Mockito.anyString())).thenReturn(null);

Esse valor é, então, passado para o método save(), que, por sua vez, lança uma exceção. Em nossa afirmação, usaremos o método assertThrows() para testar se uma exceção foi lançada. Esse método recebe o tipo da exceção e uma expressão lambda como parâmetros.

Assertions.assertThrows(Exception.class, () -> {
            mocking.updateUsername("3412","allan");
        });

Como a exceção é lançada, nosso teste é aprovado.

Você pode encontrar o código completo aqui no GitHub.

Conclusão

Como desenvolvedor, escrever testes unitários para seu código é importante. Isso ajuda você a identificar bugs mais cedo no processo de desenvolvimento.

Neste artigo, comecei introduzindo o teste unitário e expliquei três conceitos importantes envolvidos no processo de teste. Isso dará a você uma boa base antes de passar para o código.

Depois disso, mostrei, com exemplos, como você pode testar diferentes cenários usando as mesmas técnicas básicas de teste. Também mostrei como usar classes e métodos mock-ups para testar implementações complexas.

A interface em Java se parece um pouco com as classes, mas tem uma diferença importante: uma interface pode ter somente assinaturas de métodos, campos e métodos padrão. Desde o Java 8, você também pode criar métodos padrão (documentação em inglês). No bloco seguinte, você verá um exemplo de interface:

public interface Veiculo {
    public String placa = "";
    public float velMax
    public void iniciar();
    public void parar();
    default void buzinar(){
      System.out.println("Buzinando");
   }
}

A interface acima contém dois campos, dois métodos e um método padrão. Sozinha, ela não tem uma finalidade específica, mas a interface geralmente é usada em conjunto com as Classes. Como? É simples. você precisa garantir que alguma classe a implemente.

public class Carro implements Veiculo {
    public void iniciar() {
        System.out.println("ligando o motor...");
    }
    public void parar() {
        System.out.println("parando o motor...");
    }
}

Temos, porém, uma regra geral: a Classe deve implementar todos os métodos da Interface. Os métodos devem ter exatamente a mesma assinatura (nome, parâmetros e exceções) descrita na interface. No entanto, a classe não precisa declarar os campos, apenas os métodos.

Instâncias de uma interface

Ao criar uma Classe do Java, que implementa uma Interface, a instância do objeto pode ser referenciada como uma instância da interface. Esse conceito é semelhante ao de instanciação por herança.

// seguindo o exemplo anterior

Veiculo tesla = new Carro();

tesla.iniciar(); // ligando o motor...

Uma interface não pode conter um método construtor. Por isso, você não pode criar uma instância da própria interface. É preciso criar uma instância de alguma classe que implemente a interface para fazer referência a ela.

Pense nas interfaces como se elas fossem um formulário de contrato em branco ou um modelo.

O que é possível fazer com esse recurso? Polimorfismo! Você pode usar apenas interfaces para fazer referência a instâncias de objeto!

class Caminhao implements Veiculo {
    public void iniciar() {
        System.out.println("ligando o motor do caminhão...");
    }
    public void parar() {
        System.out.println("parando o motor do caminhão...");
    }
}

class Iniciador {
    // método estático, pode ser chamado sem instanciar a classe
    public static void iniciarMotor(Veiculo veiculo) {
        veiculo.iniciar();
    }
}

Veiculo tesla = new Carro();
Veiculo tata = new Caminhao();

Iniciador.iniciarMotor(tesla); // ligando o motor...
Iniciador.iniciarMotor(tata); // ligando o motor do caminhão...

Existe herança múltipla?

Sim, você pode implementar várias interfaces em uma única classe. Embora na herança dentro das Classes você esteja restrito a herdar apenas uma classe, com as interfaces, você pode herdar várias. Não se esqueça, porém, de implementar todos os métodos de todas as interfaces para não gerar um erro de compilação!

public interface GPS {
    public void obterCoordenadas();
}

public interface Radio {
    public void ligarRadio();
    public void pararRadio();
}

public class Smartphone implements GPS,Radio {
    public void obterCoordenadas() {
        // retorna coordenadas
    }
    public void ligarRadio() {
      // liga o rádio
    }
    public void pararRadio() {
        // desliga o rádio
    }
}

Alguns recursos das interfaces

• É possível colocar variáveis em uma interface, embora não seja algo sensato, pois as Classes não deveriam ficar restritas a ter a mesma variável. Em resumo, evite inserir variáveis nas interfaces!
• Todas as variáveis em uma interface são públicas, mesmo que você não inclua a palavra-chave public.
• Uma interface não pode especificar a implementação de um método. Essa é uma tarefa das classes. Há, contudo, uma exceção recente (veja abaixo).
• Se uma classe implementa diversas interfaces, há a possibilidade de uma sobreposição de métodos. Como o Java não permite que métodos diferentes tenham exatamente a mesma assinatura, isso pode causar problemas. Esta pergunta no Stack Overflow (texto em inglês) fornece mais informações.

Métodos padrão das interfaces

Antes do Java 8, não havia como orientar uma interface para que tivesse uma implementação específica de um método. Isso gerava muita confusão e problemas no código caso uma interface fosse mudada de repente.

Imagine que você escreveu uma biblioteca de código aberto contendo uma interface. Vamos supor que um de seus clientes, por exemplo, desenvolvedores de todas as partes do mundo, a utilizem muito e que estejam felizes com ela. De repente, você precisa atualizar a biblioteca adicionando a ela uma nova definição de método à interface para dar suporte a um novo recurso. Você acaba causando um problema para todas as builds que possuem aquela interface, já que todas as classes que a implementam precisam mudar. Que catástrofe!

Felizmente, o Java 8 fornece os métodos default (padrão) para as interfaces. Um método default pode conter sua própria implementação diretamente dentro da interface! Assim, se uma classe não implementar um método padrão, o compilador usará a  implementação mencionada na interface. Isso é bom, certo? Desse modo, em sua biblioteca, você pode adicionar quantos métodos padrão quiser nas interfaces sem medo de quebrar coisa alguma!

public interface GPS {
    public void obterCoordenadas();
    default public void obterCoordenadasAproximadas() {
        // implementação para retornar coordenadas de fontes aproximadas
        // como o wi-fi e dispositivos móveis
        System.out.println("Obtendo coordenadas aproximadas...");
    }
}

public interface Radio {
    public void ligarRadio();
    public void pararRadio();
}

public class Smartphone implements GPS,Radio {
    public void obterCoordenadas() {
        // retorna coordenadas
    }
    public void ligarRadio() {
      // liga o rádio
    }
    public void pararRadio() {
        // desliga o rádio
    }

    // sem implementação de obterCoordenadasAproximadas()
}

Smartphone motoG = new Smartphone();
motog.obterCoordenadasAproximadas(); // Obtendo coordenadas aproximadas...

O que acontece, no entanto, se duas interfaces têm a mesma assinatura de métodos?

Ótima pergunta. Nesse caso, se você não fornecer a implementação na classe, o pobre compilador se confundirá todo e simplesmente causará um erro! É preciso fornecer a implementação do método padrão dentro da classe também. Existe, além disso, uma maneira bem legal de usar super para chamar a implementação que você deseja:

public interface Radio {
    // public void ligarRadio();
    // public void pararRadio();

    default public void proxima() {
        System.out.println("Próxima de Radio");
    }
}

public interface ReprodutorMusical {
    // public void iniciar();
    // public void pausar();
    // public void parar();

    default public void proxima() {
        System.out.println("Próxima de ReprodutorMusical");
    }
}

public class Smartphone implements Radio, MusicPlayer {
    public void proxima() {
        // Imaginando que você queira chamar proxima de ReprodutorMusical
        ReprodutorMusical.super.proxima();
    }
}

Smartphone motoG = new Smartphone();
motoG.proxima(); // Próxima de ReprodutorMusical

Métodos estáticos nas interfaces

Outra coisa que surgiu com o Java 8 foi a capacidade de adicionar métodos estáticos às interfaces. Os métodos estáticos nas interfaces são quase idênticos aos métodos estáticos nas classes concretas. A única e grande diferença está no fato de que os métodos static não são herdados nas classes que implementam a interface. Isso quer dizer que é a interface quem é referenciada ao chamar o método estático, não a classe que implementa a interface.

interface ReprodutorMusical {
  public static void comercial(String patrocinador) {
    System.out.println("Agora, aqui vai uma mensagem trazida até você por " + patrocinador);
  }
  
  public void reproduzir();
}


class Smartphone implements ReprodutorMusical {
	public void reproduzir() {
		System.out.println("Reproduzindo no smartphone");
	}
}

class Main {
  public static void main(String[] args) {
    Smartphone motoG = new Smartphone();
    ReprodutorMusical.comercial("Motorola"); // Chamada a partir da interface, não da classe que a implementa
    // motoG.comercial("Motorola"); // Isso causaria um erro de compilação
  }
}

Herdando uma interface

Também é possível, em Java, que uma interface herde outra interface usando a palavra-chave extends:

public interface Reprodutor {
    public void iniciar();
    public void pausar();
    public void parar();
}

public interface ReprodutorMusical extends Reprodutor {
    default public void proxima() {
        System.out.println("Próxima de ReprodutorMusical");
    }
}

Isso significa que a classe que implementa a interface ReprodutorMusical precisa implementar todos os métodos de ReprodutorMusical, assim como de Reprodutor:

public class SmartPhone implements ReprodutorMusical {
    public void iniciar() {
        System.out.println("iniciar");
    }
    public void parar() {
        System.out.println("parar");
    }
    public void pausar() {
        System.out.println("pausar");
    }
}

Agora, você já tem um bom entendimento das interfaces em Java! Siga aprendendo, descubra mais sobre as classes abstratas e veja como o Java oferece a você mais uma maneira de definir contratos.

Em um artigo anterior (em inglês), escrevi sobre a Máquina Virtual do Java (JVM) e expliquei sua arquitetura. Como parte do componente de ferramenta de execução, eu também falei brevemente sobre o Coletor de Lixo do Java (em inglês, Garbage Collector, ou GC).

Neste artigo, você vai aprender mais sobre o Garbage Collector, como ele funciona, os tipos variados de GC presentes no Java e suas vantagens. Também comentarei alguns dos novos Coletores de Lixo experimentais que estão disponíveis nas últimas versões do Java.

O que é a coleta de lixo em Java?

A coleta de lixo é o processo de recolher a memória não utilizada em tempo de execução, destruindo os objetos inutilizados.

Em linguagens como C e C++, o programador é responsável tanto pela criação quanto pela destruição dos objetos. Às vezes, o programador pode esquecer de destruir objetos que não estão sendo utilizados. A memória alocada para eles, por isso, não é liberada. A memória utilizada pelo sistema continua crescendo e, em algum momento, não haverá memória disponível no sistema para alocar seus objetos. O nome dado a tal processo é "memory leak" (vazamento de memória).

Após um certo ponto, a memória suficiente não se encontra disponível para a criação de objetos. O programa inteiro, então, finaliza anormalmente devido a um erro do tipo OutOfMemoryError.

Você pode usar métodos como free() em C e delete() em C++ para realizar operações de coleta de lixo. Em Java, porém, a coleta de lixo acontece automaticamente durante o ciclo de vida de um programa. Isso elimina a necessidade de desalocar memória e, portanto, evita vazamentos de memória.

O Garbage Collector do Java é o processo no qual os programas em Java realizam o gerenciamento automático de memória. Programas em Java são compilados em bytecode, podendo ser executados na Máquina Virtual do Java (Java Virtual Machine).

Quando estes programas são executados na JVM, objetos são criados na memória heap, que é a porção da memória dedicada ao programa.

No decorrer do ciclo de vida de uma aplicação em Java, objetos são criados e dispensados. Ao final, alguns objetos não são mais necessários. É possível dizer que, a qualquer ponto, a memória heap consiste em dois tipos de objetos:

• Vivos (Live) – estes objetos estão sendo utilizados e referenciados em algum lugar
• Mortos (Dead) – estes objetos não estão sendo utilizados ou não estão sendo referenciados em lugar algum.

O coletor de lixo encontra esses objetos que não estão sendo utilizados e os exclui para salvar memória.

Como desreferenciar um objeto em Java

O objetivo principal do coletor de lixo é salvar espaço na memória heap por meio da destruição de objetos que não contêm uma referência. Quando não existem referências a um objeto, a JVM pressupõe que o mesmo está morto (dead) e que não é mais necessário. Então, a memória heap ocupada por este objeto pode ser desocupada.

Existem diversas formas pelas quais as referências de um objeto podem ser desfeitas para transformá-lo em um candidato à coleta de lixo. Algumas delas são:

Transformar uma referência em nula

Estudante estudante = new Estudante();
estudante = null;

Atribuir uma referência à outra

Estudante estudanteUm = new Estudante();
Estudante estudanteDois = new Estudante();
estudanteUm = estudanteDois; // agora o primeiro objeto referenciado por estudanteUm está disponível para garbage collection

Utilizar um objeto anônimo

registrar(new Estudante());

Como funciona o Garbage Collection em Java?

O Garbage Collection do Java é um processo automático. O programador não precisa marcar explicitamente os objetos a serem excluídos.

A implementação da coleta de lixo se encontra na JVM (Máquina Virtual do Java). Cada JVM pode implementar sua própria versão de Garbage Collection. Porém, essa versão deve atender aos padrões da especificação da JVM de trabalhar com objetos presentes na memória heap, marcar ou identificar os objetos inalcançáveis, e destruí-los com compactação.

O que são as roots de Garbage Collection em Java?

Coletores de lixo funcionam sob o conceito de Garbage Collection Roots (GC Roots) para identificar objetos vivos e mortos.

Exemplos dessas roots de Garbage Collection são:

• Classes executadas pelo executor de classes do sistema (com exceção dos executores de classes customizadas)
• Threads ativas
• Variáveis locais e parâmetros dos métodos em execução
• Variáveis locais e parâmetros de métodos JNI (Java Native Interface)
• Referências globais de JNI
• Objetos utilizados como monitores para sincronização
• Objetos mantidos da coleta de lixo pela JVM para seus fins

O coletor de lixo percorre todo o grafo de objetos na memória, começando pelas roots de Garbage Collection e referências posteriores às roots de outros objetos.

Etapas de coleta de lixo em Java

Uma implementação padrão de coletor de lixo envolve três etapas:

Marcar objetos como vivos

Nessa etapa, o GC identifica todos os objetos vivos na memória ao percorrer o grafo de objetos.

Quando o GC "visita" um objeto, o marca como acessível – logo, ele está vivo. Todo objeto que o GC visita é marcado como vivo. Todos os objetos que não podem ser visitados pelas roots do GC são lixo e considerados como candidatos para coleta.

Se livrar de objetos mortos

Após a fase de marcação, temos um espaço na memória que é ocupado tanto por objetos vivos (visited), quanto por objetos mortos (unvisited). A fase de "livração" libera fragmentos de memória que contêm objetos mortos.

Compactar os objetos restantes na memória

Os objetos mortos que são removidos durante a fase de liberação não precisam necessariamente estar um ao lado do outro. Portanto, você pode acabar tendo espaços de memória fragmentados.

A memória, então, pode ser compactada depois que o coletor de lixo excluir os objetos mortos, para que os objetos remanescentes estejam em um bloco contíguo no começo da memória heap.

O processo de compactação faz com que seja mais fácil alocar memória para novos objetos de forma sequencial.

O que é a coleta de lixo geracional em Java?

Os coletores de lixo em Java implementam uma estratégia chamada coleta de lixo geracional, que categoriza objetos por idade.

Ter que marcar e compactar todos os objetos em uma JVM é ineficiente. Quanto mais e mais objetos são alocados, a lista de objetos cresce, levando a um tempo de coleta mais longo. A análise empírica de aplicações têm mostrado que a maioria dos objetos em Java têm vida curta.

No exemplo acima, o eixo Y representa o número de bytes alocados. O eixo X representa o tempo. Como você pode ver, menos e menos objetos permanecem alocados com o passar do tempo.

Na verdade, a maioria dos objetos têm uma vida muito curta, como foi demonstrado pelos altos valores no lado esquerdo do gráfico. É por isso que o Java categoriza e realiza coleta de lixo de acordo com as gerações de objetos.

A área da memória heap na JVM é dividida em três seções:

Geração jovem

Objetos recentemente criados começam na geração jovem (Young Generation). Esta geração é subdividida em:

• Espaço Éden (EdenSpace) – todos os novos objetos começam aqui, e a memória inicial é alocada neles.
• Espaço de sobreviventes (FromSpace e ToSpace) – objetos são movidos daqui para o Éden após um ciclo de coleta.

Quando objetos são coletados a partir da Geração Jovem, é um evento menor de coleta de lixo.

Quando o Espaço Éden é preenchido por objetos, um evento menor de Garbage Collection é realizado. Todos os objetos mortos são excluídos e todos os objetos vivos são movidos para um dos Espaços de sobreviventes.  Coletas de lixo menores também verificam os objetos em um espaço de sobreviventes e os movem para outro espaço.

Tenha a seguinte sequência como exemplo:

1. O Éden tem todos os objetos (vivos e mortos)
2. Uma Coleta de Lixo menor ocorre – todos os objetos mortos são removidos do Éden. Todos os objetos vivos são movidos para o S1 (FromSpace). O Éden e o S2 agora estão vazios.
3. Objetos são criados e adicionados ao Éden. Alguns objetos neste espaço e no S1 se tornam mortos.
4. Outro evento menor de GC ocorre – todos os objetos mortos são removidos do Éden e do S1. Todos os objetos vivos são movidos para o S2 (ToSpace). Eden e S1 agora estão vazios.

Portanto, em qualquer momento, um dos espaços de sobreviventes está vazio. Quando os objetos sobreviventes alcançam uma certa "experiência" em serem movidos entre os espaços de sobreviventes diversas vezes, eles são transferidos à Geração Velha.

Você pode usar a flag `-Xmn` para definir o tamanho da Geração Jovem.

Geração velha

Objetos que são mais velhos são eventualmente movidos da Geração Jovem para a Geração Velha (Old Generation). Esta geração também é referenciada como Tenured Generation, e contêm objetos que continuaram nos espaços de sobreviventes por um longo tempo.

Há um limite definido para a promoção de um objeto que decide quantos ciclos de coleta de lixo ele pode sobreviver antes de ser movido para a Geração Antiga.

Quando objetos são coletados da Geração Antiga, chamamos de evento maior de coleta de lixo.

Você pode usar as flags -Xms e -Xmx para determinar o tamanho inicial e máximo da memória heap.

Já que o Java utiliza coleta de lixo geracional, quanto mais eventos de coleta um objeto sobrevive, mais ele é promovido na heap. Ele começa na Geração Jovem e eventualmente termina na Tenured Generation se conseguir sobreviver por tempo suficiente.

Considere o seguinte exemplo para entender a promoção de objetos entre espaços e gerações:

Quando um objeto é criado, ele primeiro fica alocado no Espaço Éden da Geração Jovem. Quando um evento menor de coleta de lixo ocorre, os objetos vivos são promovidos ao FromSpace. Quando um novo evento menor ocorre, tanto os objetos vivos do Éden e do FromSpace são movidos para o ToSpace.

Este ciclo continua por um número específico de vezes. Se o objeto continuar sendo referenciado até esse ponto, o próximo ciclo de coleta de  lixo vai movê-lo para o espaço da Geração Antiga.

Geração permanente

Metadados de classes e métodos são alocados na Geração Permanente (Permanent Generation). Ela é utilizada pela JVM durante o tempo de execução com base nas classes em uso pela aplicação. Classes que não estão mais em uso nesta Geração podem ser coletadas pelo Garbage Collector.

Você pode usar as flags -XX:PermGen e -XX:MaxPermGen para determinar o tamanho inicial e máximo da Permanent Generation.

MetaSpace

A partir do Java 8, o espaço de memória MetaSpace substituiu o espaço PermGen. A implementação difere da PermGen, e este espaço da Heap agora é redimensionado automaticamente.

Isso evita o problema de aplicações ficarem sem memória devido ao tamanho limite do espaço PermGen da memória Heap. A memória MetaSpace pode ser coletada e as classes que não estão mais em uso podem ser automaticamente coletadas quando o MetaSpace alcança seu tamanho limite.

Tipos de Garbage Collector na Máquina Virtual do Java

A coleta de lixo faz com que o Java seja uma linguagem eficiente no quesito de uso de memória porque remove os objetos sem referência da memória heap e libera espaço para novos objetos.

A Máquina Virtual do Java tem oito tipos de coletores de lixo. Vamos conhecer cada um deles com mais detalhe.

GC serial

Esta é a implementação mais simples do Garbage Collector e foi feita para aplicações pequenas que estão sendo executadas em ambientes single-threaded. Todos os eventos de coleta de lixo são conduzidos em série em uma thread. A compactação da memória é executada após cada coleta.

Quando a aplicação é executada, ocorre um evento "stop the world" (pare o mundo) onde toda a aplicação é pausada. Já que a aplicação inteira é congelada durante a coleta de lixo, o GC serial não é recomendado em aplicações de larga escala, onde a latência baixa é uma necessidade.

O argumento da JVM para utilizar o Garbage Collector serial é -XX:+UeSerialGC.

GC paralelo

O coletor paralelo é feito para aplicações com conjuntos de dados de médio a largo porte que rodam em multiprocessadores ou hardware multi-threaded. Essa é a implementação padrão do Garbage Collector da JVM e também é conhecida como Throughput Collector.

Múltiplas threads são utilizadas para um evento menor de coleta de lixo na Geração Jovem. Uma única thread é utilizada para eventos maiores de coleta na Geração Velha.

Executar o GC paralelo também ocasiona o evento "stop the world" e a aplicação é pausada. Já que esta implementação é mais apropriada em um ambiente multi-threaded, ela pode ser usada quando muitas atividades são feitas e pausas longas são aceitáveis, como, por exemplo, executar uma tarefa em lote.

O argumento na JVM para executar o GC paralelo é -XX:+UseParallelGC.

GC paralelo antigo

Essa é a versão padrão do GC paralelo desde o Java 7u4. É a mesma implementação do GC paralelo, exceto pelo fato de utilizar threads múltiplas tanto para a Geração Jovem quanto para a Velha.

O argumento na JVM para executar o Garbage Collector paralelo antigo é -XX:+UseParallelOldGC.

GC CMS (Concurrent Mark Sweep)

Essa implementação também é conhecida como o coletor de pausa baixa simultânea. Múltiplas threads são usadas como coletas de lixo menores usando o mesmo algoritmo do paralelo. Coletas de lixo maiores são multi-threaded, como no GC paralelo antigo, mas o CSM roda de forma simultânea aos processos da aplicação para minimizar os eventos "stop the world".

Por causa disso, o coletor CSM usa mais CPU do que as outras implementações de GC. Se você pode alocar mais CPU em prol de melhor desempenho, o CMS é uma escolha melhor que o paralelo. Não há compactação nesta implementação.

O argumento na JVM para usar o Garbage Collector de Concurrent Mark Sweep (em português, algo como "varredura de marca concorrente") é -XX:+UseConcMarkSweepGC.

GC G1 (Garbage First)

O G1GC tinha a intenção de substituir o CMS e foi criado para aplicações multi-threaded que possuem um tamanho grande de memória heap disponível (acima de 4GB). É implementado de modo paralelo e simultânea, como o CMS, mas funciona de maneira um pouco diferente debaixo dos panos em comparação com os garbage collectors anteriores.

Apesar do G1 também ser geracional, ele não separa espaços para as gerações Jovem e Velha. Na verdade, cada geração é um conjunto de espaços, o que permite alterar o tamanho da Geração Jovem de modo flexível.

Ele particiona a heap em um conjunto de espaços de tamanhos iguais (1MB a 32MB - dependendo do tamanho da heap) e utiliza múltiplas threads para as escanear. Uma região pode ser Velha ou Jovem em qualquer período de tempo durante a execução do programa.

Após o período de marcação ser completo, o G1 sabe quais espaços contêm mais objetos que precisam ser coletados. Se o usuário está interessado em tempos de pausa mínimos, o G1 pode escolher evacuar apenas alguns espaços. Se o usuário não se preocupa com isso ou definiu um tempo de pausa grande, o G1 pode escolher incluir mais espaços.

Já que o G1CC identifica os espaços com a maior quantidade de lixo e realiza a coleta naqueles espaços primeiro, ele é chamado de Garbage First (lixo primeiro).

Além dos espaços de memória Eden, Sobreviventes e Velho, existem mais dois tipos de espaços presentes no G1CC:

• Humongous (Enorme) – usado para objetos grandes (maiores que 50% do tamanho da heap)
• Available (Disponíveis) – usado para espaços não utilizados ou não alocados.

O argumento na JVM para usar o Garbage Collector G1 é -XX:+UseG1GC .

Garbage Collector Epsilon

O Epsilon é um coletor de lixo "do-nothing" (que "não faz nada") que foi lançado como parte da JDK 11. Ele gerencia a alocação de memória, mas não implementa nenhum mecanismo de aproveitamento de memória. Uma vez que a memória heap disponível está cheia, a JVM para de funcionar.

Ele pode ser usado para aplicações que são sensíveis a latências extremas, onde os desenvolvedores sabem o footprint exato da memória da aplicação, ou até mesmo possuem aplicações que são (quase) garbage-free (livres de lixo). A utilização do GC Epsilon em qualquer outro cenário é desencorajado.

O argumento na JVM para utilizar o Garbage Collector Epsilon é -XX:+UnlockExperimentalVMOptions -XX:+UseEpsilonGC.

Shenandoah

O Shenandoah é um GC novo que foi lançado como parte do JDK 12. A sua vantagem principal sobre o Garbage Collector G1 é que ele realiza mais ciclos de coleta de lixo de maneira simultânea às threads da aplicação. O G1 pode evacuar seus espaços na heap apenas quando a aplicação é pausada, enquanto o Shenandoah pode realocar objetos simultaneamente com a aplicação.

Shenandoah pode compactar objetos vivos, coletar o lixo e mandar RAM de volta ao sistema operacional quase imediatamente após detectar memória livre. Já que tudo isso ocorre simultaneamente enquanto a aplicação roda, o Shenandoah é mais intensivo no quesito do uso de CPU.

O argumento na JVM para utilizar o Garbage Collector Shenandoah é -XX:+UnlockExperimentalVMOptions -XX:+UseShenandoahGC.

ZGC

O ZGC é outro Garbage Collector que foi lançado como parte da JDK 11 e foi melhorado na JDK 12. Ele foi criado para aplicações que requerem baixa latência (pausas de menos de 10ms) e/ou que utilizam um grande espaço da memória heap (multi-terabytes).

Os principais objetivos do ZGC são a baixa latência, escalabilidade e facilidade de uso. Para alcançar isso, o ZGC permite que uma aplicação em Java continue rodando enquanto ele executa todas as operações de Garbage Collection. Por padrão, o ZGC libera a memória não utilizada e a retorna ao sistema operacional.

Logo, o ZGC traz uma melhora significativa sobre outros Garbage Collectors tradicionais ao prover tempos de pausa extremamente baixos (tipicamente dentro de 2ms).

O argumento na JVM para utilizar o Garbage Collector Shenandoah é -XX:+UnlockExperimentalVMOptions -XX:+UseZGC.

Observação: tanto o Shanandoah quanto o ZGC estão sob planos de passarem a ser features de produção e serem removidos do estágio de experimentação na JDK 15.

Como escolher o Garbage Collector certo?

Se a sua aplicação não tem tempos de pausa estritos, você deve somente rodar a sua aplicação e deixar a JVM escolher o coletor certo para você.

Na maior parte do tempo, as configurações padrão devem funcionar bem. Se necessário, você pode ajustar o tamanho da heap para melhorar o desempenho. Se o desempenho ainda não alcançar suas expectativas, você pode alterar o coletor de lixo padrão de acordo com as necessidades do seu projeto:

• Serial – se a aplicação tem um conjunto de dados pequeno (aproximadamente 100MB) e/ou vai rodar em um único processador sem ter requisitos de tempo de pausa.
• Paralelo – se o melhor desempenho da aplicação for a prioridade e não houver requisitos para tempos de pausa ou pausas de um segundo ou mais serão aceitáveis.
• CMS/G1 – se o tempo de resposta é mais importante que a taxa de processamento e as pausas de coleta de lixo devem ser mantidas abaixo de aproximadamente um segundo.
• ZGC – se o tempo de resposta for a prioridade maior, e/ou você está usando grande parte da heap.

Vantagens do Garbage Collection

Existem múltiplos benefícios da coleta de lixo em Java.

Primeiramente, ela deixa o seu código mais simples. Você não precisa se preocupar com a alocação correta de memória e ciclos de liberação. Você para de usar um objeto no seu código e a memória que ele utiliza vai ser automaticamente liberada em algum momento.

Programadores que trabalham em linguagens sem Garbage Collection (como C e C++) devem implementar gerenciamento de memória manual em seus códigos.

Este processo também faz com que o Java seja eficiente em termos de memória, pois o coletor de lixo remove os objetos não referenciados da memória heap. Isso libera espaço na heap para acomodar novos objetos.

Enquanto alguns programadores argumentam em favor do gerenciamento de memória manual ao invés de Garbage Collection, o GC é agora um componente padrão em diversas linguagens de programação populares.

Para cenários onde o Garbage Collector impacta negativamente o desempenho, o Java oferece diversas opções para melhorar sua eficiência.

Melhores práticas de Garbage Collection

Evite disparos manuais

Além dos mecanismos básicos de coleta de lixo, um dos pontos mais importantes para entender a respeito de Garbage Collection no Java é que ele não é determinístico. Isso significa que não tem como prever quando a coleta de lixo vai ocorrer durante o tempo de execução.

É possível incluir uma sugestão à JVM no seu código para que ela inicie o coletor de lixo com os métodos System.gc() ou Runtime.gc(), mas isso não dá garantia de que o coletor realmente vai ser executado.

Utilize ferramentas de análise

Se você não tem memória suficiente para rodar sua aplicação, você vai lidar com problemas de lentidão, um longo período de coleta de lixo, eventos "stop the world" e, por fim, erros do tipo out of memory. Isso pode indicar que o tamanho da sua heap é muito pequeno, mas também que você pode ter um vazamento de memória na sua aplicação.

Você pode ter o auxílio de uma ferramenta de monitoramento como o jstat ou Java Flight Recorder para analisar se o uso da memória heap cresce indefinidamente, o que pode indicar um bug no seu código.

Configurações padrão são suas amigas

Se você estiver executando uma aplicação Java pequena e independente, você muito provavelmente não precisa alterar as configurações do Garbage Collector. As configurações padrão devem dar conta do trabalho.

Utilize flags na JVM para ajustes

A melhor forma de ajustar a Garbage Collection de acordo com as suas necessidades é utilizando flags na JVM. Flags podem configurar o GC que vai ser utilizado (Serial, G1 ou outros), o tamanho inicial e máximo da memória heap, o tamanho dos espaços da heap (Geração Jovem, Velha) e muito mais.

Escolha o coletor apropriado

A natureza da aplicação que está passando por ajustes é um guia inicial muito eficiente para as configurações do coletor. Por exemplo, o GC paralelo é eficiente, mas vai causar eventos "stop the world" frequentes, fazendo com que ele seja mais apropriado para processamento em back-end, onde as longas pausas para coleta de lixo são aceitáveis.

Por outro lado, o Garbage Collector CMS foi criado para minimizar pausas, sendo ideal para aplicações baseadas na Web, onde a responsividade é importante.

Conclusão

Neste artigo, discutimos Garbage Collection em Java, como funciona e seus diferentes tipos.

Para muitas aplicações simples, Garbage Collection não é algo que um programador Java precise considerar. Contudo, para programadores que querem melhorar suas habilidades em Java, é importante entender como esse processo funciona.

Este conceito também é muito popular em entrevistas técnicas, tanto para cargos de back-end júnior, quanto sênior.

Agradecemos por sua companhia até aqui. Esperamos que tenha gostado do artigo. Você pode se conectar com o autor pelo LinkedIn, onde ele fala regularmente sobre assuntos como tecnologia e a vida. Dê uma olhada também em outros artigos do autor (em inglês) e no canal do autor no YouTube. Boa leitura. 🙂️

Filas de prioridades geralmente são usadas em aplicações da vida real. Neste artigo, aprenderemos o que são essas filas e como podemos usá-las em Java.

Antes de discutirmos o que é uma fila de prioridades, vejamos o que é uma fila regular.

Uma fila (ou, em inglês, queue) regular segue a estrutura em que o primeiro a entrar é o primeiro a sair (em inglês, first in first out, também conhecida pela abreviação FIFO). Isso significa que, se 3 mensagens – m1, m2 e m3 – entrarem na fila nessa ordem, elas sairão da fila exatamente na mesma ordem.

Por que precisamos de filas?

Vamos supor que tenhamos produtores de dados (por exemplo, quando um usuário clica em uma página da web) que são extremamente rápidos. Queremos, no entanto, consumir esses dados em um ritmo mais lento posteriormente.

Nesse caso, o produtor dos dados enviaria todas as mensagens para a fila e o consumidor as receberia mais tarde, vindas da fila, em um ritmo mais lento.

O que é uma fila de prioridades?

Como mencionamos anteriormente, uma fila regular segue a estrutura em que o primeiro a entrar é o primeiro a sair. Em alguns cenários, contudo, queremos processar as mensagens de uma fila com base em sua prioridade, não na ordem em que entraram na fila.

As filas de prioridades ajudam a consumir as mensagens de prioridade mais alta primeiro, seguidas daquelas com prioridade mais baixa.

Filas de prioridades em Java

Vamos agora ver um código real em Java que nos mostrará como usar filas de prioridades.

Filas de prioridades com ordenamento natural

Aqui vemos um código mostrando como criar uma fila de prioridades simples para strings

private static void testStringsNaturalOrdering() {
        Queue<String> testStringsPQ = new PriorityQueue<>();
        testStringsPQ.add("abcd");
        testStringsPQ.add("1234");
        testStringsPQ.add("23bc");
        testStringsPQ.add("zzxx");
        testStringsPQ.add("abxy");

        System.out.println("Strings armazenadas por ordenamento natural em uma fila de prioridades\n");
        while (!testStringsPQ.isEmpty()) {
            System.out.println(testStringsPQ.poll());
        }
    }

A primeira linha nos informa que estamos criando uma fila de prioridades:

Queue<String> testStringsPQ = new PriorityQueue<>();

PriorityQueue está disponível no pacote java.util.

Em seguida, adicionamos 5 strings em ordem aleatória na fila de prioridades. Para isso, usamos a função add(), como vemos abaixo:

testStringsPQ.add("abcd");
testStringsPQ.add("1234");
testStringsPQ.add("23bc");
testStringsPQ.add("zzxx");
testStringsPQ.add("abxy");

Para obter o item mais recente da fila, usamos a função poll(), deste modo:

testStringsPQ.poll()

poll() nos dará o item mais recente e o removerá da fila. Se quisermos obter o item mais recente da fila sem removê-lo, podemos usar a função peek():

testStringsPQ.peek()

Por fim, imprimimos todos os elementos da fila usando a função poll(), assim:

while (!testStringsPQ.isEmpty()) {
   System.out.println(testStringsPQ.poll());
}

Aqui vemos o resultado do programa acima:

1234
23bc
abcd
abxy
zzxx

Como não demos à fila de prioridades uma maneira de priorizar seu conteúdo, foi usado o ordenamento natural padrão. Nesse caso, recebemos os dados na ordem ascendente das strings. Essa não é a mesma ordem na qual os itens foram adicionados à fila.

Como conseguir um ordenamento personalizado?

Isso também é possível. Conseguimos fazer isso com a ajuda de um comparador (em inglês, comparator).

Vamos criar agora uma fila de prioridades de números inteiros. Desta vez, no entanto, vamos obter o resultado em ordem descendente de valores.

Para conseguir isso, primeiro precisamos criar um comparator de número inteiros:

 static class CustomIntegerComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 < o2 ? 1 : -1;
        }
    }

Para criar um comparator, implementamos a interface comparator e sobrescreveremos o método compare.

Usando o1 < o2 ? 1 : -1, obteremos o resultado em ordem descendente. Se tivéssemos usado o1 > o2 ? 1 : -1, obteríamos o resultado em ordem ascendente.

Agora que já temos o comparator, precisamos adicioná-lo à fila de prioridades. Podemos fazer isso da seguinte maneira:

Queue<Integer> testIntegersPQ = new PriorityQueue<>(new CustomIntegerComparator());

Aqui vemos o resto do código que adicionará elementos à fila de prioridades e os mostrará na tela:

   testIntegersPQ.add(11);
        testIntegersPQ.add(5);
        testIntegersPQ.add(-1);
        testIntegersPQ.add(12);
        testIntegersPQ.add(6);

        System.out.println("Números inteiros armazenados em ordem inversa na fila de prioridades\n");
        while (!testIntegersPQ.isEmpty()) {
            System.out.println(testIntegersPQ.poll());
        }

O resultado do programa acima é este:

12
11
6
5
-1

Podemos ver que o comparator fez bem o seu trabalho. Agora, a fila de prioridades nos dá os números inteiros em ordem descendente.

Fila de prioridades com objetos do Java

Até este ponto, vimos como podemos usar strings e números inteiros com as filas de prioridades.

Na vida real, as aplicações geralmente usariam filas de prioridades com objetos personalizados do Java.

Para começar, vamos criar uma classe chamada CustomerOrder (em português, pedido do cliente), que será usada para armazenar os detalhes dos pedidos dos clientes:

public class CustomerOrder implements Comparable<CustomerOrder> {
    private int orderId;
    private double orderAmount;
    private String customerName;

    public CustomerOrder(int orderId, double orderAmount, String customerName) {
        this.orderId = orderId;
        this.orderAmount = orderAmount;
        this.customerName = customerName;
    }

    @Override
    public int compareTo(CustomerOrder o) {
        return o.orderId > this.orderId ? 1 : -1;
    }

    @Override
    public String toString() {
        return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName;
    }

    public double getOrderAmount() {
        return orderAmount;
    }
}

Esse é um caso simples de classes em Java para armazenar pedidos de clientes. Essa classe implementa a interface Comparable, de modo que possamos decidir como esse objeto precisa ser ordenado na fila de prioridades.

O ordenamento é decidido pela função compareTo no código acima. A linha o.orderId > this.orderId ? 1 : -1 orienta a fila a ordenar em ordem descendente com base no campo orderId.

Abaixo vemos o código que cria uma fila de prioridades para o objeto CustomerOrder:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1");
CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3");
CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2");

Queue<CustomerOrder> customerOrders = new PriorityQueue<>();
customerOrders.add(c1);
customerOrders.add(c2);
customerOrders.add(c3);
while (!customerOrders.isEmpty()) {
	System.out.println(customerOrders.poll());
}

No código acima, três pedidos de clientes foram criados e adicionados à fila de prioridades.

Ao executarmos o código, teremos o seguinte resultado:

orderId:3, orderAmount:50.0, customerName:customer3
orderId:2, orderAmount:300.0, customerName:customer2
orderId:1, orderAmount:100.0, customerName:customer1

Como esperávamos, o resultado vem em ordem descendente com base no campo orderId.

Como faríamos para priorizar com base no campo orderAmount?

Mais uma vez, temos um cenário da vida real. Digamos que, por padrão, o objeto CustomerOrder é priorizado pelo campo orderId. No entanto, precisamos de um modo de priorizá-lo com base no campo orderAmount (em português, valor do pedido).

Você pode pensar de imediato que deveremos modificar a função compareTo na classe CustomerOrder para ordenar com base no campo orderAmount.

A classe CustomerOrder, no entanto, pode ser usada em diversos lugares da aplicação. Modificar a função compareTo diretamente interferiria com o resto da aplicação, portanto.

A solução para isso é bastante simples: podemos criar um comparator personalizado para a classe CustomerOrder e usá-lo em conjunto com a fila de prioridades.

Abaixo, vemos o código para o comparator personalizado:

 static class CustomerOrderComparator implements Comparator<CustomerOrder> {

        @Override
        public int compare(CustomerOrder o1, CustomerOrder o2)
        {
            return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1;
        }
    }

Ele é bastante semelhante ao comparator personalizado de números inteiros que vimos anteriormente.

A linha o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; indica que precisamos priorizar com base na ordem descendente de orderAmount.

Aqui vemos o código que cria a fila de prioridades:

  CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1");
        CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3");
        CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2");
        Queue<CustomerOrder> customerOrders = new PriorityQueue<>(new CustomerOrderComparator());
        customerOrders.add(c1);
        customerOrders.add(c2);
        customerOrders.add(c3);
        while (!customerOrders.isEmpty()) {
            System.out.println(customerOrders.poll());
        }

No código acima, passamos o comparator para a fila de prioridades na linha de código que diz:

Queue<CustomerOrder> customerOrders = new PriorityQueue<>(new CustomerOrderComparator());

Abaixo, vemos o resultado ao executar esse código:

orderId:2, orderAmount:300.0, customerName:customer2
orderId:1, orderAmount:100.0, customerName:customer1
orderId:3, orderAmount:50.0, customerName:customer3

Podemos ver que os dados vêm em ordem descendente com base no campo orderAmount.

Código

Todo o código que discutimos neste artigo pode ser encontrado neste repositório do GitHub.

Parabéns!

Você, agora, sabe como usar filas de prioridades em Java.

Sobre o autor

O autor é um apaixonado por tecnologia e segue os avanços no campo. Ele também gosta de auxiliar as outras pessoas com seu conhecimento em tecnologia.

Você pode entrar em contato com ele por sua conta no LinkedIn.

Você também pode seguir o autor no Twitter.

Por fim, você pode ler mais artigos escritos por ele (em inglês) no blog do autor.

Um array é uma estrutura de dados utilizada para armazenar dados de um mesmo tipo. Arrays armazenam seus elementos na memória de modo contíguo.

Em Java, arrays são objetos. Todos os métodos da classe dos objetos podem ser invocados em um array. Podemos armazenar um número fixo de elementos em um array.

Vamos declarar um array de um tipo primitivo simples:

int[] intArray = {2,5,46,12,34};

Agora, vamos tentar imprimi-lo com o método System.out.println():

System.out.println(intArray);
// Resultado: [I@74a14482

Por que o Java não imprimiu nosso array? O que está acontecendo por baixo dos panos?

O método System.out.println() converte o objeto que passamos para uma string chamando o método String.valueOf(). Se olharmos para a implementação do método String.valueOf(), veremos isso:

public static String valueOf(Object obj) {
    return (obj == null) ? "null" : obj.toString();
}

Se o objeto passado é null ele retorna null. Senão, ele chama obj.toString(). No final, System.out.println() chama toString() para imprimir a saída.

Se a classe daquele objeto não sobrescreve a implementação de Object.toString(), ele chamará o método Object.toString().

Object.toString() retorna getClass().getName()+‘@’+Integer.toHexString(hashCode()). Em outras palavras, ele simplesmente retornará: "nome_da_classe@código_hash_do_objeto".

No nosso resultado anterior [I@74a14482 , o [ constata que isso é um array, e I significa int (número inteiro, o tipo do array). 74a14482 é a representação em hexadecimal sem sinal do código hash do array.

Sempre que criarmos nossas próprias classes, é uma boa prática sobrescrever o método Object.toString().

Não podemos imprimir arrays em Java simplesmente usando o método System.out.println(). Em vez disso, essas são algumas maneiras de imprimir um array:

1. Laços: laço for e laço for-each
2. Método Arrays.toString()
3. Método Arrays.deepToString()
4. Método Arrays.asList()
5. Interface Iterator do Java
6. API Stream do Java

Vamos vê-las uma por uma.

1. Laços: laço for e laço for-each

Aqui está um exemplo de um laço for:

int[] intArray = {2,5,46,12,34};

for(int i=0; i<intArray.length; i++){
    System.out.print(intArray[i]);
    // Resultado: 25461234
}

Todas as classes wrapper sobrescrevem Object.toString() e retornam uma representação dos seus valores em string.

Aqui está um laço for-each:

int[] intArray = {2,5,46,12,34};

for(int i: intArray){
    System.out.print(i);
    // Resultado: 25461234
}

2. Método Arrays.toString()

Arrays.toString() é um método estático da classe Arrays que pertence ao pacote java.util. Ele retorna uma representação em string do conteúdo do array especificado. Podemos imprimir arrays unidimensionais usando esse método.

Os elementos do array são convertidos para string usando o método String.valueOf(), desta forma:

int[] intArray = {2,5,46,12,34};
System.out.println(Arrays.toString(intArray));
// Resultado: [2, 5, 46, 12, 34]

Para um array de referências, temos que ter certeza de que a classe dessas referências sobrescreve o método Object.toString().

Por exemplo:

public class Test {
    public static void main(String[] args) {
        Student[] students = {new Student("John"), new Student("Doe")};
        
        System.out.println(Arrays.toString(students));
        // Resultado: [Student{name='John'}, Student{name='Doe'}]
    }
}

class Student {
    private String name;

    public Student(String name){
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" + "name='" + name + '\'' + '}';
    }
}

Esse método não é apropriado para arrays multidimensionais. Ele converte arrays multidimensionais em strings usando o método Object.toString(), o que retorna suas identidades ao invés de seus conteúdos.

Por exemplo:

// Criando um array multidimensional
int[][] multiDimensionalArr = { {2,3}, {5,9} };

System.out.println(Arrays.toString(multiDimensionalArr));
// Resultado: [[I@74a14482, [I@1540e19d]

Com a ajuda do método Arrays.deepToString(), podemos imprimir arrays multidimensionais.

3. Método Arrays.deepToString()

Arrays.deepToString() retorna uma representação em string dos "conteúdos profundos" do array especificado.

Se um elemento é um array de tipo primitivo, ele é convertido para string através da invocação da sobrecarga apropriada de Arrays.toString().

Aqui está um exemplo de um array multidimensional de tipo primitivo:

// criando o array multidimensional
int[][] multiDimensionalArr = { {2,3}, {5,9} };

System.out.println(Arrays.deepToString(multiDimensionalArr));
// Resultado: [[2, 3], [5, 9]]

Se um elemento é um array de referências, ele é convertido para string através de uma chamada recursiva do método Arrays.deepToString().

Teacher[][] teachers = 
{{ new Teacher("John"), new Teacher("David") }, {new Teacher("Mary")} };

System.out.println(Arrays.deepToString(teachers));
// Resultado: 
[[Teacher{name='John'}, Teacher{name='David'}],[Teacher{name='Mary'}]]

Temos que sobrescrever o método Object.toString() na nossa classe Teacher.

Se você está curioso sobre como ele faz a recursão, aqui está o código-fonte para o método Arrays.deepToString().

Observação: arrays de referência unidimensionais também podem ser impressos usando esse método. Por exemplo:

Integer[] oneDimensionalArr = {1,4,7};

System.out.println(Arrays.deepToString(oneDimensionalArr));
// Resultado: [1, 4, 7]

4. Método Arrays.asList()

Esse método retorna uma lista de tamanho fixo criada a partir do array especificado.

Integer[] intArray = {2,5,46,12,34};

System.out.println(Arrays.asList(intArray));
// Resultado: [2, 5, 46, 12, 34]

Mudamos o tipo de int para Integer, porque List é uma coleção que armazena uma lista de objetos. Quando estamos convertendo um array em uma lista, o array deve ser de referências.

Java chama Arrays.asList(intArray).toString(). Internamente, essa técnica usa o método toString() do tipo dos elementos que estão na lista.

Temos outro exemplo abaixo, com a nossa classe customizada Teacher:

Teacher[] teacher = { new Teacher("John"), new Teacher("Mary") };

System.out.println(Arrays.asList(teacher));
// Resultado: [Teacher{name='John'}, Teacher{name='Mary'}]

OBSERVAÇÃO: não podemos imprimir arrays multidimensionais usando esse método. Por exemplo:

Teacher[][] teachers = 
{{ new Teacher("John"), new Teacher("David") }, { new Teacher("Mary") }};
        
System.out.println(Arrays.asList(teachers));

// Resultado: [[Lcom.thano.article.printarray.Teacher;@1540e19d, [Lcom.thano.article.printarray.Teacher;@677327b6]

5. Interface Iterator

Do mesmo modo que com o laço for-each, podemos usar a interface Iterator para percorrer os elementos do array e imprimi-los.

Um objeto Iterator pode ser criado invocando o método iterator() em uma Collection. Esse objeto será usado para iterar sobre os elementos dessa Collection.

Aqui está um exemplo de como poderíamos imprimir um array usando a interface Iterator:

Integer[] intArray = {2,5,46,12,34};

// Criando uma List de Integer
List<Integer> list = Arrays.asList(intArray);

// Criando um Iterator dessa lista de números inteiros
Iterator<Integer> it = list.iterator();

// Se a lista tiver elementos para serem iterados
while(it.hasNext()) {
    System.out.print(it.next());
    // Resultado: 25461234
}

6. API Stream do Java

A API Stream é usada para processar coleções de objetos. Uma stream é uma sequência de objetos. Streams não mudam a estrutura de dados original. Elas apenas fornecem o resultado de cada operação requisitada.

Com a ajuda da operação de terminal forEach(), podemos iterar sobre cada elemento da stream.

Por exemplo:

Integer[] intArray = {2,5,46,12,34};

Arrays.stream(intArray).forEach(System.out::print);
// Resultado: 25461234

Agora, sabemos como imprimir um array em Java.

Obrigado pela leitura.

Imagem de Aziz Acharki, extraída do Unsplash.

Você pode ler outros artigos do autor (em inglês) no Medium e no freeCodeCamp.

Boa programação para você!

Escrito por: Fahim ul Haq

Niklaus Wirth, um cientista da computação suíço, escreveu um livro em 1976 intitulado Algorithms + Data Structures = Programs (em português, "Algoritmos + Estrutura de Dados = Programas").

Mais de 40 anos depois, essa equação permanece sendo verdade. É por isso que aspirantes a posições em engenharia de software precisam demonstrar sua compreensão de estruturas de dados ao se candidatarem a um emprego na área.

Quase todos os problemas exigem que o candidato demonstre uma compreensão profunda das estruturas de dados. Não importa se você acabou de se formar (em uma universidade ou em um bootcamp de programação) ou se você tem décadas de experiência.

Às vezes, as perguntas em uma entrevista mencionam explicitamente uma estrutura de dados, por exemplo, "dada uma árvore binária". Outras vezes, elas estão implícitas, como em "queremos rastrear o número de livros associados a cada autor".

Aprender estruturas de dados é essencial, mesmo que você esteja apenas tentando melhorar seu trabalho atual. Vamos começar entendendo o básico.

O que é uma estrutura de dados?

Em termos simples, uma estrutura de dados é um contêiner que armazena dados em um layout específico. Esse "layout" permite que a estrutura de dados seja eficiente em algumas operações e ineficiente em outras. Seu objetivo é entender as estruturas de dados de modo que você consiga escolher a mais adequada para o problema apresentado.

Por que precisamos de estruturas de dados?

Como as estruturas de dados são usadas para armazenar dados de uma forma organizada, e como os dados são a entidade mais crucial nas ciências da computação, fica claro o verdadeiro valor das estruturas de dados.

Independentemente do problema que você esteja resolvendo, de uma forma ou de outra, terá que lidar com dados — seja o salário de um empregado, preços de ações, uma lista de compras, ou mesmo uma simples lista telefônica.

Com base em diferentes cenários, os dados precisam ser guardados em um formato específico. Temos um punhado de estrutura de dados que satisfazem nossa necessidade de armazenar dados em diferentes formatos.

Estruturas de dados mais utilizadas

Primeiro, listemos as estruturas de dados mais utilizadas e, então, vamos explorá-las uma a uma:

1. Arrays
2. Pilhas
3. Filas
4. Listas vinculadas
5. Árvores
6. Grafos
7. Tries (elas são árvores, efetivamente, mas ainda assim é bom tratar delas separadamente)
8. Hash tables

Arrays

Um array é a estrutura de dados mais simples e mais amplamente utilizada. Outras estruturas de dados como pilhas e filhas são derivadas dos arrays.

Aqui temos uma imagem de um array simples de tamanho 4, contendo elementos (1, 2, 3 e 4).

Cada elemento de dados recebe um valor numérico positivo chamado de índice, o qual corresponde à posição daquele item dentro do array. A maioria das linguagens de programação define o índice inicial do array como 0.

A seguir, temos os dois tipos de arrays:

• Arrays unidimensionais (como o mostrado acima)
• Arrays multidimensionais (arrays dentro de arrays)

Operações básicas com arrays

• Insert (inserir) — Insere um elemento em um determinado índice
• Get (receber) — Retorna um elemento em um determinado índice
• Delete (excluir) — Remove um elemento em um determinado índice
• Size (tamanho) — Obtém o número total de elementos de um array

Perguntas mais comuns sobre arrays em entrevistas

• Encontre o segundo menor elemento de um array
• Primeiros inteiros não repetidos de um array
• Mescle dois arrays ordenados
• Reordene os valores positivos e negativos em um array

Pilhas (Stacks)

Todos temos familiaridade com a famosa opção de desfazer, que está presente em quase todos os aplicativos. Você já se perguntou como ela funciona? A ideia: você armazena na memória os estados anteriores de seu trabalho (os quais são limitados a um número específico) em uma ordem tal que o último estado apareça primeiro. Isso não pode ser feito usando-se apenas arrays. É aí que as pilhas passam a ser muito úteis.

Um exemplo de uma pilha na vida real seria um conjunto de livros colocados uns sobre os outros em uma ordem vertical. Para visualizar o livro que está em algum lugar do meio, você precisará remover todos os livros colocados em cima dele. É assim que funciona o método LIFO (acrônimo para a expressão inglesa "Last In, First Out" — em português, "o último a entrar é o primeiro a sair").

Aqui temos uma imagem de uma pilha contendo três elementos de dados (1, 2 e 3), em que 3 está no topo e será removido primeiro:

Operações básicas com pilhas

• Push (empilhar) — Insere um elemento no topo
• Pop (desempilhar) — Retorna o elemento do topo após removê-lo da pilha
• isEmpty (éVazio) — Retorna verdadeiro se a pilha estiver vazia
• Top (topo) — Retorna o elemento do topo sem removê-lo da pilha

Perguntas mais comuns sobre pilhas em entrevistas

• Calcule o valor de uma expressão pós-fixada usando uma pilha
• Ordene valores em uma pilha
• Verifique se os parênteses estão balanceados em uma expressão

Filas (Queues)

Similares às pilhas, as filas são uma outra estrutura de dados linear que armazena elementos de forma sequencial. A única diferença significativa entre pilhas e filas é que, em vez de usar o método LIFO, as filas usam a lógica FIFO, um acrônimo para "First in, First Out" (em português, "o primeiro a entrar é o primeiro a sair").

Um exemplo perfeito de uma fila na vida real: uma fileira de pessoas aguardando em uma bilheteria. Se uma nova pessoa chega, ela se junta às demais ao final da fila, não no começo — e a pessoa em pé à frente da fileira será a primeira a receber o ingresso e, portanto, deixar a fila.

Aqui temos uma imagem de uma fila contendo quatro elementos de dados (1, 2, 3 e 4), em que 1 está no topo e será removido primeiro:

Operações básicas com filas

• Enqueue (enfileirar) — Insere um elemento ao final da fila
• Dequeue (desenfileirar) — Remove um elemento do início da fila
• isEmpty (éVazio) — Retorna verdadeiro se a fila estiver vazia
• Top (topo) — Retorna o primeiro elemento da fila

Perguntas mais comuns sobre filas em entrevistas

• Implemente uma pilha usando uma fila
• Ordene inversamente os primeiros k elementos de uma fila
• Gere números binários de 1 a n usando uma fila

Lista vinculada (Linked list)

Uma lista vinculada (ou encadeada) é outra estrutura de dados linear importante que pode parecer com arrays à primeira vista, mas que difere em relação à alocação de memória, à estrutura interna e a como as operações básicas de inserção e exclusão são realizadas.

Uma lista vinculada é como uma cadeia de nós, onde cada nó contém informações como dados e um ponteiro para o nó seguinte na cadeia. Há um ponteiro de cabeça (head), que aponta para o primeiro elemento da lista vinculada e, se a lista estiver vazia, ele simplesmente aponta para nulo ou nada.

As listas vinculadas são utilizadas para implementar sistemas de arquivos, tabelas hash e listas de adjacência.

Aqui está uma representação visual da estrutura interna de uma lista vinculada:

A seguir, temos os tipos de listas vinculadas:

• Lista simplesmente vinculada (unidirecional)
• Lista duplamente vinculada (bidirecional)

Operações básicas com listas vinculadas

• InsertAtEnd (inserirAoFim) — Insere determinado elemento ao fim da lista vinculada
• InsertAtHead (inserirAoInício) — Insere determinado elemento no início/cabeça da lista vinculada
• Delete (excluir) — Exclui determinado elemento da lista vinculada
• DeleteAtHead (excluirAoInício) — Exclui o primeiro elemento da lista vinculada
• Search (busca) — Retorna determinado elemento da lista vinculada
• isEmpty (éVazio)— Retorna verdadeiro se a lista vinculada estiver vazia

Perguntas mais comuns sobre listas vinculadas em uma entrevista

• Ordene inversamente uma lista vinculada
• Detecte um loop (laço) em uma lista vinculada
• Retorne o enésimo nó partindo do final de uma lista vinculada
• Remova elementos duplicados de uma lista vinculada

Grafos (Graphs)

Um grafo é um conjunto de nós que estão conectados uns aos outros na forma de uma rede. Os nós também são chamados de vértices. Um par(x,y) é chamado de aresta, indicando que o vértice x está conectado ao vértice y. Uma aresta pode conter peso/custo, mostrando qual o custo exigido para se atravessar do vértice x para y.

Tipos de grafos:

• Grafo não direcionado
• Grafo direcionado (ou orientado)

Em uma linguagem de programação, os grafos podem ser representados usando-se duas formas:

• Matriz de adjacência
• Lista de adjacência

Algoritmos comuns para varredura de grafos:

• Busca em largura (em inglês, Breadth First Search)
• Busca em profundidade (em inglês, Depth First Search)

Perguntas mais comuns sobre grafos em uma entrevista

• Implemente algoritmos de busca em largura e em profundidade
• Verifique se um grafo é ou não uma árvore
• Conte o número de arestas em um grafo
• Encontre o caminho mínimo entre dois vértices

Árvores (Trees)

Uma árvore é uma estrutura de dados hierárquica que consiste em vértices (nós) e arestas que os conectam. Árvores são semelhantes a grafos, mas o ponto-chave que diferencia uma árvore de um grafo é que, em uma árvore, não deve haver ciclos.

Árvores são amplamente utilizadas em Inteligência Artificial e em algoritmos complexos para fornecer um mecanismo de armazenamento eficiente para a resolução de problemas.

A seguir, temos a imagem de uma árvore simples, além da nomenclatura básica usada para essa estrutura de dados:

A seguir temos os tipos de árvores:

• Árvore n-ária
• Árvore balanceada
• Árvore binária
• Árvore binária de busca
• Árvore AVL
• Árvore rubro-negra
• Árvore 2-3

Destes tipos, a árvore binária e a árvore binária de busca são as mais comumente utilizadas.

Perguntas mais comuns sobre árvores em uma entrevista

• Encontre a altura de uma árvore binária
• Encontre o k-ésimo valor máximo em uma árvore binária de busca
• Encontre nós a uma distância "k" da raiz
• Encontre ancestrais de um determinado nó em uma árvore binária

Trie

A Trie, também conhecida como "árvore de prefixos", é uma estrutura de dados em formato de árvore que se mostra bastante eficiente para solução de problemas relacionados a strings. Ela fornece recuperação rápida e é usada principalmente para pesquisar palavras em um dicionário, fornecer sugestões automáticas em um mecanismo de busca, e até mesmo para roteamento de IP.

Aqui temos uma ilustração de como três palavras "top", "thus" e "their" são armazenadas em uma Trie:

As palavras são armazenadas de cima para baixo, onde os nós de cor verde "p", "s" e "r" indicam os finais de "top", "thus" e "their", respectivamente.

Perguntas mais comuns sobre Tries em uma entrevista:

• Conte o número total de palavras em uma Trie
• Imprima todas as palavras armazenadas em uma Trie
• Classifique os elementos de um array usando uma Trie
• Forme palavras de um dicionário usando Trie
• Construa um dicionário T9

Hash table

Hashing é um processo usado para identificar objetos de forma única e armazenar cada um deles em algum índice único pré-calculado chamado de "chave". Assim, o objeto é armazenado na forma de um par "chave-valor", e a coleção desses itens é chamada de "dicionário". Cada objeto pode ser pesquisado usando sua respectiva chave. Existem diferentes estruturas de dados baseadas em hashing, mas a estrutura de dados mais comumente usada é a hash table (também conhecida por "tabela de dispersão").

Hash tables são normalmente implementadas usando-se arrays.

O desempenho do hashing como estrutura de dados depende de três fatores:

• A função de hashing
• O tamanho da hash table
• O método de resolução de colisões

Aqui temos uma ilustração de como o hash é mapeado em um array. O índice deste array é calculado por meio de uma função de hashing.

Perguntas mais comuns sobre hashing em uma entrevista

• Encontre pares simétricos em um array
• Trace o caminho completo de uma jornada
• Descubra se um array é um subconjunto de outro array
• Verifique se determinados arrays são disjuntos (não possuem elementos em comum)

Acima estão as oito principais estruturas de dados que você deve, definitivamente, conhecer antes de começar uma entrevista de programação.

Se você está procurando por mais material sobre estruturas de dados para entrevistas de programação, dê uma olhada nesses cursos interativos e baseados em desafios: Data Structures for Coding Interviews (Python, Java ou JavaScript - em inglês).

Para perguntas mais avançadas, confira Coderust 3.0: Faster Coding Interview Preparation with Interactive Challenges & Visualizations (em inglês).

Se você está se preparando para entrevistas em engenharia de software, aqui você encontra um roteiro abrangente para se preparar para entrevistas de programação (em inglês).

Boa sorte e bom aprendizado! :)

Nota do tradutor: O freeCodeCamp.org possui um vasto material gratuito e em português para auxiliá-lo na preparação para entrevistas de programação, incluindo inúmeros exercícios com algoritmos e estruturas de dados.

Um array é uma estrutura de dados usada para armazenar dados do mesmo tipo. Os arrays armazenam seus elementos em localizações sequenciais contínuas da memória.

Em Java, arrays são objetos. Todos os métodos da classe Object podem ser invocados em um array. Podemos armazenar um número fixo de elementos em um array.

Vamos declarar um array simples de tipo primitivo:

int[] intArray = {2,5,46,12,34};

Agora, vamos tentar imprimi-lo com o método System.out.println():

System.out.println(intArray);
// Resultado: [I@74a14482

Por que o Java não imprimiu o array? O que está acontecendo internamente?

O método System.out.println() converte o objeto que passamos em uma string, chamando String.valueOf(). Se olharmos a implementação do método String.valueOf(), veremos o seguinte:

public static String valueOf(Object obj) {
    return (obj == null) ? "null" : obj.toString();
}

Se o objeto passado para o método for null, ele retorna "null"; caso contrário, é chamado o método obj.toString(). No fim, System.out.println() chama toString() para imprimir o resultado.

Se essa classe de objeto não sobrescrever a implementação de Object.toString(), será chamado o método Object.toString().

Object.toString() retorna getClass().getName()+‘@’+Integer.toHexString(hashCode()). Simplificando, o que ele faz é retornar "nome da classe @ hash code do objeto".

Em nosso resultado anterior, [I@74a14482, o colchete inicial ([) declara que esse objeto é um array, enquanto I representa int (o tipo do array). 74a14482 é a representação hexadecimal sem sinal do hash code do array.

Sempre que criarmos nossas próprias classes personalizadas, é uma prática recomendada sobrescrever o método Object.toString().

Não podemos imprimir arrays em Java usando um método System.out.println() simples. Em vez disso, aqui temos algumas maneiras de podermos imprimir arrays:

1. Laços: laço for e laço for-each
2. Método Arrays.toString()
3. Método Arrays.deepToString()
4. Método Arrays.asList()
5. Interface Iterator do Java
6. Stream API do Java

Vejamos um por um.

1. Laços: laço for e laço for-each

Aqui temos um exemplo de laço for:

int[] intArray = {2,5,46,12,34};

for(int i=0; i<intArray.length; i++){
    System.out.print(intArray[i]);
    // Resultado: 25461234
}

Todas as classes wrapper sobrescrevem o método Object.toString() e retornam uma representação de string de seu valor.

Aqui temos um laço for-each:

int[] intArray = {2,5,46,12,34};

for(int i: intArray){
    System.out.print(i);
    // Resultado: 25461234
}

2. Método Arrays.toString()

Arrays.toString() é um método estático da classe array que pertence ao pacote java.util. Ele retorna uma representação de string do conteúdo do array especificado. Podemos imprimir arrays unidimensionais usando esse método.

Os elementos do array são convertidos em strings usando o método String.valueOf(), assim:

int[] intArray = {2,5,46,12,34};
System.out.println(Arrays.toString(intArray));
// Resultado: [2, 5, 46, 12, 34]

Para um array com um tipo de referência, temos de nos certificar que a classe do tipo de referência sobrescreve o método Object.toString().

Por exemplo:

public class Test {
    public static void main(String[] args) {
        Student[] students = {new Student("John"), new Student("Doe")};
        
        System.out.println(Arrays.toString(students));
        // Resultado: [Student{name='John'}, Student{name='Doe'}]
    }
}

class Student {
    private String name;

    public Student(String name){
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{" + "name='" + name + '\'' + '}';
    }
}

Esse método não é adequado para métodos multidimensionais. Ele converte arrays multidimensionais em strings usando Object.toString(), o que descreve suas identidades, em vez de seu conteúdo.

Por exemplo:

// Criação de um array multidimensional
int[][] multiDimensionalArr = { {2,3}, {5,9} };

System.out.println(Arrays.toString(multiDimensionalArr));
// Resultado: [[I@74a14482, [I@1540e19d]

Com a ajuda de Arrays.deepToString(), podemos imprimir arrays multidimensionais.

3. Método Arrays.deepToString()

Arrays.deepToString() retorna uma representação de string do "conteúdo interno" do array especificado.

Se o elemento de um array for de um tipo primitivo, ele será convertido em uma string invocando a sobrecarga apropriada de Arrays.toString() .

Aqui temos um exemplo de array multidimensional de um tipo primitivo:

// Criação de um array multidimensional
int[][] multiDimensionalArr = { {2,3}, {5,9} };

System.out.println(Arrays.deepToString(multiDimensionalArr));
// Resultado: [[2, 3], [5, 9]]

Se o elemento de um array for de tipo de referência, ele será convertido em uma string invocando Arrays.deepToString() recursivamente.

Teacher[][] teachers = 
{{ new Teacher("John"), new Teacher("David") }, {new Teacher("Mary")} };

System.out.println(Arrays.deepToString(teachers));
// Resultado: 
[[Teacher{name='John'}, Teacher{name='David'}],[Teacher{name='Mary'}]]

Temos de sobrescrever Object.toString() em nossa classe Teacher.

Se estiver curioso sobre como é feita a recursão, aqui está o código-fonte do método Arrays.deepToString().

OBSERVAÇÃO: arrays unidimensionais de tipo de referência também podem ser impressos usando este método. Por exemplo:

Integer[] oneDimensionalArr = {1,4,7};

System.out.println(Arrays.deepToString(oneDimensionalArr));
// Resultado: [1, 4, 7]

4. Método Arrays.asList()

Este método retorna uma lista de tamanho fixo gerada pelo array especificado.

Integer[] intArray = {2,5,46,12,34};

System.out.println(Arrays.asList(intArray));
// Resultado: [2, 5, 46, 12, 34]

Alteramos o tipo para Integer a partir de int, pois List é uma coleção que suporta uma lista de objetos apenas. Quando convertemos um array em uma lista, ele deve ser um array de tipo de referência.

O Java chama Arrays.asList(intArray).toString(). Essa técnica usa internamente o método toString() do tipo dos elementos que está dentro da lista.

Outro exemplo com nossa classe personalizada Teacher:

Teacher[] teacher = { new Teacher("John"), new Teacher("Mary") };

System.out.println(Arrays.asList(teacher));
// Resultado: [Teacher{name='John'}, Teacher{name='Mary'}]

OBSERVAÇÃO: não podemos imprimir arrays multidimensionais usando esse método. Por exemplo:

Teacher[][] teachers = 
{{ new Teacher("John"), new Teacher("David") }, { new Teacher("Mary") }};
        
System.out.println(Arrays.asList(teachers));

// Resultado: [[Lcom.thano.article.printarray.Teacher;@1540e19d, [Lcom.thano.article.printarray.Teacher;@677327b6]

5. Interface Iterator do Java

Da mesma forma que em um laço for-each, podemos usar a interface Iterator para percorrer elementos do array e imprimi-los.

O objeto Iterator pode ser criado invocando o método iterator() em uma coleção. Esse objeto será usado para iterar sobre os elementos daquela coleção.

Aqui temos um exemplo de como podemos imprimir um array usando a interface Iterator:

Integer[] intArray = {2,5,46,12,34};

// Criação de uma lista de Integer
List<Integer> list = Arrays.asList(intArray);

// Criação de um iterator da lista de Integer
Iterator<Integer> it = list.iterator();

// Se a lista tiver elementos que possam ser percorridos pelo Iterator
while(it.hasNext()) {
    System.out.print(it.next());
    // Resultado: 25461234
}

6. Stream API do Java

A Stream API é usada para processar coleções de objetos. Uma stream é uma sequência de objetos. Streams não mudam a estrutura de dados original. Elas apenas fornecem o resultado de acordo com as operações solicitadas.

Com o auxílio da operação terminal forEach(), podemos percorrer cada elemento da stream por iteração.

Por exemplo:

Integer[] intArray = {2,5,46,12,34};

Arrays.stream(intArray).forEach(System.out::print);
// Resultado: 25461234

Agora, você já sabe como imprimir um array em Java.

Obrigado pela leitura.

A imagem de capa é de Aziz Acharki e retirada do Unsplash.

Você pode ler outros artigos do autor no Medium e no freeCodeCamp (em inglês).

Boa programação para você!

Getters e setters são usados para proteger seus dados, especialmente na criação de classes.

Para cada instância de variável, um método getter retorna seu valor, enquanto um método setter o define ou atualiza. Com isso em mente, getters e setters também são conhecidos como métodos de acesso e de modificação, respectivamente.

Por convenção, getters começam com a palavra "get" e setters com a palavra "set", seguidos de um nome de variável. Em ambos os casos, a primeira letra do nome da variável será maiúscula:

public class Vehicle {
  private String color;
  
  // Getter
  public String getColor() {
    return color;
  }
  
  // Setter
  public void setColor(String c) {
    this.color = c;
  }
}

O método getter retorna o valor do atributo. O método setter recebe um parâmetro e o coloca no atributo.

Quando os métodos getter e setter estiverem definidos, os utilizamos no main:

public static void main(String[] args) {
  Vehicle v1 = new Vehicle();
  v1.setColor("Vermelho");
  System.out.println(v1.getColor());
}

// O resultado é "Vermelho"

Getters e setters permitem o controle dos valores. Você pode validar o valor dado no setter antes de definir o valor de fato.

Por que usar getters e setters?

Getters e setters permitem controlar a forma como variáveis importantes são acessadas e atualizadas no seu código. Por exemplo, considere este método setter:

public void setNumber(int number) {
  if (number < 1 || number > 10) {
    throw new IllegalArgumentException();
  }
  this.number = num;
}

Ao usar o método setNumber, você pode se certificar de que o valor de number está sempre entre 1 e 10. Isso é muito melhor do que atualizar a variável number diretamente:

obj.number = 13;

Se você atualizar number diretamente, você pode vir a causar efeitos colaterais indesejados em outros pontos do seu código. Aqui, definir number com o valor de 13 violaria a restrição que desejamos estabelecer de que o número precisa estar entre 1 e 10.

Tornar number uma variável privada e usar o método setNumber evita que isso aconteça.

Por outro lado, a única maneira de ler o valor de number é usando um método getter:

public int getNumber() {
  return this.number;
}

Objetos de string são representados como uma cadeia de caracteres.

Se você já trabalhou com o Java Swing, ele tem componentes como o JTextField e o JTextArea, que nós usamos para obter entradas de dados da GUI. Eles carregam nossos dados como strings.

Se quisermos fazer uma calculadora simples usando o Swing, precisamos descobrir como converter uma string em um número inteiro. Isso nos leva à pergunta – como podemos converter uma string em um inteiro?

Em Java, podemos usar Integer.valueOf() e Integer.parseInt() para converter uma string em um número inteiro.

1. Use Integer.parseInt() para converter uma string em um número inteiro

Este método retorna a string como um tipo primitivo int. Se a string não contiver um número inteiro válido, será lançada uma NumberFormatException.

Assim, sempre que convertemos uma string em um int, precisamos lidar com essa exceção colocando o código dentro de um bloco de try-catch.

Vamos considerar um exemplo convertendo uma string em um int usando Integer.parseInt():

        String str = "25";
        try{
            int number = Integer.parseInt(str);
            System.out.println(number); // resultado = 25
        }
        catch (NumberFormatException ex){
            ex.printStackTrace();
        }

Vamos tentar quebrar esse código inserindo um número inteiro inválido:

     	String str = "25T";
        try{
            int number = Integer.parseInt(str);
            System.out.println(number);
        }
        catch (NumberFormatException ex){
            ex.printStackTrace();
        }

Como você pode ver no código acima, tentamos converter 25T em um número inteiro. Esta não é uma entrada válida. Portanto, ela deverá lançar uma NumberFormatException.

Este é o resultado do código acima:

java.lang.NumberFormatException: For input string: "25T"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:580)
	at java.lang.Integer.parseInt(Integer.java:615)
	at OOP.StringTest.main(StringTest.java:51)

Em seguida, vamos ver como converter uma string em um número inteiro usando o método Integer.valueOf().

2. Use Integer.valueOf() para converter uma string em um número inteiro

Este método retorna a string como um objeto de número inteiro. Se você olhar a documentação do Java, Integer.valueOf() retorna um objeto de número inteiro equivalente a new Integer(Integer.parseInt(s)).

Colocaremos nosso código dentro de um bloco de try-catch ao usar esse método. Vejamos um exemplo usando o método Integer.valueOf():

        String str = "25";
        try{
            Integer number = Integer.valueOf(str);
            System.out.println(number); // resultado = 25
        }
        catch (NumberFormatException ex){
            ex.printStackTrace();
        }

Agora, vamos tentar quebrar o código acima inserindo um número inteiro inválido:

        String str = "25TA";
        try{
            Integer number = Integer.valueOf(str);
            System.out.println(number); 
        }
        catch (NumberFormatException ex){
            ex.printStackTrace();
        }

Da mesma maneira que no exemplo anterior, o código acima lançará uma exceção.

Aqui está o resultado do código acima:

java.lang.NumberFormatException: For input string: "25TA"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:580)
	at java.lang.Integer.valueOf(Integer.java:766)
	at OOP.StringTest.main(StringTest.java:42)

Também criaremos um método para verificar se a string informada é numérica ou não antes de usar os métodos mencionados acima.

Criei um método simples para verificar se a string informada é ou não numérica.

public class StringTest {
    public static void main(String[] args) {
        String str = "25";
        String str1 = "25.06";
        System.out.println(isNumeric(str));
        System.out.println(isNumeric(str1));
    }

    private static boolean isNumeric(String str){
        return str != null && str.matches("[0-9.]+");
    }
}

O resultado é:

true
true

O método isNumeric() recebe uma string como argumento. Primeiro, ele verifica se o argumento é null ou não. Depois disso, usamos o método matches() para verificar se ele contém algarismos de 0 a 9 e o caractere de ponto.

Essa é uma maneira simples de verificar valores numéricos. Você pode escrever ou pesquisar no Google para encontrar expressões regulares mais avançadas que capturem números, dependendo de seu caso.

É uma prática recomendada verificar se a string informada é numérica ou não antes de tentar convertê-la em um número inteiro.

Obrigado pelo leitura.

Imagem da publicação: 🇸🇮 Janko Ferlič, do Unsplash

Entre em contato com o autor do texto pelo Medium.

Feliz programação!