deque java deque implementation
Este tutorial fornece uma explicação detalhada de Deque ou “Fila dupla” em Java. Você aprenderá sobre Deque Interface, Métodos API, Implementação, etc:
O Deque ou “fila dupla” em Java é uma estrutura de dados na qual podemos inserir ou excluir elementos de ambas as extremidades. O deque é uma interface em Java pertencente ao pacote java.util e implementa a interface java.queue.
Podemos implementar deque como uma estrutura de pilha (Last In, First Out) ou como uma fila (first-in-first-out). Deque é mais rápido que Stack e / ou LinkedList. Deque é pronunciado como “baralho” como no “baralho de cartas”.
=> Verifique aqui para ver A-Z dos tutoriais de treinamento de Java aqui.
O que você aprenderá:
Por volta de Java
Uma coleção típica deque terá a seguinte aparência:
perguntas da entrevista para desenvolvedores .net
Deque é usado principalmente para implementar estruturas de pilha, fila ou lista de dados. Também pode ser usado para implementar filas prioritárias. Os recursos de desfazer ou histórico mais presentes nos navegadores da web podem ser implementados usando deques.
Interface Java Deque
O diagrama abaixo mostra a hierarquia para a fila dupla ou deque. Conforme mostrado no diagrama abaixo, a interface Deque se estende à interface Queue que, por sua vez, estende a interface Collection.
Para usar uma interface deque em nosso programa, temos que importar o pacote que contém a funcionalidade deque usando uma instrução de importação como mostrado abaixo.
import java.util.deque; ou
import java.util.*; Como o deque é uma interface, precisamos de classes concretas para implementar a funcionalidade da interface deque.
As duas classes abaixo implementam a interface deque.
- ArrayDeque
- LinkedList
Portanto, podemos criar objetos deque usando essas duas classes, conforme mostrado abaixo:
Deque numdeque = new ArrayDeque (); Deque strDeque = new LinkedList (); Assim, uma vez que os objetos deque acima sejam criados com sucesso, eles podem usar a funcionalidade da interface deque.
Abaixo estão alguns pontos importantes a serem observados sobre o deque:
- A interface Deque oferece suporte a matrizes redimensionáveis que podem crescer conforme necessário.
- Array deques não permite o uso de valores nulos.
- Deque não oferece suporte a acesso simultâneo por mais de um encadeamento.
- Deque não é seguro para thread, a menos que uma sincronização externa seja fornecida.
ArrayDeque em Java
ArrayDeque pertence ao pacote java.util. Ele implementa a interface deque. Internamente, a classe ArrayDeque usa uma matriz redimensionável dinamicamente que cresce conforme o número de elementos aumenta.
O diagrama abaixo mostra a hierarquia da classe ArrayDeque:
Conforme mostrado no diagrama, a classe ArrayDeque herda a classe AbstractCollection e implementa a interface Deque.
o que significa incompatibilidade de chave de segurança de rede
Podemos criar um objeto deque usando a classe ArrayDeque conforme mostrado abaixo:
Deque deque_obj = new ArrayDeque (); e exemplo
O programa Java a seguir demonstra um exemplo simples para entender melhor o deque. Aqui, usamos a classe ArrayDeque para instanciar a interface deque. Acabamos de adicionar alguns elementos ao objeto deque e depois imprimi-los usando um loop forEach.
import java.util.*; public class Main { public static void main(String() args) { //Creat a Deque and add elements Deque cities_deque = new ArrayDeque(); cities_deque.add('Delhi'); cities_deque.add('Mumbai'); cities_deque.add('Bangaluru'); System.out.println('Deque Contents:'); //Traverse the Deque for (String str : cities_deque) { System.out.print(str + ' '); } } } Resultado:
A API E MÉTODOS Java
Como a interface deque implementa uma interface de fila, ela suporta todos os métodos da interface de fila. Além disso, a interface deque fornece os seguintes métodos que podem ser usados para realizar várias operações com o objeto deque.
Vamos resumir esses métodos na tabela abaixo.
| Método | Protótipo de Método | Descrição |
|---|---|---|
| getFirst | E getFirst () | Recupere o primeiro elemento do deque sem removê-lo. |
| adicionar | adição booleana (E e) | Adiciona o elemento e fornecido ao deque (na cauda) sem violar as restrições de capacidade e retorna true se for bem-sucedido. Lança IllegalStateException se não houver espaço disponível no deque. |
| addFirst | void addFirst (E e) | Adiciona determinado elemento e à frente da fila sem violar as restrições de capacidade. |
| addLast | void addLast (E e) | Adiciona o elemento e ao último do deque sem violar as restrições de capacidade. |
| contém | boolean contém (objeto o) | Verifica se o deque contém o elemento o fornecido. Retorna verdadeiro se sim. |
| descendingIterator | Iterator descendingIterator () | Este método retorna o iterador de ordem reversa para o deque. |
| elemento | Elemento E () | Retorna o primeiro elemento ou cabeça do deque. Observe que isso não exclui o elemento. |
| Obtenha o último | E getLast () | Obtém o último elemento do deque sem removê-lo. |
| iterador | Iterator iterator () | Retorna um iterador padrão sobre os elementos do deque. |
| oferta | oferta booleana (E e) | Adiciona determinado elemento e ao deque (como uma cauda) sem violar as restrições de capacidade. Retorna verdadeiro em caso de sucesso e falso em caso de falha. |
| offerFirst | oferta booleanaFirst (E e) | Insira o elemento e fornecido na frente do deque sem violar as restrições de capacidade. |
| offerLast | oferta booleanaLast (E e) | Insira o elemento e fornecido no final do deque sem violar as restrições de capacidade. |
| olhadinha | E peek () | Retorna o cabeçalho do deque (primeiro elemento) ou nulo se uma fila estiver vazia. ** não exclui a cabeça |
| peekFirst | E peekFirst () | Retorna o primeiro elemento no deque sem excluí-lo. Retorna nulo se o deque estiver vazio. |
| peekLast | E peekLast () | Recupera o último elemento no deque sem removê-lo. Retorna nulo se o deque estiver vazio. |
| enquete | E poll () | Exclui e retorna a cabeça do deque. Retorna nulo se o deque estiver vazio. |
| pollFirst | E pollFirst () | Retorna e remove o primeiro elemento do deque. Retorna nulo se o deque estiver vazio. |
| pollLast | E pollLast () | Retorna e remove o último elemento do deque. Retorna nulo se o deque estiver vazio. |
| pop | E pop () | Retire o elemento da pilha que é representado usando deque. |
| Empurre | void push (E e) | Empurre o elemento e fornecido para a pilha representada usando deque sem violar as restrições de capacidade. Retorna verdadeiro em caso de sucesso ou IllegalStateException se nenhum espaço estiver disponível no deque. |
| retirar | E remove () | Retire e devolva a cabeça do deque. |
| retirar | boolean remove (objeto o) | Remova a primeira ocorrência do elemento o fornecido do deque. |
| removeFirst | E removeFirst () | Remova e devolva o primeiro elemento do deque. |
| removeFirstOccurrence | boolean removeFirstOccurrence (Object o) | Remove a primeira ocorrência do elemento o fornecido do deque. |
| removeLast | E removeLast () | Recupera e exclui o último elemento no deque. |
| removeLastOccurrence | boolean removeLastOccurrence (Object o) | Exclui a última ocorrência de um determinado elemento o do deque. |
| Tamanho | tamanho interno () | Retorna o tamanho ou número de elementos no deque. |
E implementação em Java
Vamos agora implementar um programa Java para demonstrar alguns dos principais métodos deque discutidos acima.
Neste programa, usamos um deque do tipo String e, em seguida, adicionamos elementos a esse deque usando vários métodos como add, addFirst, addLast, push, offer, offerFirst, etc. Em seguida, exibimos o deque. Em seguida, definimos os iteradores padrão e reversos para o deque e atravessamos o deque para imprimir os elementos.
Também usamos os outros métodos como contains, pop, push, peek, poll, remove, etc.
import java.util.*; public class Main { public static void main(String() args) { //Declare Deque object Deque deque = new LinkedList(); // add elements to the queue using various methods deque.add('One'); //add () deque.addFirst('Two'); //addFirst () deque.addLast('Three'); //addLast () deque.push('Four'); //push () deque.offer('Five'); //offer () deque.offerFirst('Six'); //offerFirst () deque.offerLast('Seven'); //offerLast () System.out.println('Initial Deque:'); System.out.print(deque + ' '); // Iterate using standard iterator System.out.println('
Deque contents using Standard Iterator:'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Iterate using Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Deque contents using Reverse Iterator:'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek () method System.out.println('
Deque Peek:' + deque.peek()); System.out.println('
Deque,After peek:' + deque); // Pop () method System.out.println('
Deque Pop:' + deque.pop()); System.out.println('
Deque,After pop:' + deque); // contains () method System.out.println('
Deque Contains Three: ' + deque.contains('Three')); deque.removeFirst(); //removeFirst () deque.removeLast(); //removeLast () System.out.println('
Deque, after removing ' + 'first and last elements: ' + deque); } }Resultado:
perguntas frequentes
P # 1) O Deque é thread-safe Java?
Responda: ArrayDeque não é seguro para threads. Mas a interface BlockingDeque na classe java.util.concurrent representa o deque. Este deque é thread-safe.
Q # 2) Por que o Deque é mais rápido do que empilhar?
Responda: A interface ArrayDeque que implementa a interface deque é eficiente em termos de memória, pois não precisa manter um controle dos nós anteriores ou seguintes. Além disso, é uma implementação redimensionável. Portanto, deque é mais rápido que a pilha.
Q # 3) Deque é uma pilha?
Responda: Um deque é uma fila dupla. Ele permite o comportamento LIFO e, portanto, pode ser implementado como uma pilha, embora não seja uma pilha.
Q # 4) Onde o Deque é usado?
Responda: Um deque é usado principalmente para implementar recursos como desfazer e histórico.
P # 5) O Deque é circular?
Responda: Sim, Deque é circular.
Conclusão
Isso conclui nosso tutorial sobre a interface Deque em Java. A interface deque é implementada por uma estrutura de dados deque que é uma coleção que pode inserir e excluir elementos de ambas as extremidades.
As duas classes, ou seja, ArrayDeque e LinkedList implementam a interface deque. Podemos usar essas classes para implementar a funcionalidade da interface deque.
=> Visite aqui a série exclusiva de tutoriais de treinamento em Java.
Leitura recomendada
- Double Ended Queue (Deque) em C ++ com exemplos
- Java Queue - métodos de fila, implementação de fila com exemplos
- Tutorial Java Priority Queue - Implementação e exemplos
- Estrutura de dados da fila de prioridade em C ++ com ilustração
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de dados da fila circular C ++: implementação e aplicativos
- Tutorial JAVA para iniciantes: mais de 100 tutoriais práticos em vídeo Java
- Fila prioritária em STL