Interfaccia Queue in Java

Queue<E> è Collection<E> con in più il concetto di testa. La testa è il prossimo elemento da rimuovere; tutti gli altri aspettano il loro turno dietro di essa. La semantica predefinita — e quella usata da quasi ogni implementazione nel JDK — è FIFO: primo entrato, primo uscito. I produttori usano offer per aggiungere elementi in coda; i consumatori usano poll per prelevarli dalla testa. Questo capitolo riguarda il contratto: i sei metodi, i due stili di gestione degli errori, la regola sul null e quale implementazione scegliere in quale situazione.

Due modi per fare ogni cosa — per design

Ogni operazione sulla coda è disponibile in due varianti: una che lancia un'eccezione in caso di fallimento e una che restituisce un valore speciale. Il Javadoc lo presenta come una griglia 3×2:

La colonna "lancia" è quella ereditata da Collection e List — è familiare ma scomoda quando il caso vuota/piena è normale (un consumatore che aspetta il prossimo lavoro, una coda limitata che rifiuta un produttore in eccesso). La colonna "restituisce un valore speciale" è stata aggiunta per le code in modo da poter scrivere cicli che non si affidano alle eccezioni per il flusso di controllo:

String item;
while ((item = queue.poll()) != null) {
  process(item);
}

Usa la forma con restituzione di valore come impostazione predefinita. Ricorri a remove/element solo quando una coda vuota in quel punto sarebbe un vero bug che vorresti segnalato come eccezione.

Null e Queue non vanno d'accordo

Poiché poll() e peek() restituiscono null per indicare "vuoto", consentire null come elemento reale è una ricetta per l'ambiguità. Ogni Queue di uso generale nel JDK, tranne LinkedList, rifiuta null — ArrayDeque, PriorityQueue, ArrayBlockingQueue, tutte le code concorrenti. LinkedList ti permette di aggiungere un null, ma se lo fai hai violato il contratto: non c'è più modo di distinguere "la testa è null" da "la coda è vuota."

La regola: non memorizzare null in una coda. Scegli ArrayDeque invece di LinkedList e il linguaggio lo impone per te.

FIFO è il comportamento predefinito — ma non universale

Queue non richiede il FIFO. L'interfaccia definisce una testa e operazioni che prelevano da essa; come viene decisa la testa dipende dall'implementazione. Le due implementazioni in java.util che non sono FIFO sono:

• PriorityQueue — la testa è sempre l'elemento più piccolo (per ordine naturale o tramite un Comparator). Gli inserimenti vanno dove l'heap lo stabilisce, non in coda.
• Le varianti bloccanti in java.util.concurrent — PriorityBlockingQueue, DelayQueue, ecc. — riordinano per priorità, scadenza, ecc.

Tutto il resto (ArrayDeque, LinkedList, ArrayBlockingQueue, LinkedBlockingQueue, ConcurrentLinkedQueue) è FIFO.

Scegliere un'implementazione

Per il caso single-threaded:

• ArrayDeque — la scelta predefinita. Array circolare, nessuna allocazione per elemento, veloce. Usala come Queue<E> o come Deque<E> a seconda che tu abbia bisogno di accesso a entrambe le estremità.
• LinkedList — funziona, implementa anche List. Sceglila solo se hai davvero bisogno di entrambe le interfacce sullo stesso oggetto. Il capitolo su LinkedList copre i compromessi.
• PriorityQueue — quando vuoi "il prossimo elemento in attesa più piccolo" invece del FIFO.

Per il caso multi-threaded (trattato in dettaglio nella parte sulla concorrenza in seguito — solo indicazioni qui):

• ConcurrentLinkedQueue — FIFO lock-free. Non limitata.
• ArrayBlockingQueue — limitata, basata su array, blocca put quando piena e take quando vuota. La classica coda produttore/consumatore.
• LinkedBlockingQueue — opzionalmente limitata, forma a nodi collegati della stessa.
• PriorityBlockingQueue — PriorityQueue concorrente. Non limitata.

La maggior parte del codice applicativo usa una delle prime quattro. Le code bloccanti sono il modo in cui si costruiscono pool di worker e back-pressure.

Cosa puoi chiamare su qualsiasi Queue

Oltre ai sei metodi specifici per la testa, una Queue è anche una Collection — quindi size, isEmpty, contains, iterator, forEach, stream, clear, toArray funzionano tutti. L'ordine di iterazione è l'ordine in cui gli elementi verrebbero prelevati con poll per le implementazioni FIFO (ArrayDeque, LinkedList), ma per PriorityQueue l'ordine dell'iteratore non è l'ordine di priorità — visita l'array heap sottostante così com'è. Se vuoi gli elementi in ordine di priorità, devi svuotare la coda con poll finché non è vuota.

Un esempio pratico: produttore/consumatore in un thread

Il programma seguente usa un ArrayDeque come coda FIFO per modellare un piccolo sistema di stampa: i lavori arrivano nel tempo (lo rappresentiamo offrendo in batch), e il worker svuota ogni batch con poll. La coppia con stile di errore è mostrata all'inizio in modo da poter vedere esattamente quando si attiva ciascuna forma.

Alcune considerazioni sull'output dell'esecuzione:

• poll e peek hanno restituito silenziosamente null quando la coda era vuota; remove e element hanno sollevato eccezioni. Entrambi i comportamenti fanno parte del contratto — scegli quello che corrisponde a se "vuoto" è un errore o solo uno stato.
• offer(null) ha lanciato su ArrayDeque. L'implementazione impone la regola da cui dipende l'interfaccia.
• La PriorityQueue ha restituito 10, 20, 30, 40 — ordine ordinato, non ordine di inserimento. Stessa interfaccia Queue, regola di selezione della testa completamente diversa.

Cosa c'è dopo

La prima implementazione non-FIFO merita un capitolo a parte — PriorityQueue è una coda basata su heap dove la testa è sempre l'elemento più piccolo. Questo è l'ingrediente di base di praticamente ogni scheduler "elabora prima il compito più urgente" nel JDK.

Pratica