Estrutura De Dados E Algoritmos Java

[Vespasiano Jilg]

Algoritmose estruturas de dados so componentes essenciais da cincia da computao. Eles desempenham um papel fundamental no desenvolvimento de software eficiente e na soluo de problemas complexos. Neste artigo, vamos explorar o que so algoritmos e estruturas de dados e fornecer exemplos prticos de implementao em Java.

Estrutura de dados a forma de organizar e guardar dados, ela existe para que determinado dado possa ser utilizado de maneira eficiente, possibilitando uma melhor administrao. O objetivo deste artigo entender como as estruturas de dados funcionam por baixo dos panos, discutir as vantagens e desvantagens de cada uma e ver, em diferentes situaes, qual o tempo de execuo e performance dessas estruturas. Esse conhecimento importante para podermos optar por uma delas em nosso programa, ou seja, escolhendo a soluo mais vivel. Para isso, vamos ver na prtica usando como base um projeto em Java.

Com o Eclipse aberto, vamos comear o nosso primeiro projeto de estrutura de dados. Como exemplo, estaremos trabalhando com uma universidade, onde precisamos guardar e recuperar dados dos alunos. Ou seja, vamos adicion-lo no fim ou no meio de uma lista, remov-lo, ach-lo a partir de seu nmero e assim por diante.

O primeiro passo nesse projeto modelar a Classe "Aluno". Para isso criamos um novo projeto e dentro dele a classe Aluno, que onde guardaremos o nome do aluno, que receberemos no prprio Construtor da Classe.

Em seguida, vamos criar o getter e implementar os mtodos "equals" e "toString", que sero muito importantes. O "equals" o mtodo que serve para comparar dois objetos, no caso alunos. Faremos um casting do object para aluno. O "toString" retorna o nome do aluno:

Ao fazer isso, a primeira estrutura de dados que veremos o Armazenamento Sequencial. A ideia dessa estrutura armazenar um aluno atrs do outro. Teremos um conjunto de espaos (Array), sendo que: o primeiro aluno fica no primeiro espao, o segundo aluno no segundo espao, e assim por diante.

Sabendo disso, vamos criar uma nova Classe, chamada "Vetor", na qual preciso implementar a estrutura de armazenamento sequencial. Alm disso, precisamos inserir um array com 100 posies e implementar os mtodos dos comportamentos desse array:

Os return's j foram inseridos para que possamos compilar o cdigo. Antes de implementar os comportamentos, iremos escrever o mtodo main para testar o Vetor, antes mesmo do cdigo existir. Para isso vamos criar a Classe "VetorTeste":

Agora os dois alunos foram inseridos no array. Mas perceba que o algoritmo que implementamos no muito performtico, pois quanto maior o nmero de alunos inseridos no array, mais demorado ser o mtodo, uma vez que o lao ir percorrer vrias vezes os espaos j preenchidos. Vamos tentar melhor-lo para que no fique dependente da quantidade de elementos na lista. Para isso, vamos usar do seguinte cdigo:

O programa retorna o "Jose", pois ele que est na posio de nmero 1. Se escolhermos a posio 200, o programa retorna um erro com a mensagem "ArrayIndexOutOfBounds", ou seja, estamos tentando acessar uma posio do array que no existe.

Vamos comear a pensar na validao dos dados que vamos passar para o programa. Precisamos que ele retorne, por exemplo, uma mensagem mais amigvel, ao invs de um erro. Criaremos um mtodo auxiliar que ir dizer se uma determinada posio est ocupada ou no:

O nosso prximo desafio o mtodo "remove", que ser parecido com o "adiciona", porm pensando inversamente: retiramos o aluno da posio n e empurramos para a esquerda todos aqueles que vinham depois dele:

O Java j tem uma implementao de Vetor, a classe conhecida por "ArrayList". Ela bem parecida com tudo o que fizemos at agora e funciona como um armazenamento sequencial, possuindo os mtodos implementados nesta aula:

J vimos o Vetor e observamos seus prs e contras e agora vamos aprender sobre uma outra lista. Com ela tentaremos melhorar o cdigo para que essa adio de elementos no meio do array seja um processo mais rpido.

A essa lista ns damos o nome de lista ligada. A diferena dela para o Vetor que neste os elementos esto um do lado do outro na memria, enquanto que na lista ligada eles esto em lugares diferentes, porm um aponta para o outro indicando o prximo.

Ento, dessa forma que iremos desenhar a estrutura, na qual um elemento tambm conhecer o endereo do prximo. Para isso, vamos criar uma Classe "Celula" que possuir um objeto e seu seguinte (do tipo "Celula"). Para facilitar, vamos tambm criar um Construtor e getters (para o elemento) e setters (para o elemento e para a Celula):

Vamos comear imaginando que j temos uma lista com clulas apontando uma para outra. Para uma nova Clula entrar no comeo do array ela deve apontar para sua prxima, ou seja, a primeira do array atual. Ento devemos ter um atributo chamado "primeira". Como a lista comea vazia, essa clula aponta para null:

