Il Corso Typescript Completo è online!

Queue in Java

Edoardo Midali
Edoardo Midali

L’interfaccia Queue rappresenta una delle strutture dati più fondamentali in informatica, implementando il principio FIFO (First In, First Out) dove gli elementi vengono inseriti in coda e rimossi dalla testa. Java fornisce diverse implementazioni di Queue, ognuna ottimizzata per scenari specifici, dalla semplice LinkedList alla sofisticata PriorityQueue.

Concetti Fondamentali

Queue estende l’interfaccia Collection e definisce operazioni specifiche per la gestione di code. La caratteristica distintiva è la presenza di due set di metodi per ogni operazione: versioni che lanciano eccezioni in caso di fallimento e versioni che restituiscono valori speciali.

Operazioni Base e Dualità dei Metodi

Inserimento: add(element) lancia eccezione se fallisce, offer(element) restituisce false se non può inserire l’elemento.

Rimozione: remove() lancia eccezione se la coda è vuota, poll() restituisce null se la coda è vuota.

Ispezione: element() lancia eccezione se la coda è vuota, peek() restituisce null se la coda è vuota.

Questa dualità è particolarmente importante in contesti dove le operazioni potrebbero fallire (come code con capacità limitata) e dove si preferisce gestire errori attraverso valori di ritorno piuttosto che eccezioni.

Queue<String> coda = new LinkedList<>();

// Metodi che lanciano eccezioni
coda.add("elemento1");
String primo = coda.element(); // NoSuchElementException se vuota
String rimosso = coda.remove(); // NoSuchElementException se vuota

// Metodi che restituiscono valori speciali
coda.offer("elemento2"); // Restituisce true/false
String testa = coda.peek(); // null se vuota
String estratto = coda.poll(); // null se vuota

Semantica FIFO

Il principio FIFO garantisce che gli elementi vengano processati nell’ordine di arrivo. Questo è fondamentale per scenari come task scheduling, buffer di messaggi e algoritmi di attraversamento grafi. La prevedibilità dell’ordinamento rende Queue ideale per implementare fairness in sistemi concorrenti.

Implementazioni Principali

LinkedList come Queue

LinkedList implementa sia List che Queue, rendendola una scelta versatile per code di dimensione variabile. Offre performance O(1) per inserimenti e rimozioni alle estremità, rendendola ideale per code semplici senza limitazioni di capacità.

Vantaggi:

  • Dimensione dinamica illimitata
  • Performance O(1) per operazioni di coda
  • Implementa anche List per funzionalità aggiuntive

Svantaggi:

  • Overhead di memoria per i puntatori
  • Non thread-safe
  • Cache performance inferiore rispetto ad array

ArrayDeque come Queue

ArrayDeque (Array Double Ended Queue) è spesso la scelta migliore per implementare Queue quando non si necessita di thread safety. Basata su array ridimensionabili, offre performance migliori di LinkedList nella maggior parte dei casi.

Vantaggi:

  • Performance superiori a LinkedList
  • Minore overhead di memoria
  • Supporta operazioni da entrambe le estremità (deque)
  • Implementazione cache-friendly

Considerazioni:

  • Ridimensionamento dell’array può causare picchi temporanei di allocazione
  • Non thread-safe
  • Dimensione iniziale dovrebbe essere considerata per performance ottimali

PriorityQueue - Code con Priorità

PriorityQueue implementa una coda dove gli elementi vengono estratti in base alla loro priorità piuttosto che in ordine FIFO. Internamente utilizza un heap binario per mantenere l’ordinamento, garantendo che l’elemento con priorità più alta sia sempre in testa.

// PriorityQueue con ordinamento naturale (minimo prima)
PriorityQueue<Integer> codaPriorita = new PriorityQueue<>();
codaPriorita.offer(5);
codaPriorita.offer(1);
codaPriorita.offer(3);

System.out.println(codaPriorita.poll()); // 1 (minimo)

// PriorityQueue con Comparator personalizzato per priorità alta
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    (t1, t2) -> Integer.compare(t2.getPriorita(), t1.getPriorita())
);

