Estrutura de Dados em Java

Estrutura de Dados

O que é uma estrutura de dados? Como o próprio nome diz, é uma forma de organizar informações. Ou seja, passamos de um patamar que usávamos tipos primitivos como Inteiro, Caractere e outros para tipos mais complexos, como Pilha, Fila e Árvore. Sim, esses tipos complexos utilizam tipos primários, mas estamos interessados agora em entender essa composição maior, como esses tipos se relacionam, qual a sua semântica dentro da estrutura, seu comportamento e os efeitos que eles causam no estado da estrutura.

Como disciplina, Estrutura de Dados tem como objetivo apresentar estruturas já consolidadas da área de Computação. Essas estruturas buscam resolver diversos problemas recorrentes na área de desenvolvimento. Os estudantes precisam entender, implementar e avaliar em quais situações eles são mais adequadas.

É importante ressaltar que uma Estrutura de Dados é formada por Dados (organizados segundo alguma lógica). Além disso possuem operações permitidas, vinculadas a essas dados. A palavra permite merece destaque, já que diversas operações podem ser realizadas sobre os dados, mas nem todas são "legais" dentro das regras de cada estrutura. Quando isso ocorre, dizemos que um programador "burlou" ou "violou" as regras. Mas qual o impacto disso? Logicamente isso afetará a forma de organização e possivelmente as próximas interações com esta estrutura.

Formalizando:

Estrutura de Dados envolve dados organizados de alguma forma e operações vinculadas aos dados que garantem a manutenção da organização após inserções e deleções.

Assim, algumas estruturas são utilizadas como forma de facilitar o armazenamento de informações, permitindo a recuperação de modo mais rápido. Logicamente, tudo depende do contexto do nosso problema. Por exemplo, não é recomendável utilizar uma Pilha para um problema que envolve o conceito de Fila, como uma fila de Banco por exemplo. Com o uso correto de uma estrutura é possível diminuir custos computacionais e esta disciplina oferece também este aspecto analítico.

Logicamente que o mais pudente é retirar os pratos de cima um a um e colocar em algum outo lugar, até que possamos - com segurança - pegar o prato desejado. Então, vamos criar um algoritmo simples para modelar isso:

Modelagem

Modelagem Computacional é um área da Computação que visa modelar computacionalmente alguns cenários ou problemas. Basicamente, buscamos transpor elementos do mundo real para o computador e para isso precisamos usar a "abstração". Logicamente que não iremos modelar algo da natureza em sua perfeição, e muitas vezes não precisamos. Modelamos apenas os elementos essenciais, arte proveniente da abstração:

focar em elementos principais, ignorando elementos eventuais ou menos importantes (para um contexto específico).

Desse modo, podemos criar classes - já que usaremos Java - com seus métodos que simulem um determinado elemento a ser modelado. Por exemplo: Carro possui uma marca, placa, modelo, ano de fabricação, motor e pode acelerar, frear, virar à esquerda, entre outros.

Em Estrutura de Dados, faremos constantemente esse exercício, modelaremos elementos do mundo real, eliminando suas características eventuais, focando apenas nos elementos principais. Isso ocorre com Pilhas, Filas, Árvores entre outras estruturas.

Revisão POO

Uma condição essencial para criar estruturas de dados, no modelo que vamos apresentar, é saber os conceitos de POO e Java. Caso esse não seja o seu caso, recomendo parar a leitura e fazer um curso ou ler materiais específicos sobre POO. Aqui forneço uma breve introdução!

Então, assumindo que você já conhece POO, vamos relembrar.

Classes

Classes são elementos no qual podemos implementar modelos, tal como uma forma de bolo que usaremos para fazer vários bolos: chocolate, cenoura e outros. Não importa os ingredientes utilizados, a forma sempre será a mesma.

Com classes podemos definir como serão os nossos objetos. Fazendo outra analogia, classes são como gabaritos. Através das classes podemos definir os atributos e métodos dos objetos.

Vamos ver um exemplo em Java. A seguir temos uma classe de nome AlgumaClasse, com dois atributos: um do tipo inteiro, chamado número, e outro do tipo string, chamado nome:

public class AlgumaClasse{
    int numero;
    String nome;
}

Objetos

Objetos são copias das Classes, dizemos ainda que quando instanciamos um objeto, estamos consolidando a classe. Ou seja, estamos de fato utilizando a classe como modelo para criar um objeto. Esse objeto terá os atributos e métodos estipulados na Classe. Mas é importante saber que: dois objetos da mesma classe podem ter comportamentos diferentes, dado o seu estado (os valores nos atributos). Como o exemplo do bolo, chocolate e cenoura foram implementados com ingredientes diferentes, mas ainda são bolos.

