Interface Java Deque

Java Deque é uma estrutura de dados que combina uma Fila e uma Pilha comuns. Você pode adicionar e remover elementos tanto na cabeça quanto na cauda do Deque. Na fila “tradicional” você adiciona elementos ao final da linha (após o último elemento) e remove elementos do início da fila. Este princípio é chamado First In First Out (FIFO) e funciona como qualquer fila normal de clientes na vida real. Em Java Queue é uma Interface, uma parte do Collections Framework. Existe também uma importante estrutura de dados chamada Stack, uma lista que trabalha com elementos em princípio totalmente reverso, LIFO — último a entrar, primeiro a sair. É semelhante a uma pilha de pratos, só é possível adicionar ou remover no topo.

Fila vs Deque

Deque é um tipo meio estranho de Fila: você pode adicionar novos elementos tanto no final quanto no início da linha. A mesma história com a remoção: você pode remover o último ou o primeiro elemento desta estrutura. Portanto, parece ser uma mistura de Stack e Queue. O nome “Deque” significa “Fila Dupla”. “Deque” se pronuncia como um “baralho” de cartas e quer saber? É um pouco semelhante a um baralho de cartas real: você pode pegar uma carta do fundo ou do topo desse baralho. Quer adicionar ou remover elementos de ambos os lados de alguma estrutura linear? Use o Deque. O Java 8 ou quase qualquer outra versão o suporta. Imagine um típico tijolo de lego e “torres” de uma coluna feitas de tijolos. Você pode adicionar um novo tijolo no topo da torre ou na parte inferior. Você também pode remover um tijolo de ambos os lados. Aqui temos um exemplo: adicionamos todos os tijolos amarelos ao topo e todos os vermelhos ao fundo. Demonstraremos este exemplo com código Java em breve. Assim, você pode enfileirar e desenfileirar de ambas as extremidades de um Java Deque, o que significa que você pode usar um Deque como fila e pilha. Leia sobre Stack em Java: Java Stack 101: Investigando a classe Stack Leia sobre Queue em Java: Java Queue Interface e suas implementações

Características do Deque

• Deque em Java é uma Interface, cujas implementações fornecem suporte a um array redimensionável. Assim, você tem uma gama de capacidade livre de restrições e pode adicionar novos elementos de acordo com suas necessidades.
• O acesso simultâneo por vários threads não é suportado pelo Deque
• Deque não é thread-safe em caso de ausência de sincronização externa.
• Nenhum elemento nulo é permitido no array deque.

Deque declaração de interface Java

public interface Deque<E> extends Queue<E>

Métodos Java Deque

java.util.Deque é uma interface que estende a interface Java Queue e representa uma fila dupla. Assim, você pode usar todos os métodos Java Queue enquanto trabalha com um Deque. Apesar de Deque não estender a interface Stack, a interface Deque define métodos que permitem que você faça operações típicas de pilha, como push , peek e pop .

• boolean add(element) adiciona um elemento ao final do Deque. Retorna true em caso de sucesso, lança um IllegalStateException se nenhum espaço estiver disponível no momento.
• addFirst(element) adiciona um elemento à cabeça do Deque.
• addLast(element) adiciona um elemento à cauda do Deque.
• offer(element) adiciona um elemento à cauda e retorna um booleano para explicar se a inserção foi bem-sucedida.
• offerFirst(element) adiciona um elemento à cabeça e retorna um booleano para explicar se a inserção foi bem-sucedida.
• offerLast(element) adiciona um elemento à cauda e retorna um booleano para explicar se a inserção foi bem-sucedida.
• iterator() retorna um iterador para o deque.
• descendingIterator() retorna um iterador que tem a ordem inversa para este deque.
• push(element) adiciona um elemento à cabeça.
• pop(elemento) remove um elemento da cabeça e o retorna.
• removeFirst() remove o elemento na cabeça.
• removeLast() remove o elemento na cauda.
• poll() recupera e remove a cabeça da fila representada por este deque (ou seja, o primeiro elemento deste deque), ou retorna null se este deque estiver vazio.
• pollFirst() recupera e remove o primeiro elemento deste deque, ou retorna nulo se este deque estiver vazio.
• pollLast() recupera e remove o último elemento deste deque, ou retorna nulo se este deque estiver vazio.
• peek() recupera, mas não remove, a cabeça da fila representada por este deque (ou seja, o primeiro elemento deste deque), ou retorna null se este deque estiver vazio.
• peekFirst() recupera, mas não remove, o primeiro elemento deste deque, ou retorna null se este deque estiver vazio.
• peekLast() recupera, mas não remove, o último elemento deste deque, ou retorna null se este deque estiver vazio.

