Java Deque

Uma fila na computação é uma estrutura de dados da lista de primeiros in_first-out (FIFO). Isso significa adicionar um novo elemento, o elemento é inserido na parte traseira da lista; e para remover um elemento, o elemento é despedido da frente da lista. O elemento frontal também pode ser espiado, o que significa lê -lo, mas não removendo.

Uma pilha em computação é uma estrutura de dados da lista Last-In_First-Out (LIFO). Isso significa adicionar um novo elemento, o elemento é empurrado para a frente da lista; e para remover um elemento, o elemento é saído da frente da lista. O elemento frontal também pode ser espiado, o que significa lê -lo, mas não removendo.

O nome "deque" é a forma curta para "fila de ponta dupla", pronunciada "deck". O deque é um FIFO e uma estrutura de dados da LIFO List em Java. Bem, também em Java, o deque é uma interface da qual as classes podem ser implementadas. Java já tem as seguintes classes implementadas: Arraydeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. A classe Arraydeque foi escolhida para ser estudada neste artigo.

A seguir, são apresentados os métodos correspondentes de Java Arraydeque para fila:

Fila	Arraydeque
enquadre	adicionar
Dequeue	remover
olhadinha	olhadinha

A seguir, são apresentados os métodos correspondentes de Java Arraydeque para a pilha:

Pilha	Arraydeque
empurrar	empurrar
pop	pop
olhadinha	olhadinha

Nota: O método Peek () é o mesmo para ambos os comportamentos. Além disso, remova () e pop () são muito semelhantes; Eles são explicados abaixo.

Construindo um Arraydeque

A classe Arraydeque está no Java.util.* pacote, que deve ser importado. Tem três construtores, dois dos quais são explicados aqui.

Public Arraydeque ()
Isso cria um deque vazio, como mostra o seguinte segmento de código:

Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');

Cinco elementos foram adicionados. O nome do deque aqui é, DQ.

Public Arraydeque (Coleção C)
Este construtor sobrecarregado cria um deque de outro deque. O seguinte segmento de código ilustra o seguinte:

Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');
Arraydeque dq1 = novo Arraydeque(DQ);

DQ1 foi criado a partir do DQ.

Métodos da classe Arraydeque

public boolean add (e e)
Este é o equivalente a Enqueue. Adiciona um elemento no final do deque. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');

Public int size ()
Isso retorna o tamanho (comprimento) do deque. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');
int sz = dq.tamanho();
Sistema.fora.println (sz);

A saída é 5.

public e remover ()
Este é o equivalente a dequeue. Ele remove um elemento da frente da lista. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');
char ch1 = dq.remover(); char ch2 = dq.remover(); char ch3 = dq.remover();
char ch4 = dq.remover(); char ch5 = dq.remover();
Sistema.fora.impressão (CH1); Sistema.fora.print ("); sistema.fora.impressão (CH2); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH3); Sistema.fora.print ("); sistema.fora.impressão (CH4); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH5); Sistema.fora.imprimir(");
Sistema.fora.println ();

A saída é:

F g h i j

mostrando um comportamento FIFO.

Public E Peek ()
Isso lê o elemento na frente do deque sem removê -lo. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.add ('f'); DQ.add ('g'); DQ.add ('h'); DQ.add ('i'); DQ.add ('j');
char ch1 = dq.olhadinha(); char ch2 = dq.olhadinha(); char ch3 = dq.olhadinha();
char ch4 = dq.olhadinha(); char ch5 = dq.olhadinha();
Sistema.fora.impressão (CH1); Sistema.fora.print ("); sistema.fora.impressão (CH2); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH3); Sistema.fora.print ("); sistema.fora.impressão (CH4); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH5); Sistema.fora.imprimir(");
Sistema.fora.println ();

A saída é:

F f f f f

indicando que nada foi removido e o primeiro elemento acabou de ser lido cinco vezes.

Push de vazio público (e e)
Isso adiciona um elemento à frente do deque. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.push ('f'); DQ.push ('g'); DQ.push ('h'); DQ.push ('i'); DQ.push ('j');
char ch1 = dq.remover(); char ch2 = dq.remover(); char ch3 = dq.remover();
char ch4 = dq.remover(); char ch5 = dq.remover();
Sistema.fora.impressão (CH1); Sistema.fora.print ("); sistema.fora.impressão (CH2); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH3); Sistema.fora.print ("); sistema.fora.impressão (CH4); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH5); Sistema.fora.imprimir(");
Sistema.fora.println ();

A saída é:

J i h g f

mostrando um comportamento de vida.

public e pop ()
Isso remove e retorna o primeiro elemento do deque. O programa a seguir ilustra o seguinte:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.push ('f'); DQ.push ('g'); DQ.push ('h'); DQ.push ('i'); DQ.push ('j');
char ch1 = dq.pop (); char ch2 = dq.pop (); char ch3 = dq.pop ();
char ch4 = dq.pop (); char ch5 = dq.pop ();
Sistema.fora.impressão (CH1); Sistema.fora.print ("); sistema.fora.impressão (CH2); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH3); Sistema.fora.print ("); sistema.fora.impressão (CH4); Sistema.fora.imprimir(");
Sistema.fora.impressão (CH5); Sistema.fora.imprimir(");
Sistema.fora.println ();

A saída é:

J i h g f

mostrando um comportamento de vida.

public void foreach (ação do consumidor)
Este método foreach pode ser usado para acessar cada elemento no deque. O programa a seguir o usa para imprimir todos os elementos do deque:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.push ('f'); DQ.push ('g'); DQ.push ('h'); DQ.push ('i'); DQ.push ('j');
DQ.foreach ((item) -> sistema.fora.impressão (item + ""));
Sistema.fora.println ();

A saída é:

J i h g f

O item é uma variável dummy que representa cada elemento no deque. Observe a maneira como foi usada. Observe o uso do operador de seta, -> . A iteração foi feita em ordem inversa.

Iterator iterator ()
Isso retorna um iterador que pode ser usado para remover um elemento dentro do deque. No entanto, essa ação leva mais tempo do que remover um elemento na frente ou atrás do deque. A declaração a seguir retornaria o iterador para os caracteres de um deque.

Iterador iter = dq.iterator ();

Onde o iter é o objeto iterador, e DQ é o objeto Deque.

O iterador tem os seguintes métodos:

boolean hasNext (): retorna true se a iteração tiver mais elementos.

E próximo (): retorna o próximo elemento na iteração.

Void padrão Remover (): Remove da lista, o último elemento retornado por este iterador (a seguir).

Observe que ele não tem um método para inserir um elemento dentro do deque.

Removendo um elemento dentro de Deque

O programa a seguir remove 'h' no meio da lista deque: f, g, h, i, j:

importar java.util.*;
classe pública theClass
public static void main (string [] args)
Arraydeque DQ = novo Arraydeque();
DQ.push ('f'); DQ.push ('g'); DQ.push ('h'); DQ.push ('i'); DQ.push ('j');
Iterador iter = dq.iterator ();
iter.próximo(); iter.próximo(); iter.próximo();
iter.remover();
DQ.foreach ((item) -> sistema.fora.impressão (item + ""));
Sistema.fora.println ();

A saída é:

J eu g f

Observe que o próximo () teve que ser chamado três vezes.

Conclusão

Em Java, o deque é uma coleção FIFO e LIFO. Deque em Java é na verdade uma interface da qual uma classe deve ser implementada antes que o deque possa ser usado. Felizmente, Java já tem as seguintes classes implementadas deque: Arraydeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList. A operação para Arraydeque foi explicada acima.