Estruturas de dados: pilha e fila

Oi! Hoje falaremos sobre algo super importante para qualquer programador: estruturas de dados. Wikipedia diz: "Uma estrutura de dados é um formato de organização, gerenciamento e armazenamento de dados que permite acesso e modificação eficientes. Mais precisamente, uma estrutura de dados é uma coleção de valores de dados, as relações entre eles e as funções ou operações que podem ser aplicada aos dados." A definição é um pouco confusa, mas sua essência é clara. Uma estrutura de dados é uma espécie de repositório onde armazenamos dados para uso futuro. Na programação, há uma enorme variedade de estruturas de dados. Ao resolver problemas específicos, muitas vezes o mais importante é escolher a estrutura de dados mais adequada para o problema. E você já conhece muitos deles! Por exemplo, você conhece arrays. E você também está familiarizado comMap(essa estrutura de dados também pode ser chamada de "dicionário" ou "matriz associativa"). É muito importante entender que as estruturas de dados não estão vinculadas a nenhum idioma específico. Eles são simplesmente "esquemas" abstratos que cada linguagem de programação usa para criar suas próprias classes ou implementações de uma estrutura específica. Por exemplo, uma das estruturas de dados mais famosas é uma lista encadeada. Você pode ir à Wikipedia e ler sobre como funciona e quais as vantagens e desvantagens que tem. Talvez sua definição lhe pareça familiar :) "Uma lista encadeada é uma coleção linear de elementos de dados, cuja ordem não é dada por seu posicionamento físico na memória. Em vez disso, cada elemento aponta para o próximo." Isso descreve nosso amado LinkedList, não é? Sim, e é exatamente isso :) Em Java, a estrutura de dados "lista encadeada" é implementada pela LinkedListclasse. Mas outras linguagens também implementam listas encadeadas! Em Python, essa estrutura de dados é chamada de " llist". Em Scala é chamado de " LinkedList", assim como em Java. Uma lista vinculada é uma das estruturas de dados comuns básicas, portanto, você descobrirá que ela é implementada em qualquer linguagem de programação moderna. O mesmo vale para arrays associativos. Aqui está a definição da Wikipedia: "Uma matriz associativa, mapa, tabela de símbolos ou dicionário é um tipo de dados abstrato composto por uma coleção de pares (chave, valor), de modo que cada chave possível apareça no máximo uma vez na coleção." Isso te lembra alguma coisa? :) Sim. Para nós, desenvolvedores Java, um array associativo é oMapinterface. Mas essa estrutura de dados também é implementada em outras linguagens! Por exemplo, os programadores C# o conhecem sob o nome de "Dicionário". E em Ruby, ele é implementado em uma classe chamada "Hash". Bem, você entendeu: estruturas de dados são conceitos universais em programação e cada linguagem de programação os implementa de sua própria maneira. Hoje estudaremos duas dessas estruturas — a pilha e a fila — e veremos como elas são implementadas em Java.

Pilhas em Java

Uma pilha é uma estrutura de dados bem conhecida. É muito simples. Alguns itens em nossas vidas diárias são "implementados" como uma pilha. Imagine esta situação simples: você está hospedado em um hotel e, ao longo do dia, recebeu algumas cartas comerciais. Você não estava em seu quarto no momento, então o recepcionista do hotel simplesmente colocou as cartas recebidas em sua mesa. Primeiro, ele colocou a primeira carta na mesa. Então chegou uma segunda carta e ele a colocou em cima da primeira. Ele colocou a terceira letra em cima da segunda e a quarta em cima da terceira. E agora, responda a uma pergunta simples: qual carta você vai ler primeiro quando voltar para o seu quarto e ver a pilha sobre a mesa? Certo, você vai ler o mais altocarta. Ou seja, aquele que chegou mais recentemente . É exatamente assim que uma pilha funciona. Este princípio é chamado de "último a entrar, primeiro a sair" (LIFO) . Para que servem as pilhas? Bem, suponha que você esteja 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 usar duas pilhas para implementar o baralho de compra e a pilha de descarte. Os jogadores pegam suas cartas do topo do baralho, seguindo o mesmo princípio das cartas comerciais. Quando os jogadores colocam cartas na pilha de descarte, as novas cartas descartadas são colocadas em cima das antigas. Aqui está nossa primeira tentativa de jogo, implementada com base em 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 {

   // Draw deck
   private Stack<Card> deck;
  
   // Discard pile
   private Stack<Card> discardPile;

   public Card getCardFromDeck() {
       return deck.pop();
   }

   public void discard(Card card) {
       discardPile.push(card);
   }

   public Card lookAtTopCard() {

       return deck.peek();
   }
  
   // ...getters, setters, etc.
}

