Qui discuteremo dell'interfaccia Java Queue. Scoprirai cos'è la struttura dei dati della coda , come è rappresentata in Java, quali sono i metodi più importanti per tutte le code. Inoltre, quali implementazioni di Queue sono in linguaggio Java. Successivamente, esaminiamo più da vicino le implementazioni più importanti e le apprendiamo con esempi.
Struttura dei dati della coda
Una coda è una struttura di dati astratta lineare con il particolare ordine di esecuzione delle operazioni: First In First Out (FIFO). Ciò significa che puoi aggiungere un elemento (o accodare, mettere in coda) solo alla fine della struttura e prendere un elemento (eliminare dalla coda o rimuovere dalla coda) solo dal suo inizio. Puoi immaginare la struttura dei dati della coda molto facilmente. Sembra una coda o una fila di clienti nella vita reale. Anche il cliente che è arrivato per primo sarà servito per primo. Se hai quattro persone in fila al McDonalds o altrove, il primo a mettersi in fila sarà il primo ad entrare nel negozio. Se arriva il nuovo cliente, lui/lei sarà il 5° in fila per avere gli hamburger. Quindi, mentre si lavora con una coda, vengono aggiunti nuovi elementi alla fine e, se si desidera ottenere un elemento, verrà preso dall'inizio. Questo è il principio fondamentale del classico lavoro sulla struttura dei dati delle code.
Coda in Java
La coda in Java è un'interfaccia. Secondo la documentazione Oracle, l'interfaccia Queue ha 2 superinterfacce, 4 diverse interfacce che ereditano dalla coda e un elenco di classi estremamente impressionante.
Cosa significa? Prima di tutto, Java Queue fa parte del Collection Framework e implementa l'interfaccia Collection. Quindi supporta tutti i metodi dell'interfaccia Collection come inserimento, cancellazione e così via. Queue implementa l'interfaccia Iterable, che consente a un oggetto di essere il target dell'istruzione "for-each loop".
Metodi di coda Java
La coda dichiara un numero di metodi. Come metodi dell'interfaccia dovrebbero essere rappresentati in tutte le classi che implementano Queue. I metodi di coda più importanti, Java:
Boolean offer() – inserisce un nuovo elemento nella coda se possibile
Boolean add(E e) – inserisce un nuovo elemento nella coda se possibile. Restituisce true in caso di successo e genera un'eccezione IllegalStateException se non c'è spazio.
Object poll() – recupera e rimuove un elemento dalla testa di. Restituisce null se la coda è vuota.
Object remove() – recupera e rimuove un elemento dall'inizio della coda.
Object peek() – recupera, ma non rimuove un elemento dall'inizio della coda. Restituisce null se la coda è vuota.
Object element() – recupera, ma non rimuove un elemento dall'inizio della coda.
Sottointerfacce di Java Queue
L'interfaccia della coda è ereditata da 4 sottointerfacce: BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Puoi dividerli in 3 gruppi: Deque, Code di blocco e Code di trasferimento con BlockingDeque che appartiene ai primi due. Diamo uno sguardo a questi gruppi.
Deques
Deque significa Double - Ended Queue e supporta l'aggiunta o la rimozione dalla coda dei dati come coda (first-in-first-out/FIFO) o dalla testa come un'altra popolare struttura di dati chiamata stack (last-in-first-out / FIFO ) primo uscito/LIFO). Classi che implementano l'interfaccia Deque: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Code di blocco
Una coda di blocco è una coda che blocca un thread in due casi:
thread sta cercando di ottenere elementi da una coda vuota
thread sta tentando di inserire elementi nella coda completa
Quando un thread tenta di ottenere elementi da una coda vuota, attende fino a quando un altro thread inserisce gli elementi nella coda. Allo stesso modo, quando un thread tenta di inserire elementi in una coda piena, attende fino a quando un altro thread estrae gli elementi dalla coda per ottenere spazio libero per gli elementi. Certo, il concetto di "coda piena" implica che la coda abbia una dimensione limitata, che di solito è specificata nel costruttore. Le code di blocco standard includono LinkedBlockingQueue, SynchronousQueue e ArrayBlockingQueue. Implementazione delle classi dell'interfaccia BlockingQueue : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeè una sottointerfaccia per BlockingQueue. BlockingDeque come BlockingQueue è una coda di blocco, ma bidirezionale. Quindi eredita le proprietà dell'interfaccia Deque. È orientato all'esecuzione multi-thread, non consente zero elementi e la capacità potrebbe essere limitata. Le implementazioni dell'interfaccia BlockingDeque bloccano l'operazione di ottenere elementi se la coda è vuota e di aggiungere un elemento alla coda se è piena.
Code di trasferimento
L'interfaccia TransferQueue estende l'interfaccia BlockingQueue. Tuttavia, a differenza dell'implementazione delle code dell'interfaccia BlockingQueue, in cui i thread possono essere bloccati se la coda è vuota (lettura) o se la coda è piena (scrittura), le code dell'interfaccia TransferQueue bloccano il flusso di scrittura finché un altro flusso non recupera l'elemento. Utilizzare un metodo di trasferimento per questo. In altre parole, l'implementazione di BlockingQueue garantisce che l'elemento creato dal Producer debba essere in coda, mentre l'implementazione di TransferQueue garantisce che l'elemento Producer sia "ricevuto" dal Consumer. Esiste solo un'implementazione Java ufficiale dell'interfaccia TransferQueue: LinkedTransferQueue.
Implementazioni della coda Java
Esistono molte classi che implementano l'interfaccia Queue:
AbstractQueue secondo Queue Java 8 docs, questa classe astratta fornisce implementazioni di base di alcune operazioni Queue. Non consente elementi nulli. Esistono altri 3 metodi add, remove ed element basati rispettivamente su Queue classico offer , poll e peek . Tuttavia generano eccezioni invece di indicare il fallimento tramite ritorni falsi o nulli.
ArrayBlockingQueue : una coda di blocco FIFO di dimensioni fisse supportata da un array
LinkedBlockingQueue : una coda di blocco FIFO facoltativamente delimitata supportata da nodi collegati
LinkedList : implementazione di elenchi doppiamente collegati delle interfacce List e Deque. Implementa tutte le operazioni di elenco facoltative e consente tutti gli elementi (incluso null)
LinkedTransferQueue : una TransferQueue illimitata basata su nodi collegati
PriorityBlockingQueue : una coda di priorità di blocco illimitata supportata da un heap
PriorityQueue : una coda di priorità basata sulla struttura dei dati dell'heap
SynchronousQueue : una coda di blocco in cui ogni operazione di inserimento deve attendere un'operazione di rimozione corrispondente da parte di un altro thread e viceversa.
Le implementazioni più popolari sono LinkedList, ArrayBlockingQueue e PriorityQueue. Diamo un'occhiata a loro e facciamo alcuni esempi per una migliore comprensione.
Lista collegata
La classe LinkedList in Java implementa le interfacce List e Deque. Quindi, è una combinazione di List e Deque, una coda bidirezionale, che supporta l'aggiunta e la rimozione di elementi da entrambi i lati. In Java LinkedList è List doppiamente collegato: ogni elemento di List chiama Node e contiene un oggetto e fa riferimento a due oggetti vicini: il precedente e il successivo. Potresti dire che LinkedList non è molto efficace in termini di utilizzo della memoria. È vero, ma questa struttura dati può essere utile in caso di esecuzione delle operazioni di inserimento e cancellazione. Tuttavia accade solo se si utilizzano iteratori per loro (in questo caso si verifica in tempo costante). Le operazioni di accesso per indice vengono eseguite cercando dall'inizio alla fine (qualunque sia più vicino) all'elemento desiderato. Tuttavia, non dimenticare i costi aggiuntivi per l'archiviazione dei riferimenti tra gli elementi. Quindi, LinkedList è l'implementazione della coda più popolare in Java. È anche un'implementazione di List e Deque e ci consente di creare una coda bidirezionale composta da qualsiasi oggetto incluso null. LinkedList è una raccolta di elementi.
LinkedList() senza parametri viene utilizzato per costruire un elenco vuoto. LinkedList(Collection<? extends E> c) serve per creare un elenco contenente gli elementi della raccolta specificata, nell'ordine in cui vengono restituiti dall'iteratore della raccolta.
Principali metodi LinkedList:
add(E elemento) Aggiunge l'elemento specificato alla fine di questo elenco;
add(int index, E element) Inserisce l'elemento nella posizione specificata index;
get(int index) Restituisce l'elemento nella posizione specificata in questo elenco;
remove(int index) Rimuove l'elemento che si trova nella posizione index;
remove(Object o) Rimuove la prima occorrenza dell'elemento ?o da questo elenco, se presente.
remove() Recupera e rimuove il primo elemento dell'elenco.
addFirst(), addLast() aggiungono un elemento all'inizio/fine di una lista
clear() rimuove tutti gli elementi dalla lista
contains(Object o) restituisce true se la lista contiene l'elemento o.
indexOf(Object o) restituisce l'indice della prima occorrenza dell'elemento o, oppure -1 se non è nell'elenco.
set(int index, E element) sostituisce l'elemento nella posizione dell'indice con l'elemento
size() Restituisce la quantità di elementi nell'elenco.
toArray() restituisce un array contenente tutti gli elementi della lista dal primo all'ultimo elemento.
pop() che estrae un elemento dallo stack (rappresentato dalla lista)
push(E e) che inserisce un elemento nello stack (rappresentato da questa lista)
Esempio di coda Java - LinkedList (inserimento e rimozione di elementi in modi diversi)
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);
}
}
Coda prioritaria
PriorityQueue non è esattamente la coda nel significato generale FIFO. Gli elementi della coda prioritaria sono ordinati in base al loro ordinamento naturale o da un Comparatore fornito al momento della costruzione della coda, a seconda del costruttore utilizzato. Tuttavia non è un ordine come potrebbe essere in una struttura lineare come una lista (dal più grande al più piccolo o viceversa). Una coda di priorità basata su un heap minimo di priorità. Heap è una struttura di dati basata su un albero binario. La priorità di ogni genitore è maggiore delle priorità dei suoi figli. Un albero è chiamato binario completo se ogni genitore non ha più di due figli e il riempimento dei livelli va dall'alto verso il basso (dallo stesso livello - da sinistra a destra). L'heap binario si riorganizza ogni volta che viene aggiunto o rimosso un nuovo elemento. In caso di min-heap, l'elemento più piccolo va alla radice indipendentemente dall'ordine del suo inserimento. Coda di priorità basata su questo min-heap, quindi se abbiamo una PriorityQueue di numeri interi, il suo primo elemento sarà il più piccolo di questi numeri. Se elimini la radice, la successiva più piccola diventa una radice.
Principali metodi PriorityQueue:
boolean add(object) inserisce l'elemento specificato nella coda di priorità. Restituisce true in caso di successo. Se la coda è piena, il metodo genera un'eccezione.
boolean offer(object) inserisce l'elemento specificato in questa coda di priorità. Se la coda è piena, il metodo restituisce false.
boolean remove(object) rimuove una singola istanza dell'elemento specificato da questa coda, se presente.
L'oggetto poll() recupera e rimuove l'intestazione di questa coda. Restituisce null se la coda è vuota.
void clear() rimuove tutti gli elementi dalla coda di priorità.
Object element() recupera l'intestazione di questa coda senza rimuoverla. Genera NoSuchElementException se la coda è vuota.
Object peek() recupera l'inizio della coda senza rimuoverlo. Restituisce null se la coda è vuota.
boolean contains(Object o) restituisce true se la coda contiene l'elemento o.
int size() restituisce il numero di elementi in questa coda.
Esempio di 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 comprendere che le code di priorità si basano su heap binari, quindi non mantengono gli elementi in ordine lineare. Ogni via dalla radice alla foglia è ordinata, ma le vie diverse dalla radice non lo sono. Ciò significa che puoi ottenere l'elemento minimo della coda molto rapidamente. Se elimini la testa ogni volta, stamperai una struttura ordinata.
ArrayBlockingQueue
Struttura dati interna di ArrayBlockingQueuesi basa su un array circolare per memorizzare gli elementi. Si tratta di una coda tipica (FIFO) nel caso in cui vengano inseriti nuovi elementi in coda alla coda e le operazioni di estrazione restituiscano un elemento dalla testa della coda. Una volta creata la capacità della coda non può essere modificata. I tentativi di inserire (mettere) un elemento in una coda piena portano al blocco del flusso; provare a prendere un elemento da una coda vuota blocca anche il thread. Come abbiamo detto prima, questo array è circolare. Ciò significa che il primo e l'ultimo elemento dell'array sono considerati logicamente adiacenti. La coda fa avanzare gli indici degli elementi head e tail ogni volta che metti l'elemento in coda o lo rimuovi dalla coda. Se un indice fa avanzare l'ultimo elemento dell'array, ricomincia da 0. Quindi, la coda non deve spostare tutti gli elementi in caso di rimozione della testina (come nel solito array). Tuttavia, in caso di rimozione di un elemento dal centro (utilizzando Iterator.remove), gli elementi vengono spostati. ArrayBlockingQueue supporta una politica di equità aggiuntiva con parametro equo nel costruttore per ordinare il lavoro dei flussi in attesa di produttori (inserimento di elementi) e consumatori (estrazione di elementi). Per impostazione predefinita, l'ordine non è garantito. Tuttavia, se la coda viene creata con "fair == true", l'implementazione della classe ArrayBlockingQueue fornisce l'accesso ai thread in ordine FIFO. L'equità in genere riduce la larghezza di banda, ma riduce anche la volatilità e previene l'esaurimento delle risorse.
Costruttori della classe ArrayBlockingQueue
ArrayBlockingQueue (capacità int) crea una coda di capacità fissa e con un criterio di accesso predefinito.
ArrayBlockingQueue (int capacity, boolean fair) crea una coda con una capacità fissa e una policy di accesso specificata.
ArrayBlockingQueue (int capacity, boolean fair, Collection <? extends E> c) crea una coda con una capacità fissa specificata dalla policy di accesso e include elementi nella coda.
Qui abbiamo l'esempio BlockingQueueExample. Creiamo una coda dell'ArrayBlockingQueue con una capacità di un elemento e un fair flag. Vengono avviati due thread. Il primo di essi, il thread Producer, accoda i messaggi dall'array di messaggi utilizzando il metodo put. Il secondo, Consumer, thread legge gli elementi dalla coda utilizzando il metodo take e li visualizza nella console. L'ordine degli elementi è quello naturale per la coda.
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();
}
}
L'output è la coda in ordine naturale; i primi due elementi compaiono con ritardo. Per rafforzare ciò che hai imparato, ti suggeriamo di guardare una lezione video dal nostro corso Java
Conclusioni
La coda viene utilizzata per inserire elementi alla fine della coda e rimuove dall'inizio della coda. Segue il concetto FIFO.
Java Queue fa parte del Collection Framework e implementa l'interfaccia Collection. Quindi supporta tutti i metodi dell'interfaccia Collection come inserimento, cancellazione e così via.
Le implementazioni più utilizzate di Queue sono LinkedList, ArrayBlockingQueue e PriorityQueue.
Gli elementi della coda prioritaria sono ordinati in base al loro ordinamento naturale o da un Comparatore fornito al momento della costruzione della coda, a seconda del costruttore utilizzato.
Se viene eseguita un'operazione nulla su BlockingQueues, viene generata NullPointerException.
Quindi, mentre si lavora con una coda, vengono aggiunti nuovi elementi alla fine e, se si desidera ottenere un elemento, verrà preso dall'inizio. Questo è il principio fondamentale del classico lavoro sulla struttura dei dati delle code.
Potresti dire che LinkedList non è molto efficace in termini di utilizzo della memoria. È vero, ma questa struttura dati può essere utile in caso di esecuzione delle operazioni di inserimento e cancellazione. Tuttavia accade solo se si utilizzano iteratori per loro (in questo caso si verifica in tempo costante). Le operazioni di accesso per indice vengono eseguite cercando dall'inizio alla fine (qualunque sia più vicino) all'elemento desiderato. Tuttavia, non dimenticare i costi aggiuntivi per l'archiviazione dei riferimenti tra gli elementi. Quindi, LinkedList è l'implementazione della coda più popolare in Java. È anche un'implementazione di List e Deque e ci consente di creare una coda bidirezionale composta da qualsiasi oggetto incluso null. LinkedList è una raccolta di elementi.
GO TO FULL VERSION