Olá! Hoje falaremos sobre coisas tão importantes para qualquer programador como estruturas de dados . A Wikipedia diz: Estrutura de dados ( eng. estrutura de dados ) é uma unidade de software que permite armazenar e processar muitos dados do mesmo tipo e/ou logicamente relacionados na computação. A definição é um pouco confusa, mas sua essência é clara. Uma estrutura de dados é um tipo de armazenamento onde armazenamos dados para uso posterior. Há uma grande variedade de estruturas de dados na programação. Muitas vezes, na hora de resolver um problema específico, o mais importante é escolher a estrutura de dados mais adequada para esse fim. E você já conhece muitos deles! Por exemplo, com matrizes . E também com
Map
(que geralmente é traduzido como “dicionário”, “mapa” ou “matriz associativa”). É muito importante entender: as estruturas de dados não estão vinculadas a nenhuma linguagem específica . Estes são simplesmente “projetos” abstratos segundo os quais cada linguagem de programação cria suas próprias classes - implementações dessa estrutura. Por exemplo, uma das estruturas de dados mais famosas é a lista vinculada . Você pode ir à Wikipedia, ler sobre como funciona, quais vantagens e desvantagens tem. Você pode achar sua definição familiar :) “Uma lista vinculada é uma estrutura de dados dinâmica básica em ciência da computação, consistindo de nós, cada um dos quais contém os dados em si e um ou dois links (“links”) para o próximo e/ou lista de nós anterior” Então esta é nossa LinkedList
! Exatamente, é assim :) A estrutura de dados da lista vinculada é implementada na linguagem Java na classe LinkedList
. Mas outras linguagens também implementam listas vinculadas! Em Python é chamado de “ llist
”, em Scala é chamado da mesma forma que em Java - “ LinkedList
“. Uma lista vinculada é uma das estruturas de dados básicas comuns, portanto você pode encontrar sua implementação em qualquer linguagem de programação moderna. A mesma coisa com uma matriz associativa. Aqui está sua definição da Wikipedia: Um array associativo é um tipo de dados abstrato (uma interface para um armazenamento de dados) que permite armazenar pares no formato “(chave, valor)” e suporta as operações de adição de um par, bem como pesquisa e excluindo um par por chave. Não te lembra nada? :) Exatamente, para nós Javaistas, um array associativo é uma interfaceMap
. Mas essa estrutura de dados também é implementada em outras linguagens! Por exemplo, os programadores C# o conhecem pelo nome de “Dicionário”. E na linguagem Ruby é implementado em uma classe chamada “Hash”. Em geral, você entende aproximadamente qual é o significado: uma estrutura de dados é algo comum a toda programação, que é implementada de forma diferente em cada linguagem específica. Hoje estudaremos duas dessas estruturas e veremos como elas são implementadas em Java - pilha e fila.
Pilha em Java
Uma pilha é uma estrutura de dados conhecida. É muito simples e muitos objetos do nosso dia a dia são “implementados” em pilha. Imagine uma situação simples: você mora em um hotel e durante o dia recebe cartas comerciais. Como você não estava no quarto naquele momento, o funcionário do hotel simplesmente colocou as cartas recebidas na sua mesa. Primeiro ele colocou a primeira carta na mesa. Aí veio o segundo e ele colocou em cima do primeiro. Ele colocou a terceira carta que chegou em cima da segunda e a quarta em cima da terceira. Agora, responda a uma pergunta simples: qual carta você lerá primeiro quando chegar ao seu quarto e ver uma pilha sobre a mesa? Isso mesmo, você lerá a carta de cima. Ou seja, aquele que veio por último no tempo . É exatamente assim que uma pilha funciona. Este princípio de operação é denominado LIFO - “último a entrar - primeiro a sair” (“último a entrar, primeiro a sair”). Para que uma pilha pode ser útil? Por exemplo, você está criando algum tipo de jogo de cartas em Java. Um baralho de cartas está sobre a mesa. As cartas jogadas são descartadas. Você pode implementar tanto o baralho quanto o descarte usando duas pilhas. Os jogadores compram cartas do topo do baralho - o mesmo princípio das cartas. Quando os jogadores descartam cartas, novas cartas são colocadas em cima das antigas. Aqui está como seria o primeiro rascunho do nosso jogo, implementado usando uma pilha:public class Card {
public Card(String name) {
this.name = name;
}
private String name;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Card{" +
"name='" + name + '\'' +
'}';
}
}
import java.util.Stack;
public class SimpleCardGame {
// колода
private Stack<Card> deck;
// сброс
private Stack<Card> graveyard;
public Card getCardFromDeck() {
return deck.pop();
}
public void discard(Card card) {
graveyard.push(card);
}
public Card lookTopCard() {
return deck.peek();
}
// ..геттеры, сеттеры и т.д.
}
Como dissemos anteriormente, temos duas pilhas: o baralho e o descarte. A estrutura de dados da pilha é implementada em Java no formato java.util.Stack
. Em nosso jogo de cartas existem 3 métodos que descrevem as ações dos jogadores:
- pegue uma carta do baralho (método
getCardFromDeck()
); - descartar carta (método
discard()
); - olhe para o cartão superior (método
lookTopCard()
). Digamos que esta será a mecânica bônus “Inteligência”, que permitirá ao jogador descobrir qual carta entrará em jogo a seguir.
Stack
:
push()
— adiciona um elemento ao topo da pilha. Quando descartamos uma carta, ela vai para cima das cartas descartadas anteriormente;pop()
— remove o elemento superior da pilha e o retorna. Este método é ideal para implementar a mecânica “o jogador compra uma carta”.peek()
- retorna o elemento do topo da pilha, mas não o remove da pilha
import java.util.Stack;
public class Main3 {
public static void main(String[] args) {
// создаем колоду и добавляем в нее карты
Stack<Card> deck = new Stack<>();
deck.push(new Card("Рагнарос"));
deck.push(new Card("Пират Глазастик"));
deck.push(new Card("Сильвана Ветрокрылая"));
deck.push(new Card("Миллхаус Манашторм"));
deck.push(new Card("Эдвин ван Клифф"));
// создаем сброс
Stack<Card> graveyard = new Stack<>();
// начинаем игру
SimpleCardGame game = new SimpleCardGame();
game.setDeck(deck);
game.setGraveyard(graveyard);
// первый игрок берет 3 карты из колоды
Card card1 = game.getCardFromDeck();
Card card2 = game.getCardFromDeck();
Card card3 = game.getCardFromDeck();
System.out.println("Какие карты достались первому игроку?");
System.out.println(card1);
System.out.println(card2);
System.out.println(card3);
// первый игрок отправляет в сброс 3 своих карты
game.discard(card1);
game.discard(card2);
game.discard(card3);
System.out.println("Какие карты находятся в сбросе?");
System.out.println(game.getGraveyard().pop());
System.out.println(game.getGraveyard().pop());
System.out.println(game.getGraveyard().pop());
}
}
Então adicionamos cinco cartas ao nosso baralho. O primeiro jogador pegou 3 deles. Que cartas ele recebeu? Saída do console:
Card{name='Эдвин ван Клифф'}
Card{name='Миллхаус Манашторм'}
Card{name='Сильвана Ветрокрылая'}
Preste atenção na ordem em que os cartões foram enviados para o console. A carta “Edwin Van Cleiff” foi a última a chegar ao baralho (quinta consecutiva), e foi a carta que o jogador pegou primeiro. “Michhlaus” foi o penúltimo no baralho e seu jogador ficou em segundo. “Sylvanas” acertou o baralho em terceiro lugar e foi para o terceiro jogador. Em seguida, o jogador descarta suas cartas. Primeiro ele derruba Edwin, depois Millhouse, depois Sylvanas. Depois disso, enviamos, uma por uma, para o console as cartas que estão em nosso descarte: Saída para o console:
Card{name='Сильвана Ветрокрылая'}
Card{name='Миллхаус Манашторм'}
Card{name='Эдвин ван Клифф'}
E novamente vemos como a pilha funciona! O descarte em nosso jogo também é uma pilha (assim como o baralho). "Edwin Van Clyffe" foi o primeiro a ser descartado. O segundo a ser largado foi “Millhouse Manastorm” – e ficou em cima de Edwin no descarte. Em seguida, Sylvanas foi descartada - e esta carta ficou em cima de Millhouse. Como você pode ver, não há nada complicado no funcionamento da pilha. No entanto, é necessário conhecer essa estrutura de dados - ela é frequentemente questionada em entrevistas, e muitas vezes são construídas estruturas de dados mais complexas a partir dela.
Fila
Uma fila (ou, em inglês, “Queue”) é outra estrutura de dados comum. Assim como uma pilha, ela é implementada em muitas linguagens de programação, incluindo Java. Qual é a diferença entre uma fila e uma pilha? Sua fila não é baseada no LIFO, mas em outro princípio - FIFO (“primeiro a entrar - primeiro a sair”, “primeiro a entrar - primeiro a sair”) . É fácil de entender, tomando como exemplo... ou pelo menos uma fila comum e real da vida real! Por exemplo, uma fila para a loja. Se houver cinco pessoas na fila, a primeira entrará na loja . Se mais uma pessoa (além das cinco da fila) quiser comprar alguma coisa e entrar na fila, ela entra na loja por último , ou seja, em sexto. Ao trabalhar com uma fila, novos elementos são adicionados ao final, e se você quiser obter um elemento, ele será retirado do início. Este é o princípio básico de seu funcionamento, que você precisa lembrar: o princípio da fila é muito fácil de entender intuitivamente, pois é frequentemente encontrado na vida real. Vale a pena notar separadamente que em Java a fila é representada não por uma classe, mas por uma interface -Queue
. Mas, ao mesmo tempo, uma fila em Java é uma interface que possui muitas implementações. Se olharmos a documentação do Oracle, veremos que 4 interfaces diferentes e uma lista de classes extremamente impressionante são herdadas da fila:
All Known Subinterfaces
BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>
All Known Implementing Classes
AbstractQueue, ArrayBlockingQueue, ArrayDeque
ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue
LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue
PriorityBlockingQueue, PriorityQueue, SynchronousQueue
Que lista grande! Mas, é claro, você não precisa memorizar todas essas classes e interfaces agora - sua cabeça pode explodir :) Veremos apenas alguns dos pontos mais importantes e interessantes. Primeiro, vamos prestar atenção em uma das quatro “subinterfaces” da fila - Deque
. O que há de tão especial nisso? Deque
- Esta é uma fila de mão dupla. Ele estende a funcionalidade de uma fila normal, permitindo adicionar elementos em ambas as extremidades (o início e o fim da fila) e obter elementos de ambas as extremidades da fila. O deque é amplamente utilizado no desenvolvimento. Preste atenção na lista de classes de fila que fornecemos acima. A lista é bastante longa, mas há algo familiar para nós aí?
LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue
Ha, então nosso velho amigo está aqui LinkedList
! Ou seja, implementa a interface Queue
? Mas como ele pode ser uma fila? Afinal LinkedList
, esta é uma lista conectada! É verdade, mas isso não impede que seja uma fila :) Aqui está uma lista de todas as interfaces que ela implementa:
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>
Como você pode ver, LinkedList
ele implementa uma interface Deque
- uma fila bidirecional. Por que isso é necessário? Graças a isso, podemos obter elementos do início e do fim LinkedList
. E também - adicione elementos ao início e ao fim. Aqui estão os métodos herdados LinkedList
da interface Deque
:
peekFirst()
— retorna (mas não remove da fila) o primeiro elemento.peekLast()
— retorna (mas não remove da fila) o último elemento.pollFirst()
- retorna o primeiro elemento da fila e o remove.pollLast()
- retorna o último elemento da fila e o remove.addFirst()
— adiciona um novo elemento ao início da fila.addLast()
— adiciona um elemento ao final da fila.
LinkedList
ele implementa totalmente a funcionalidade de uma fila bidirecional! E se tal funcionalidade for necessária no programa, você saberá que ela pode ser utilizada :) E nossa palestra de hoje está chegando ao fim. Por fim, darei alguns links para leitura adicional. Primeiramente, preste atenção ao artigo dedicado a PriorityQueue - “priority queue”. Esta é uma das implementações mais interessantes e úteis do Queue. Por exemplo, se houver 50 pessoas na fila da sua loja, e 7 delas forem clientes VIP, PriorityQueue
isso permitirá que você as atenda primeiro! Uma coisa muito útil, não concorda? :) Em segundo lugar, não seria supérfluo mencionar mais uma vez o livro de Robert Laforet “Data Structures and Algorithms in Java” . Ao ler o livro, você não apenas aprenderá muitas estruturas de dados (incluindo pilha e fila), mas também implementará muitas delas você mesmo! Por exemplo, imagine se Java não tivesse uma classe Stack. O que você faria se precisasse de tal estrutura de dados para o seu programa? Claro, eu teria que escrever sozinho. Ao ler o livro de Laforet, muitas vezes é isso que você fará. Graças a isso, sua compreensão das estruturas de dados será muito mais ampla do que simplesmente estudar teoria :) Terminamos a teoria por hoje, mas teoria sem prática não é nada! Os problemas não se resolverão sozinhos, então agora é a hora de enfrentá-los! :)
GO TO FULL VERSION