Caratteristiche:

  • Ordinamento automatico basato su priorità
  • Performance O(log n) per inserimento e rimozione
  • Non garantisce ordinamento completo durante iterazione
  • Non permette elementi null
  • Richiede elementi Comparable o Comparator

Thread Safety e Code Concurrent

Le implementazioni base di Queue non sono thread-safe. Per ambienti multi-thread, Java fornisce implementazioni specializzate nel package java.util.concurrent.

Blocking Queues

Le Blocking Queues forniscono operazioni che bloccano il thread quando la coda è piena (per inserimenti) o vuota (per estrazioni). Questo è fondamentale per implementare pattern producer-consumer sicuri.

LinkedBlockingQueue: Basata su linked nodes con capacità opzionalmente limitata. Ottima per scenari producer-consumer con throughput variabile.

ArrayBlockingQueue: Capacità fissa basata su array. Supporta fairness opzionale per garantire ordine FIFO anche per thread in attesa.

PriorityBlockingQueue: Versione thread-safe di PriorityQueue con capacità illimitata.

BlockingQueue<String> blockingQueue = new LinkedBlockingQueue<>(10);

// Producer
blockingQueue.put("elemento"); // Blocca se coda piena

// Consumer
String elemento = blockingQueue.take(); // Blocca se coda vuota

Non-Blocking Queues

ConcurrentLinkedQueue: Implementazione lock-free basata su algoritmi compare-and-swap. Offre alta performance in scenari multi-thread senza blocking, ideale quando si vuole evitare contention tra thread.

Queue<String> concurrentQueue = new ConcurrentLinkedQueue<>();
// Sicuro da usare da thread multipli senza sincronizzazione
concurrentQueue.offer("elemento");
String elemento = concurrentQueue.poll();

Pattern di Utilizzo Comuni

Producer-Consumer Pattern

Queue è fondamentale per disaccoppiare producer e consumer, permettendo elaborazione asincrona e gestione di carichi di lavoro variabili.

public class TaskProcessor {
    private final BlockingQueue<Task> taskQueue = new LinkedBlockingQueue<>();
    private volatile boolean running = true;

