Aqui vamos discutir a interface Java Queue. Você descobrirá o que é a estrutura de dados da Queue , como ela é representada em Java, quais métodos são os mais importantes para todas as filas. Além disso, quais implementações de Queue estão na linguagem Java. Depois disso, examinamos mais de perto as implementações mais importantes e as aprendemos com exemplos.
Estrutura de dados da fila
Uma Fila é uma estrutura de dados abstrata linear com a ordem particular de execução das operações — Primeiro a Entrar, Primeiro a Sair (FIFO). Isso significa que você pode adicionar um elemento (ou enfileirar, colocar na fila) apenas no final da estrutura e retirar um elemento (desenfileirar ou remover da fila) apenas no início. Você pode imaginar a estrutura de dados da fila com muita facilidade. Parece uma fila ou fila de clientes na vida real. O cliente que chegou primeiro, também será atendido primeiro. Se você tiver quatro pessoas na fila do McDonalds ou de qualquer outro lugar, o primeiro a entrar na fila será o primeiro a chegar à loja. Se o novo cliente vier, ele será o 5º na fila para comprar hambúrgueres. Portanto, ao trabalhar com uma fila, novos elementos são adicionados ao final e, se você deseja obter um elemento, ele será retirado do início. Este é o princípio principal do trabalho de estrutura de dados de fila clássica.
Fila em Java
Fila em Java é uma interface. De acordo com a documentação do Oracle, a interface Queue possui 2 superinterfaces, 4 interfaces diferentes que herdam da fila e uma lista de classes extremamente impressionante.
O que isso significa? Em primeiro lugar, o Java Queue faz parte do Collection Framework e implementa a interface Collection. Portanto, ele suporta todos os métodos da interface Collection, como inserção, exclusão e assim por diante. Queue implementa a interface Iterable, que permite que um objeto seja o alvo da instrução "for-each loop".
Métodos de Fila Java
A Fila declara vários métodos. Como métodos da interface, eles devem ser representados em todas as classes que implementam Fila. Os métodos de fila mais importantes, Java:
Boolean offer() – insere um novo elemento na fila se possível
Boolean add(E e) – insere um novo elemento na fila se possível. Retorna verdadeiro em caso de sucesso e lança um IllegalStateException se não houver espaço.
Object poll() – recupera e remove um elemento da cabeça do. Retorna nulo se a fila estiver vazia.
Object remove() – recupera e remove um elemento do início da fila.
Object peek() – recupera, mas não remove um elemento do início da fila. Retorna nulo se a fila estiver vazia.
Object element() – recupera, mas não remove um elemento do início da fila.
Subinterfaces do Java Queue
A interface da fila é herdada por 4 subinterfaces – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Você pode dividi-las em 3 grupos: Deques, Filas Bloqueadoras e Filas de Transferência com BloqueioDeque pertencentes às duas primeiras. Vamos dar uma olhada nesses grupos.
Deques
Deque significa Fila Dupla e suporta a adição ou remoção de qualquer extremidade dos dados como uma fila (primeiro a entrar, primeiro a sair/FIFO) ou da cabeça como outra estrutura de dados popular chamada pilha ( último a entrar , primeiro a sair/LIFO). Classes que implementam a Interface Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Bloqueio de Filas
Uma fila de bloqueio é uma fila que bloqueia um thread em dois casos:
thread está tentando obter elementos de uma fila vazia
thread está tentando colocar elementos na fila completa
Quando um thread tenta obter itens de uma fila vazia, ele espera até que algum outro thread coloque os itens na fila. Da mesma forma, quando um thread tenta colocar elementos em uma fila cheia, ele espera até que algum outro thread tire os elementos da fila para obter espaço livre para os elementos. Claro, o conceito de "fila cheia" implica que a fila tem um tamanho limitado, que geralmente é especificado no construtor. Filas de bloqueio padrão incluem LinkedBlockingQueue, SynchronousQueue e ArrayBlockingQueue. Implementando as classes da interface BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeé uma subinterface para BlockingQueue. BlockingDeque como BlockingQueue é uma fila de bloqueio, mas bidirecional. Portanto herda as propriedades da interface Deque. É orientado para execução multi-threaded, não permite zero elementos e a capacidade pode ser limitada. As implementações da interface BlockingDeque bloqueiam a operação de obter elementos se a fila estiver vazia e adicionar um elemento na fila se ela estiver cheia.
filas de transferência
A interface TransferQueue estende a interface BlockingQueue. No entanto, ao contrário da implementação das filas da interface BlockingQueue, onde os encadeamentos podem ser bloqueados se a fila estiver vazia (leitura) ou se a fila estiver cheia (gravação), as filas da interface TransferQueue bloqueiam o fluxo de gravação até que outro fluxo recupere o elemento. Use um método de transferência para isso. Ou seja, a implementação de BlockingQueue garante que o elemento criado pelo Producer deve estar na fila, enquanto a implementação de TransferQueue garante que o elemento Producer seja “recebido” pelo Consumer. Há apenas uma implementação Java oficial da interface TransferQueue — LinkedTransferQueue.
Implementações de Filas Java
Existem muitas classes que implementam a interface Queue:
AbstractQueue de acordo com a documentação do Queue Java 8, esta classe abstrata fornece implementações básicas de algumas operações de fila. Não permite elementos nulos. Existem mais 3 métodos add, remove e element baseados em Queue classic offer , poll e peek , respectivamente. No entanto, eles lançam exceções em vez de indicar falha por meio de retornos falsos ou nulos.
ArrayBlockingQueue — uma fila de bloqueio FIFO de tamanho fixo suportada por um array
ArrayDeque — implementação de array redimensionável da interface Deque
ConcurrentLinkedDeque — um deque simultâneo ilimitado baseado em nós vinculados.
ConcurrentLinkedQueue — uma fila thread-safe ilimitada baseada em nós vinculados.
DelayQueue — uma fila de agendamento baseada em tempo apoiada por um heap
LinkedBlockingDeque — a implementação simultânea da interface Deque.
LinkedBlockingQueue — uma fila de bloqueio FIFO opcionalmente limitada apoiada por nós vinculados
LinkedList — implementação de lista duplamente vinculada das interfaces List e Deque. Implementa todas as operações de lista opcionais e permite todos os elementos (incluindo null)
LinkedTransferQueue — uma TransferQueue ilimitada baseada em nós vinculados
PriorityBlockingQueue — uma fila de prioridade de bloqueio ilimitada apoiada por um heap
PriorityQueue — uma fila de prioridade baseada na estrutura de dados heap
SynchronousQueue — uma fila de bloqueio onde cada operação de inserção deve esperar por uma operação de remoção correspondente por outro thread e vice-versa.
As implementações mais populares são LinkedList, ArrayBlockingQueue e PriorityQueue. Vamos olhar para eles e fazer alguns exemplos para melhor compreensão.
LinkedList
A classe LinkedList em Java implementa as interfaces List e Deque. Portanto, é uma combinação de List e Deque, uma fila bidirecional, que suporta adicionar e remover elementos de ambos os lados. Em Java, LinkedList é uma lista duplamente vinculada: cada elemento da lista chama Node e contém um objeto e referências a dois objetos vizinhos — o anterior e o próximo. Você pode dizer que LinkedList não é muito eficaz em termos de uso de memória. Isso é verdade, mas essa estrutura de dados pode ser útil no caso da execução de operações de inserção e exclusão. No entanto, isso acontece apenas se você usar iteradores para eles (neste caso, ocorre em tempo constante). As operações de acesso por índice são realizadas buscando do início ao fim (o que for mais próximo) até o elemento desejado. No entanto, não se esqueça dos custos adicionais para armazenar referências entre elementos. Portanto, LinkedList é a implementação de fila mais popular em Java. É uma implementação de List e Deque também e nos permite criar uma fila bidirecional que consiste em quaisquer objetos, incluindo null. LinkedList é uma coleção de elementos.
LinkedList() sem parâmetros é usado para construir uma lista vazia. LinkedList(Collection<? extends E> c) serve para criar uma lista contendo os elementos da coleção especificada, em ordem, eles são retornados pelo iterador da coleção.
Principais métodos LinkedList:
add(E element) Acrescenta o elemento especificado ao final desta lista;
add(int index, E element) Insere o elemento no índice de posição especificado;
get(int index) Retorna o elemento na posição especificada nesta lista;
remove(int index) Remove o elemento que está na posição index;
remove(Object o) Remove a primeira ocorrência do elemento ?o desta lista se estiver lá.
remove() Recupera e remove o primeiro elemento da lista.
addFirst(), addLast() adiciona um elemento ao início/fim de uma lista
clear() remove todos os elementos da lista
contains(Object o) retorna verdadeiro se a lista contiver o elemento o.
indexOf(Object o) retorna o índice da primeira ocorrência do elemento o, ou -1 se não estiver na lista.
set(int index, elemento E) substitui o elemento na posição do índice pelo elemento
size() Retorna a quantidade de elementos na lista.
toArray() retorna um array contendo todos os elementos da lista do primeiro ao último elemento.
pop() que retira um elemento da pilha (representado pela lista)
push(E e) que coloca um elemento na pilha (representado por esta lista)
Java Queue Example — LinkedList (colocando e removendo elementos de maneiras diferentes)
import java.util.*;
public class LinkedListTest {
public static void main(String args[]){
LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(4);
System.out.println("three added elements: " + myLinkedList);
//put one element into the head, not to the tail:
myLinkedList.push(5);
System.out.println("The new element last in will be the first: " + myLinkedList);
//add new element at the specified position:
myLinkedList.add(4,3);
//put one element into the head, not to the tail (same as push):
myLinkedList.addFirst(6);
System.out.println(myLinkedList);
//now remove element no 2 (it is 1):
myLinkedList.remove(2);
System.out.println(myLinkedList);
//now remove the head of the list
myLinkedList.pop();
System.out.println(myLinkedList);
//remove with the other method
myLinkedList.remove();
System.out.println(myLinkedList);
//and with one more
myLinkedList.poll();
System.out.println(myLinkedList);
}
}
Fila de prioridade
PriorityQueue não é exatamente a fila no significado geral FIFO. Os elementos da fila de prioridade são ordenados de acordo com sua ordem natural, ou por um Comparator fornecido no momento da construção da fila, dependendo de qual construtor é utilizado. No entanto, não é uma ordem como poderia ser em uma estrutura linear como uma lista (do maior para o menor ou vice-versa). Uma fila de prioridade baseada em um heap mínimo de prioridade. Heap é uma estrutura de dados baseada em árvore binária. A prioridade de cada pai é maior do que as prioridades de seus filhos. Uma árvore é chamada de binário completo se cada pai não tiver mais de dois filhos e o preenchimento dos níveis for de cima para baixo (do mesmo nível - da esquerda para a direita). A pilha binária se reorganiza toda vez que um novo elemento é adicionado ou removido dela. No caso do min-heap, o menor elemento vai para a raiz independentemente da ordem de sua inserção. Fila de prioridade baseada neste min-heap, então se tivermos uma PriorityQueue de números inteiros, seu primeiro elemento será o menor desses números. Se você excluir a raiz, a próxima menor se tornará uma raiz.
Principais métodos PriorityQueue:
boolean add(object) insere o elemento especificado na fila de prioridade. Retorna verdadeiro em caso de sucesso. Se a fila estiver cheia, o método lançará uma exceção.
boolean offer(object) insere o elemento especificado nesta fila de prioridade. Se a fila estiver cheia, o método retorna false.
boolean remove(object) remove uma única instância do elemento especificado desta fila, se estiver presente.
Object poll() recupera e remove o início desta fila. Retorna nulo se a fila estiver vazia.
void clear() remove todos os elementos da fila de prioridade.
Object element() recupera o início desta fila sem removê-lo. Lança NoSuchElementException se a fila estiver vazia.
Object peek() recupera o início da fila sem removê-lo. Retorna nulo se a fila estiver vazia.
boolean contains(Object o) retorna true se a fila contiver o elemento o.
int size() retorna o número de elementos nesta fila.
Exemplo de PriorityQueue
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
System.out.println("Print PriorityQueue using poll() (by retrieval): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our PriorityQueue using poll() (by retrieval):
1
2
3
4
5
É importante entender que as filas de prioridade são baseadas em heaps binários, portanto, não mantêm os elementos em ordem de classificação linear. Todos os caminhos da raiz até a folha são ordenados, mas os caminhos diferentes da raiz não. Isso significa que você pode obter o elemento mínimo da fila muito rapidamente. Se você excluir a cabeça todas as vezes, imprimirá uma estrutura classificada.
ArrayBlockingQueue
Estrutura de dados interna de ArrayBlockingQueueé baseado em uma matriz circular para armazenar elementos. É uma fila típica (FIFO) caso novos elementos sejam inseridos no final da fila e as operações de extração retornem um elemento do início da fila. Uma vez criada, a capacidade da fila não pode ser alterada. Tentativas de inserir (colocar) um elemento em uma fila cheia levam ao bloqueio do fluxo; tentar pegar um elemento de uma fila vazia também bloqueia o thread. Como dissemos antes, esta matriz é circular. Isso significa que o primeiro e o último elemento da matriz são tratados logicamente adjacentes. A fila avança os índices dos elementos iniciais e finais toda vez que você coloca o elemento na fila ou o remove da fila. Se algum índice avança o último elemento da matriz, ele reinicia de 0. Portanto, a fila não precisa deslocar todos os elementos no caso da remoção da cabeça (como na matriz usual). No entanto, no caso de remover um elemento do meio (usando Iterator.remove), os elementos são deslocados. ArrayBlockingQueue suporta uma política de imparcialidade adicional com parâmetro justo no construtor para ordenar o trabalho dos fluxos de espera de produtores (inserindo elementos) e consumidores (extraindo elementos). Por padrão, o pedido não é garantido. No entanto, se a fila for criada com "fair == true", a implementação da classe ArrayBlockingQueue fornece acesso ao thread na ordem FIFO. A equidade normalmente reduz a largura de banda, mas também reduz a volatilidade e evita a falta de recursos.
ArrayBlockingQueue Class construtores
ArrayBlockingQueue (capacidade int) cria uma fila de capacidade fixa e com uma política de acesso padrão.
ArrayBlockingQueue (capacidade int, valor booleano) cria uma fila com uma capacidade fixa e uma política de acesso especificada.
ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) cria uma fila com uma capacidade fixa especificada pela política de acesso e inclui elementos na fila.
Aqui temos o exemplo BlockingQueueExample. Criamos uma fila do ArrayBlockingQueue com capacidade de um elemento e um sinalizador justo. Dois threads são iniciados. A primeira delas, thread do produtor, enfileira as mensagens do array de mensagens usando o método put. A segunda thread, Consumer, lê os elementos da fila usando o método take e os exibe no console. A ordem dos elementos é a natural da fila.
import java.util.concurrent.*;
public class ArrayBlockingQueueExample {
private BlockingQueue<Integer> blockingQueue;
private final Integer[] myArray = {1,2,3,4,5};
public ArrayBlockingQueueExample ()
{ blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
(new Thread(new Producer())).start();
(new Thread(new Consumer())).start();
}
class Producer implements Runnable
{
public void run() {
try {
int counter = 0;
for (int i=0; i < myArray.length; i++) {
blockingQueue.put(myArray[i]);
if (counter++ < 2)
Thread.sleep(3000);
} blockingQueue.put(-1);
}
catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
class Consumer implements Runnable
{
public void run() {
try {
Integer message = 0;
while (!((message = blockingQueue.take()).equals(-1)))
System.out.println(message);
} catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
public static void main(String[] args) {
new ArrayBlockingQueueExample();
}
}
A saída é a fila em ordem natural; os dois primeiros elementos aparecem com um atraso. Para reforçar o que você aprendeu, sugerimos que você assista a uma vídeo aula do nosso Curso de Java
Conclusões
A Fila é utilizada para inserir elementos no final da fila e retirar do início da fila. Segue o conceito FIFO.
O Java Queue faz parte do Collection Framework e implementa a interface Collection. Portanto, ele suporta todos os métodos da interface Collection, como inserção, exclusão e assim por diante.
As implementações de Queue usadas com mais frequência são LinkedList, ArrayBlockingQueue e PriorityQueue.
Os elementos da fila de prioridade são ordenados de acordo com sua ordem natural, ou por um Comparator fornecido no momento da construção da fila, dependendo de qual construtor é usado.
Se qualquer operação nula for executada em BlockingQueues, NullPointerException será lançada.
Portanto, ao trabalhar com uma fila, novos elementos são adicionados ao final e, se você deseja obter um elemento, ele será retirado do início. Este é o princípio principal do trabalho de estrutura de dados de fila clássica.
Você pode dizer que LinkedList não é muito eficaz em termos de uso de memória. Isso é verdade, mas essa estrutura de dados pode ser útil no caso da execução de operações de inserção e exclusão. No entanto, isso acontece apenas se você usar iteradores para eles (neste caso, ocorre em tempo constante). As operações de acesso por índice são realizadas buscando do início ao fim (o que for mais próximo) até o elemento desejado. No entanto, não se esqueça dos custos adicionais para armazenar referências entre elementos. Portanto, LinkedList é a implementação de fila mais popular em Java. É uma implementação de List e Deque também e nos permite criar uma fila bidirecional que consiste em quaisquer objetos, incluindo null. LinkedList é uma coleção de elementos.
GO TO FULL VERSION