#AVISOS:

Estou estou remodeando esse repositório e criando uma página web (https://luisaraujo.github.io/Estrutura-de-Dados-em-Java/index.html) para introduzir figuras e animações.

Todos os códigos foram movidos para a pasta Códigos.

---

AULAS COMIGO?

Acesso o superprof: superprof/luisaraujo

INTERESSE EM CURSO DE ESTRUTURA DE DADOS?

Deixe a sua opinião e contato:

Para preencher o formulário leva apenas 1 minutos!

Estrutura de Dados em Java

Esse texto tem por objetivo apoiar o processo de ensino-aprendizagem do componente curricular Estrutura de Dados. O texto tem como base os códigos no repositório. Não há restrições para a ordem da leitura, mas - se você for um estudante que ainda não conhece os tópicos apresentados - recomenda-se ler um capítulo por vez e partir para a implementação na seção overview.

Licença: O material está disponível sob licença: Creative Commons BY

Requisitos: conhecer o Paradigma Orientado a Objeto (POO) e Linguagem em Java.

Obs: Esse documento está em construção, deixe-me saber se há algum erro: luisaraujo.ifba@gmail.com

Sumário

1. Capítulo 1 - Estrutura de Dados
2. Capítulo 2 - Pilha
3. Capítulo 3 - Fila
4. Capítulo 4 - Lista Simplesmente Encadeada
5. Capítulo 5 - Lista Duplamente Encadeada
6. Capítulo 6 - Lista Circular
7. Capítulo 7 - Árvores

1 - 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, Árvore e outros. Sim, esses tipos complexos utilizam tipos primários, mas estamos interessados agora nesses mais complexos.

Como disciplina Estrutura de Dados, embora usemos os tipos primitivos, tem como objetivo apresentar estruturas já consolidadas da área de computação que buscam resolver diversos problemas recorrentes.

É importante ressaltar que uma Estrutura de Dados é formada por Dados (organizados segundo alguma lógica) e operações permitidas, vinculadas a essas dados.

Formalizando:

Estrutura de Dados envolve dados organizados de alguma forma e operações vinculadas aos dados que garantem que os mesmos permaneçam com a mesma 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 que tudo depende do contexto do 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.

1.1 - Modelagem Computacional

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. Assim, muitas vezes, modelamos apenas os elementos essenciais, arte proveniente da abstração: poder de focar em elementos principais, ignorando elementos eventuais ou menos importantes (para um contexto específico).

Desse modo, podemos criar classe - quando falamos em POO - 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, Árvore entre outras estruturas.

1.2 - Revisão POO com Java

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, recomendamos parar a leitura e fazer um curso ou ler materiais específicos sobre POO.

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

Classe

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 gabarito. 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.

1.3 - 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 podemos tratar todas as classes como Objects. 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){
		return 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(); //