    public void submitTask(Task task) {
        try {
            taskQueue.put(task);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    public void startWorker() {
        new Thread(() -> {
            while (running) {
                try {
                    Task task = taskQueue.take();
                    processTask(task);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        }).start();
    }

    private void processTask(Task task) {
        // Elaborazione del task
    }
}

Queue è essenziale per implementare algoritmi di attraversamento in ampiezza su grafi e alberi, garantendo che tutti i nodi a una certa distanza vengano visitati prima di passare al livello successivo.

public void bfsTraversal(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        visit(current);

        if (current.getLeft() != null) queue.offer(current.getLeft());
        if (current.getRight() != null) queue.offer(current.getRight());
    }
}

Task Scheduling

PriorityQueue è ideale per implementare scheduler dove task devono essere eseguiti in ordine di priorità o tempo di scadenza.

public class TaskScheduler {
    private final PriorityQueue<ScheduledTask> taskQueue = new PriorityQueue<>(
        Comparator.comparing(ScheduledTask::getScheduledTime)
    );

    public void scheduleTask(ScheduledTask task) {
        taskQueue.offer(task);
    }

    public void processReadyTasks() {
        LocalDateTime now = LocalDateTime.now();

        while (!taskQueue.isEmpty() &&
               !taskQueue.peek().getScheduledTime().isAfter(now)) {
            ScheduledTask task = taskQueue.poll();
            executeTask(task);
        }
    }
}

Performance e Considerazioni di Design

Scelta dell’Implementazione

Per code semplici FIFO: ArrayDeque è generalmente la scelta migliore per single-thread, offrendo il miglior bilanciamento tra performance e efficienza di memoria.

Per code con priorità: PriorityQueue quando l’ordinamento per priorità è necessario, con attenzione al costo O(log n) delle operazioni.

Per ambienti multi-thread: ConcurrentLinkedQueue per operazioni non-bloccanti ad alta performance, BlockingQueue varianti per sincronizzazione producer-consumer.

Per capacità limitata: ArrayBlockingQueue quando si vuole limitare l’uso di memoria e implementare backpressure naturale.

Gestione della Memoria e Backpressure

Queue può causare memory leak se elementi si accumulano più velocemente di quanto vengono processati. È importante implementare strategie di monitoraggio e backpressure.

public class SafeQueue<T> {
    private final Queue<T> queue = new ArrayDeque<>();
    private final int maxSize;

    public SafeQueue(int maxSize) {
        this.maxSize = maxSize;
    }

    public boolean offer(T element) {
        if (queue.size() >= maxSize) {
            return false; // Rifiuta se troppo piena
        }
        return queue.offer(element);
    }

    public void monitorSize() {
        int currentSize = queue.size();
        if (currentSize > maxSize * 0.8) {
            System.out.println("Warning: Queue è all'80% della capacità");
        }
    }
}

Considerazioni su Cache Performance

ArrayDeque e ArrayList-based queues tendono ad avere migliori cache performance rispetto a LinkedList grazie alla locality of reference. Per workload con accesso frequente, questo può fare una differenza significativa nelle performance.

Operazioni Avanzate

Batch Processing

Per migliorare throughput, spesso è utile processare elementi in batch piuttosto che uno alla volta.

public class BatchProcessor<T> {
    private final Queue<T> queue = new ArrayDeque<>();
    private final int batchSize;

    public BatchProcessor(int batchSize) {
        this.batchSize = batchSize;
    }

    public List<T> pollBatch() {
        List<T> batch = new ArrayList<>(batchSize);

        for (int i = 0; i < batchSize && !queue.isEmpty(); i++) {
            T element = queue.poll();
            if (element != null) {
                batch.add(element);
            }
        }

        return batch;
    }
}

Timeout Operations

Per evitare attese indefinite, molte implementazioni supportano operazioni con timeout.

// Con BlockingQueue
try {
    String element = blockingQueue.poll(5, TimeUnit.SECONDS);
    if (element == null) {
        System.out.println("Timeout: nessun elemento disponibile");
    }
} catch (InterruptedException e) {
    Thread.currentThread().interrupt();
}

Best Practices

Scegli l’Implementazione Appropriata: Considera i requisiti di thread safety, capacità limitata, ordinamento e performance per selezionare l’implementazione corretta.

Gestisci Interruzioni: Nei metodi che possono essere interrotti, gestisci sempre InterruptedException appropriatamente ripristinando l’interrupt flag.

Implementa Backpressure: Per code di produzione, implementa meccanismi per gestire situazioni dove i producer sono più veloci dei consumer.

Monitora Performance: Tieni traccia della dimensione della coda e dei tempi di processamento per identificare bottleneck.

Considera Batching: Per migliorare throughput, considera il processamento in batch quando appropriato.

Documenta la Semantica: Chiarisci se la tua Queue implementation è FIFO, priority-based, o ha altra semantica di ordinamento.

Limitazioni e Considerazioni

Capacity Bounds: Alcune implementazioni hanno limitazioni di capacità che possono causare blocking o rifiuto di elementi.

Thread Safety: La maggior parte delle implementazioni base non sono thread-safe, richiedendo sincronizzazione esterna o l’uso di implementazioni concurrent.

Memory Overhead: LinkedList-based queues hanno overhead significativo per i puntatori; ArrayDeque è più efficiente per memoria.

Null Elements: La maggior parte delle implementazioni non supporta elementi null, con alcune eccezioni come LinkedList.

Conclusione

Queue è una struttura dati fondamentale che fornisce la base per molti pattern di programmazione, dal semplice buffering all’implementazione di algoritmi complessi. La scelta dell’implementazione corretta dipende dai requisiti specifici di performance, thread safety, capacità e semantica di ordinamento.

ArrayDeque è spesso la scelta migliore per scenari single-thread, mentre le varianti Concurrent offrono opzioni robuste per ambienti multi-thread. PriorityQueue risolve scenari dove l’ordinamento per priorità è cruciale, e le BlockingQueue forniscono sincronizzazione built-in per pattern producer-consumer.

La comprensione delle caratteristiche e limitazioni di ogni implementazione è essenziale per utilizzare Queue efficacemente in applicazioni di produzione.

PrecedenteTreeSetSuccessivoDeque