Como dissemos anteriormente, temos duas pilhas: uma pilha de compra e uma pilha de descarte. Em Java, a estrutura de dados da pilha é implementada na java.util.Stackclasse. Nosso jogo de cartas possui 3 métodos que descrevem as ações dos jogadores:

• pegue uma carta do baralho ( getCardFromDeck()método)
• descartar uma carta ( discard()método)
• olhe para o cartão superior ( lookAtTopCard()método). Digamos que este seja um bônus de "Inteligência" que permite ao jogador descobrir qual carta virá a seguir no jogo.

Dentro de nossos métodos, chamamos os seguintes métodos da classe Stack:

• push()— adiciona um item ao topo da pilha. Quando mandamos uma carta para a pilha de descarte, ela vai para o topo da pilha
• pop()— remove o elemento superior da pilha e o retorna. Este método é perfeito para implementar ações nas quais 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) {

       // Create a deck and add cards to it
       Stack<Card> deck = new Stack<>();
       deck.push(new Card("Ragnaros"));
       deck.push(new Card("Patches the Pirate"));
       deck.push(new Card("Sylvanas Windrunner"));
       deck.push(new Card("Millhouse Manastorm"));
       deck.push (new Card ("Edwin VanCleef"));

       // Create the discard pile
       Stack<Card> discardPile = new Stack<>();

       // Start the game
       SimpleCardGame game = new SimpleCardGame();
       game.setDeck(deck);
       game.setDiscardPile(discardPile);

       // The first player draws 3 cards from the deck
       Card card1 = game.getCardFromDeck();
       Card card2 = game.getCardFromDeck();
       Card card3 = game.getCardFromDeck();

       System.out.println("Which cards went to the first player?");
       System.out.println(card1);
       System.out.println(card2);
       System.out.println(card3);

       // The first player discards 3 of his cards
       game.discard(card1);
       game.discard(card2);
       game.discard(card3);

       System.out.println("What cards are in the discard pile?");
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
       System.out.println(game.getDiscardPile().pop());
   }
}

Adicionamos cinco cartas ao nosso baralho. O primeiro jogador pegou 3 deles. Quais cartas ela recebeu? Saída do console:

