Estruturas de dados em Java - Pilha e Fila

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.

Dentro de nossos métodos, os métodos de classe são chamados 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

Vamos ver como nosso jogo funcionará:

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, LinkedListele 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 LinkedListda 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.

Como você pode ver, LinkedListele 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, PriorityQueueisso 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! :)