Na lista vazia, ao adicionarmos uma clula na primeira posio do array, ela dever apontar para null. J quando acrescentamos uma prxima, tambm no comeo, esta apontar para a anterior; e soma-se 1 ao total de elementos:

Para Listas Ligadas, este mtodo um pouco mais complexo. O que nos diz se um elemento o ltimo do array se ele apontar para um null. Para isso necessrio varrer toda a lista. Vamos resolver o problema criando uma seta para o ltimo elemento (da mesma forma que fizemos para o primeiro):

Voltemos ao desafio de inserir no final. Criamos uma nova clula cujo prximo elemento null, afinal ela est sendo adicionada no final do array. Precisamos fazer com que a ltima atual aponte para essa nova.

J aprendemos sobre listas ligadas e duplamente ligadas. Tais listas possuam clulas que apontavam para outras, anteriores e posteriores. Vimos nos exerccios que o Java j tem tudo isso implementado por meio da Classe LinkedList.

Neste momento, veremos uma outra estrutura de dados cuja principal diferena, em relao aos outros tipos de estruturas de dados, guardar os diversos estados de uma aplicao para que no futuro, se necessrio, seja possvel voltar a estes estados. A essa estrutura damos o nome de Pilha.

A Pilha segue a regra de insero de elementos um aps o outro e a remoo funciona da mesma forma, do ltimo para o primeiro elemento. Para comear a implementar, no comeamos do zero. J temos uma parte do cdigo feita, pois a fizemos nos estudos de listas. Vamos utilizar a implementao que o Java nos oferece.

Como vimos, o pop remove o ltimo elemento da pilha. O mtodo peek trabalha em cima desse elemento tambm, porm sem remov-lo, j que ele apenas o retorna. Portanto, se temos a pilha [Mauricio, Marcelo],

O conceito de pilhas amplamente utilizado por compiladores e autmatos, portanto, podemos afirmar que essa estrutura de dados tem muita usabilidade em cincia da computao. O prprio, e muito conhecido, comando "Desfazer" dos editores de texto, de cdigo, de imagens, etc. tem como base as pilhas. Podemos tambm brincar com palavras e inverter a ordem de suas letras utilizando as pilhas.

Agora vamos conhecer as Filas, que se estruturam de modo parecido com as pilhas. Porm, diferente das pilhas, na qual o primeiro elemento a entrar o ltimo a sair, em filas o primeiro a entrar o primeiro a sair.

Neste artigo, vimos na prtica vetores, lista ligada, lista duplamente ligada, pilha e fila. muito importante compreender como uma estrutura funciona por baixo dos panos e, por isso, o estudo de estrutura de dados uma parte fundamental na programao e na formao de profissionais da rea. Aprendendo isso, voc estar preparado para optar pela melhor soluo.

Este livro oferece uma introduo a estruturas de dados e algoritmos, incluindo projeto, anlise e implementao. Em um texto simples e claro, os autores utilizam recursos visuais e cenrios do mundo real, focando as funes mais populares na anlise de algoritmos.

Os selos editoriais do Grupo A abrangem todas as reas do conhecimento tcnico, cientfico e profissional, sempre focando em contedo referenciado e atualizado. So mais de 4 mil obras entre livros impressos, eBooks e audiobooks presentes na formao e atualizao de estudantes e profissionais de lngua portuguesa. Publicamos as mais importantes obras do mundo em diversas reas, como psicologia, psiquiatria, medicina, enfermagem, fisioterapia, educao, engenharia, clculo, qumica, fsica, administrao, marketing, design e muito mais.

Voc adicionou em seu carrinho de compras um livro em formato e-book, que dever ser lido utilizando o aplicativo BOOKSHELF. Caso queira exclu-lo, clique no boto fechar e remova o produto com a identificao E-BOOK.

Mais de 40 anos depois, essa equao permanece sendo verdade. por isso que aspirantes a posies em engenharia de software precisam demonstrar sua compreenso de estruturas de dados ao se candidatarem a um emprego na rea.

Quase todos os problemas exigem que o candidato demonstre uma compreenso profunda das estruturas de dados. No importa se voc acabou de se formar (em uma universidade ou em um bootcamp de programao) ou se voc tem dcadas de experincia.

Em termos simples, uma estrutura de dados um continer que armazena dados em um layout especfico. Esse "layout" permite que a estrutura de dados seja eficiente em algumas operaes e ineficiente em outras. Seu objetivo entender as estruturas de dados de modo que voc consiga escolher a mais adequada para o problema apresentado.

Como as estruturas de dados so usadas para armazenar dados de uma forma organizada, e como os dados so a entidade mais crucial nas cincias da computao, fica claro o verdadeiro valor das estruturas de dados.

Com base em diferentes cenrios, os dados precisam ser guardados em um formato especfico. Temos um punhado de estrutura de dados que satisfazem nossa necessidade de armazenar dados em diferentes formatos.

3a8082e126