Aqui na tabela abaixo todos os métodos são divididos por grupos. Como você pode ver, existem muitos métodos diferentes para adicionar e remover um elemento. Por exemplo, removeFirst() e pop() removem o primeiro elemento de deque. O segundo “veio” da pilha. Isso significa que se você usar seu ArrayDeque apenas como uma pilha, use pop() para remover, push() para adicionar e peek() para examinar. Isso torna seu código mais sensível para outros desenvolvedores.

Implementações Deque

Java Deque é uma interface e possui implementações na API Java Collections:

• java.util.LinkedList //Implementação de lista e Deque
• java.util.ArrayDeque //Implementação Deque, biblioteca Java

A classe LinkedList usa internamente uma lista duplamente vinculada para modelar uma fila ou um deque. A classe ArrayDeque armazena os elementos internamente em um array. Se o número de elementos exceder o volume do array, um novo array é alocado e todos os elementos são movidos. Isso significa que o ArrayDeque cresce conforme as necessidades.

Classe ArrayDeque

A classe ArrayDeque <E> é uma fila bidirecional geral, herdando a funcionalidade da classe AbstractCollection e usando a interface Deque. ArrayDeque fornece a facilidade de usar deque e resizable-array. Inicialmente, o array é inicializado com tamanho 16. Ele é implementado como uma fila bidirecional, onde suporta dois ponteiros, ou seja, o head e o tail. Ele herda a classe AbstractCollection e implementa a interface Deque . Os pontos importantes sobre a classe ArrayDeque são:

• Você pode adicionar ou remover elementos da cauda e da cabeça do ArrayDeque
• Elementos nulos não são permitidos
• ArrayDeque não é thread-safe, na ausência de sincronização externa.
• ArrayDeque não tem restrições de capacidade.

Construtores da classe ArrayDeque

• ArrayDeque() cria uma fila vazia.
• ArrayDeque (Collection <? Extends E> collection) cria uma fila preenchida com elementos da coleção Collection.
• ArrayDeque (capacidade int) cria uma fila com capacidade de capacidade inicial . Se você não especificar a capacidade inicial, a capacidade padrão será 16.

Java Deque Exemplo — ArrayDeque

Lembre-se do exemplo da torre de Lego no início do artigo? Vamos criar uma classe para Construir Torres de uma coluna feitas de Lego Bricks. Os tijolos podem ser vermelhos, amarelos ou azuis. Nossa regra de construção da Torre: colocamos os tijolos vermelhos no fundo e os amarelos no topo. Exemplo de Big Java Deque

//enum with colors
public enum Color {
   RED, YELLOW, BLUE;
}

//class for the standard Lego Brick. You can connect or disconnect the Brick, it has color
public class LegoBrick {
   Color color;
   boolean isConnected;

   public void connect() {
       System.out.println("This brick is connected");
       this.isConnected = true;
   }

   public void disconnect() {
       System.out.println("Disconnected");
       isConnected = false;
   }

   public LegoBrick(Color color, boolean isConnected) {
       this.color = color;
       this.isConnected = isConnected;
   }

   public Color getColor() {
       return color;
   }

   public boolean isConnected() {
       return isConnected;
   }

   @Override
   public String toString() {
       return "LegoBrick{" +
              "color=" + color +
              ", isConnected=" + isConnected +
              '}';
   }
}

Aqui está a nossa classe Tower. Iniciamos uma torre. A torre iniciada depende da quantidade de vermelhos e amarelos. Podemos adicionar tijolo à torre ou removê-lo. Adicionamos tijolo ao topo se for amarelo e adicionamos ao fundo se for vermelho.

import java.util.ArrayDeque;
public class LegoTower {
   ArrayDeque<LegoBrick> myTower;
   int quantityOfReds;
   int quantityOfYellows;

   public void addBrickToTower(LegoBrick newLegoBrick) {
       if (newLegoBrick.getColor() == Color.YELLOW) {
           this.myTower.offerLast(newLegoBrick);
           quantityOfYellows++;
       }
	//we can use addFirst(e)/push(e) instead of offerFirst here
       if (newLegoBrick.getColor() == Color.RED) {
           myTower.offerFirst(newLegoBrick);
           quantityOfReds++;
       }
   }