Card{name='Edwin VanCleef"}
Card{name='Millhouse Manastorm'}
Card{name='Sylvanas Windrunner'}

Preste atenção na ordem em que as cartas são exibidas no console. A carta "Edwin VanCleef" foi para o baralho por último (era a quinta carta), e foi a carta que o jogador comprou primeiro. "Millhouse" foi o penúltimo no baralho, e o jogador empatou em segundo. "Sylvanas" foi para o terceiro baralho de cima, e foi a terceira carta que o jogador comprou. Em seguida, o jogador descarta as cartas. Primeiro, ela descarta Edwin, depois Millhouse, depois Sylvanas. Em seguida, exibimos as cartas em nossa pilha de descarte, uma a uma: Saída do console:

Card{name='Sylvanas Windrunner'}
Card{name='Millhouse Manastorm'}
Card{name='Edwin VanCleef"}

Mais uma vez, vemos como uma pilha funciona! Em nosso jogo, a pilha de descarte também é uma pilha (assim como o baralho de compra). "Edwin VanCleef" foi descartado primeiro. A segunda carta descartada foi Millhouse Manastorm, e foi colocada em cima de Edwin na pilha de descarte. Então Sylvanas foi descartada e esta carta foi colocada em cima de Millhouse. Como você pode ver, não há nada complicado em uma pilha. Ainda assim, você precisa conhecer essa estrutura de dados — muitas vezes é questionada durante entrevistas de emprego e geralmente é a base para a construção de estruturas de dados mais complexas.

Fila em Java

Uma fila é outra estrutura de dados comum. Além das pilhas, muitas linguagens de programação, incluindo Java, também implementam a estrutura de dados de fila. Qual é a diferença entre uma fila e uma pilha? Uma fila não é baseada no princípio LIFO, mas sim no princípio FIFO ("primeiro a entrar, primeiro a sair"). Este princípio é fácil de entender considerando, por exemplo, uma linha comum, ou fila, na vida real! Por exemplo, uma fila no supermercado. Se houver cinco pessoas na fila, o primeiro a ser atendido será aquele que entrou primeiro na fila . Se outra pessoa (além de cinco já na fila) quiser comprar alguma coisa e entrar na fila, ela será atendida por último, ou seja, sexto. Ao trabalhar com uma fila, novos elementos são adicionados à cauda (atrás) e, se você deseja obter um elemento, ele será retirado da cabeça (frente). Este é o princípio básico que você precisa lembrar sobre como uma fila funciona. A operação de uma fila é muito intuitiva, pois encontramos filas frequentemente na vida real. Vale destacar separadamente que em Java uma fila é representada não por uma classe, mas por uma interface: Fila. Além do mais, há muitas implementações dessa interface de fila em Java. Se olharmos a documentação do Oracle, veremos que 4 interfaces diferentes, assim como uma lista de classes extremamente impressionante, herdam a interface Queue:

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 :) Consideraremos apenas alguns dos pontos mais importantes e interessantes. Primeiro, vamos prestar atenção em uma das quatro "subinterfaces" do Queue: Deque . O que o torna tão especial? A Dequeé uma fila dupla. Ele estende a funcionalidade de uma fila regular, permitindo adicionar elementos a ambas as extremidades (no início e no final) e retirar elementos de ambas as extremidades da fila. Filas duplas são amplamente utilizadas no desenvolvimento de software. Preste atenção na lista de classes de filas que fornecemos acima. A lista é bastante longa, mas contém algo familiar?

LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue

Ha! Aqui está o nosso velho amigo LinkedList! Então, ele implementa a interface Queue? Mas como pode ser uma fila? Afinal, a LinkedListé uma lista encadeada! É verdade, mas isso não impede que seja uma fila :) Aqui está uma lista de todas as interfaces que ele implementa:

All implemented interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>

Como você pode ver, LinkedListimplementa a Dequeinterface (novamente, isso significa fila dupla). Por que isso é necessário? Isso nos permite obter elementos do início e do fim de um arquivo LinkedList. Também nos permite adicionar elementos ao início e ao fim. Aqui estão os métodos que LinkedListobtém da Dequeinterface:

• peekFirst()— retorna o primeiro elemento (mas não o remove da fila).
• peekLast()— retorna o último elemento (mas não o remove da fila).
• pollFirst()— retorna o primeiro elemento da fila e o remove.
• pollLast()— retorna o último item da fila e o remove.
• addFirst()— adiciona um novo item à frente da fila.
• addLast()— adiciona um item ao final da fila.

Como você pode ver, LinkedListimplementa totalmente a funcionalidade de uma fila dupla! E você precisa dessa funcionalidade em seu programa, saberá onde encontrá-la :) A aula de hoje está chegando ao fim. Concluindo, darei a vocês alguns links para leitura adicional. Primeiro, preste atenção a este artigo sobre PriorityQueue . Esta é uma das Queueimplementações mais interessantes e úteis. Por exemplo, suponha que haja 50 pessoas esperando na fila de sua loja e 7 delas sejam clientes VIP. Uma PriorityQueue permitirá que você os atenda primeiro! Coisas muito úteis, certo? :) Em segundo lugar, não faria mal mencionar mais uma vez o livro de Robert Lafore "Data Structures and Algorithms in Java". Lendo este livro, você não apenas aprenderá muitas estruturas de dados (incluindo pilha e fila), mas também implementará muitas delas você mesmo! Por exemplo, e se Java não tivesse uma classe Stack? O que você faria se precisasse de tal estrutura de dados para o seu programa? Você teria que escrevê-lo sozinho, é claro. Ao ler o livro de Lafore , você frequentemente fará exatamente isso. Como resultado, sua compreensão das estruturas de dados será muito mais profunda do que você obteria com um simples estudo da teoria :) Estamos encerrando a teoria por hoje, mas teoria sem prática não é nada! As tarefas não vão se resolver sozinhas, então é hora de enfrentá-las! :)