Em Java, um objeto é criado da seguintes forma, declara-se um local para armazená-lo (como uma variável) estipulando o seu tipo (AlgumaClasse) e depois o seu nome. Do lado direto da igualdade, temos o operador new acompanhado do nome da Classe e de parênteses:

public static void main(){
	AlgumaClasse ac = new AlgumaClasse();
}

Como disse antes, elas podem ter valores diferentes (estado). Vejamos:

public static void main(){
	AlgumaClasse ac = new AlgumaClasse();
	ac.numero = 10;
	ac.nome = "AC 1";

	AlgumaClasse ac2 = new AlgumaClasse();
	ac.numero = 20;
	ac.nome = "AC 2";

}

Assim, ac e ac2 são objetos diferentes que possuem seus próprios valores. Mas, ainda assim, são objetos de AlgumaClasse.

Construtor

Mas o que faz o new? Bem, ele 'chama' o construtor da classe para que seja instanciado o objeto (o objeto é colocado dentro da variável ac). Esse construtor é um método diferenciado, pois ele não possui retorno. Isso não quer dizer que ele é um void, ele literalmente não possui retorno. O Java saberá que ele é um construtor, pois não colocamos o tipo de retorno (void, Integer, String ...). Vejamos a diferença entre os métodos setNumero, getNumero e o Construtor.

public class AlgumaClasse{

    [...] //trecho inibido

	public AlgumaClasse(){
		nome = "";
	}

	public int getNumero(){
		return this.numero;
	}

	public void setNumero(int numero){
		this.numero = numero
	}	

}

Atributos

Atributos são variáveis (primitivas ou objetos) que são inerentes ao Objeto instanciado. Ou seja, os atributos são estipulados no modelo (a Classe). No exemplo anterior, já vimos o uso de atributos (nome e número). Os valores nos atributos definem o estado do objeto, que podem influenciar as suas ações (os métodos).

Métodos

Como vimos, os métodos são as ações dos objetos. O que isso significa? Significa que são eles os responsáveis por executar as operações, como obter um valor ou inserir um valor. Vimos um exemplos do Método (getNúmeros).

Métodos podem retornar um tipo ou não (void). Vejamos dois exemplos:

public class AlgumaClasse{

    [...] //trecho inibido

	public void setNumero(int numero){
		this.numero = numero
	}

	public int getNumero(){
 		return numero;
	}

}

Herança

Herança é uma forma de compartilhar atributos e métodos, de modo a eliminar a duplicidade de código. Assim, o processo de Herança consiste em agrupar atributos e métodos gerais em uma classe, que chamamos de Pai e reaproveitá-los nos Filhos.

Em Java, a Herança é implementada com a palavra-chave extends. Todos os atributos e métodos públicos (public) e protegidos (protected) serão herdados pelos filhos. Vejamos:

A classe Pai:

public class ClassePai{

    protected int valor1;

    protected void getValor1(){
	return valor1;
    }

}

A classe Filha:

public class ClasseFilha extends ClassePai{

    protected int valor2;

    protected void getValor2(){
	return valor2;
    }

    // usando o método do Pai
    protected void exibeValor(){
        System.out.println(  getValor1()  + "  " +  getValor2());
    }

}

Através da Herança podemos utilizar o Polimofirmos para agregar dados de vários tipos e tratá-los como iguais. Por exemplo: Um lista de Funcionários tem objetos do tipo Operador, Gerente e Supervisor. Poderíamos tratá-los como Funcionários e assim utilizar os métodos e atributos em comum.

Tipos Abstratos em Java

Já que relembramos os conceitos básicos de POO, buscaremos agora entender como implementar algo que funcione para uma variedade de tipos, eliminando a necessidade de implementar várias estrutura (uma para cada tipo). Afinal nosso objetivo é criar estruturas que possam ser utilizadas em vários contextos.

Classe Object

Como já falamos sobre Herança, podemos então definir a Classe Object. Basicamente, todos as Classes em Java são filhas de Object, mesmo sem o uso de extends. Ou seja, nativamente, todas as classes são filhas de Object.

Object é uma super classe! Logo, graças ao Polimorfismo, podemos tratar todas as classes como Object. O problema é que precisamos saber os seus tipos, quando formos utilizar os atributos e métodos. Então, nem sempre isso é uma vantagem.