   public void removeBrickFromTower (LegoBrick legoBrick) {
       if (legoBrick.getColor() == Color.YELLOW) {
           this.myTower.removeLast();
           quantityOfYellows--;
       }
       if (legoBrick.getColor() == Color.RED) {
           myTower.removeFirst();
           quantityOfReds--;
       }
       legoBrick.isConnected = false;

   }

   public LegoTower(int quantityOfReds, int quantityOfYellows) {

       myTower = new ArrayDeque<>();
       this.quantityOfReds = quantityOfReds;
       this.quantityOfYellows = quantityOfYellows;
       for (int i = 0; i < quantityOfReds; i++) {
           LegoBrick redLegoBrick = new LegoBrick(Color.RED, false);
           myTower.addFirst(redLegoBrick);
           redLegoBrick.isConnected = true;
       }
       for (int i = 0; i < quantityOfYellows; i++) {
           LegoBrick yellowLegoBrick = new LegoBrick(Color.YELLOW, false);
           myTower.addLast(yellowLegoBrick);
           yellowLegoBrick.isConnected = true;
       }
   }

   public void setMyTower(ArrayDeque<legobrick> myTower) {
       this.myTower = myTower;
   }

   public void setQuantityOfReds(int quantityOfReds) {
       this.quantityOfReds = quantityOfReds;
   }

   public void setQuantityOfYellows(int quantityOfYellows) {
       this.quantityOfYellows = quantityOfYellows;
   }

   @Override
   public String toString() {
       return "LegoTower{" +
              "myTower=" + myTower +
              ", quantityOfReds=" + quantityOfReds +
              ", quantityOfYellows=" + quantityOfYellows +
              '}';
   }

   public void drawTower() {
       for (LegoBrick i : myTower) {
           System.out.println(i.color);
       }
   }
}


public class Main {
   public static void main(String[] args) {
       LegoBrick legoBrick1 = new LegoBrick(Color.YELLOW, false);
       legoBrick1.connect();
       System.out.println(legoBrick1.toString());
       legoBrick1.disconnect();
       System.out.println(legoBrick1.toString());
       LegoBrick legoBrick2 = new LegoBrick(Color.YELLOW, false);
       LegoBrick legoBrick3 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick4 = new LegoBrick(Color.RED, false);
       LegoBrick legoBrick5 = new LegoBrick(Color.YELLOW, false);

       LegoTower legoTower = new LegoTower(2, 5);
       System.out.println("my Initiated Lego Tower: ");
       legoTower.drawTower();
       legoTower.addBrickToTower(legoBrick1);
       legoTower.addBrickToTower(legoBrick2);
       legoTower.addBrickToTower(legoBrick3);
       legoTower.addBrickToTower(legoBrick4);
       legoTower.addBrickToTower(legoBrick5);
       System.out.println("My LegoTower after adding some elements: ");
       legoTower.drawTower();
       legoTower.removeBrickFromTower(legoBrick1);
       legoTower.removeBrickFromTower(legoBrick3);
       System.out.println("We removed one red and one yellow brick:");
       legoTower.drawTower();

   }

}

O resultado da execução deste programa:

my Initiated LegoTower:

RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW

Process finished with exit code 0

Espere o que?? Por que os vermelhos estão no topo? Não, eles não. Eles apenas imprimiram no console começando do primeiro (inferior) ao último (superior). Então, se você quiser ver algo como na figura com os tijolos acima, você pode alterar o método drawTower da classe LegoTower. É uma tarefa muito fácil!

LinkedList

A interface List mantém a sequência de adição de itens e permite o acesso ao item por índice. Deque é uma fila bidirecional e suporta a adição e remoção de elementos de ambos os lados. LinkedList é conhecido principalmente como uma implementação de List, mas também esta classe implementa o Deque e nos permite criar uma fila bidirecional que consiste em quaisquer objetos, incluindo null. LinkedList é uma coleção de elementos. Podemos vê-lo no código-fonte da classe, desta vez preste atenção aos campos: Aqui adicionamos um exemplo, mas se você quiser aprender mais sobre LinkedList, seja bem-vindo a este artigo do CodeGym .

Implementação de lista encadeada em Java, adicionando e removendo elementos. Exemplo

Vamos experimentar essas operações na prática. Primeiro, a implementação do Java LinkedList: criando um LinkedList de Strings, adicionando 3 elementos. Em seguida, remova um e adicione um no meio.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<string> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

O resultado da execução deste programa:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]