public class EstruturaQualquer (){

	Object[] vetor;

	public EstruturaQualquer(int tamanho){
		vetor = new Object[tamanho];
	} 
	
	public void getItem(int i, Object valor){
		vetor[i] = valor;
	}
	public Object getItem(int i){
		retunr vetor[i];
	}

}

Agora vamos utilizar essa estrutura. Como ela foi implementada com Object, podemos inserir todos tipo de objeto, pois todos são filhos de Object.

public static void main(Strings[] args){

	EstruturaQualquer est1 = new EstruturaQualquer(10);
	est1.setItem(0, "Teste");
	est1.setItem(1, "Teste 2");

	EstruturaQualquer est2 = new EstruturaQualquer(10);
	est2.setItem(0, new Gerente() );
	est2.setItem(1, new Gerente() );
}

Mas do que se trata isso? Bem, estamos tentando esboçar uma forma de implementar nossas estrutura apenas uma vez de modo que ela sirva para uma ampla gama de contextos. O uso do Object funciona, criamos apenas uma estrutura e podemos inserir vários tipos, mas isso possui uma dificuldade: precisamos sempre fazer o cast para usar métodos específicos.

public static void main(Strings[] args){

	[...]

	EstruturaQualquer est2 = new EstruturaQualquer(10);
	est2.setItem(0, new Gerente() );
	est2.setItem(1, new Gerente() );

	double sal = est2.getItem(0).getSalario(); //isso possui um erro

}

Então vamos lá:

public static void main(Strings[] args){
	
	[...]

	EstruturaQualquer est2 = new EstruturaQualqyer(10);
	est2.setItem(0, new Gerente() );
	est2.setItem(1, new Gerente() );

	Gerente g = (Gerente) est2.getItem(0).getSalario(); //cast
	double sal = g.getSalario();
	
}

Agora que já entendemos a limitação, vamos ao próximo tópico.

Classes Genéricas

Classes Genéricas são muito boas para o que estamos querendo fazer. É comum que aqui você fique um pouco confuso, mas tenha uma coisa em mente:

Queremos criar estruturas que sejam implementadas um única vez e que sirva para String, Inteiro, Classes criadas por nós e outras.

Basicamente Classes Genéricas postergam a definição do tipo de dados. Assim, ao invés de definirmos na implementação (Classe) o tipo a ser utilizado, vamos definir no instanciamento do objeto. As classes Genéricas recebem um termo (T) que será substituído em tempo de execução, pelo tipo passado por parâmetro. Certamente você já utilizou algo similar como ArrayList, mas não sabia o motivo.

public class EstruturaQualquer<T>(){

	T[] vetor;

	public EstruturaQualquer(int tamanho){
		vetor = (T[]) new Object[tamanho];
	} 
	
	public void getItem(int i, T valor){
		vetor[i] = valor;
	}
	public T getItem(int i){
		retunr vetor[i];
	}

}

Pare um pouco, observe esse código e compare com a implementação da subseção anterior sobre Object. O que mudou? Certamente você percebeu que as referências do Object sumiram (menos a de instanciar o vetor, pois em Java não podemos criar diretamente um vetor genérico: new T[tamanho].

Ao usar essa estrutura, vamos dizer no instanciamento o tipo que desejamos:

public static void main(Strings[] args){

	EstruturaQualquer<String> est1 = new EstruturaQualquer<String>(10);
	est1.setItem(0, "Teste");
	est1.setItem(1, "Teste 2");

	EstruturaQualquer<Gerente> est2 = new EstruturaQualquer<Gerente>(10);
	est2.setItem(0, new Gerente() );
	est2.setItem(1, new Gerente() );
}

Vamos ao exemplo do uso de métodos específicos:

public static void main(Strings[] args){

	[...]

	EstruturaQualquer<Gerente> est2 = new EstruturaQualquer<Gerente>(10);
	est2.setItem(0, new Gerente() );
	est2.setItem(1, new Gerente() );

	double sal = est2.getItem(0).getSalario(); //isso NÃO possui erro
}

Pronto, chegamos ao nosso objetivo. Por se tratar de um assunto novo e abstrato, é recomendado que você implemente os exemplos com Object e Classes Genéricas para internalizar os conceitos. Vamos utilizar esse tipo de codificação para as estruturas a seguir: Pilha, Fila, Listas e Árvores.

Esta foi a nossa revisão, espero que tenha relembrando pontos importantes. Agora é hora de seguir para as estruturas! :)