Le classi Queue: PriorityQueue e ArrayDeque in Java

La Classe PriorityQueue

PriorityQueue estende AbstractQueue e implementa l'interfaccia Queue.

Crea una coda che è prioritizzata basata sul comparatore della coda. PriorityQueue è una classe generica che ha questa dichiarazione:

class PriorityQueue<E>

Qui, E specifica il tipo di oggetti memorizzati nella coda. Le PriorityQueue sono dinamiche, crescendo come necessario.

PriorityQueue definisce i sette costruttori mostrati qui:

PriorityQueue()
PriorityQueue(int capacita)
PriorityQueue(Comparator<? super E> comp) 
PriorityQueue(int capacita, Comparator<? super E> comp)
PriorityQueue(Collection<? extends E> c)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)

1. Il primo costruttore costruisce una coda vuota. La sua capacità iniziale è 11.
2. Il secondo costruttore costruisce una coda che ha la capacità iniziale specificata.
3. Il terzo costruttore specifica un comparatore, e il quarto costruisce una coda con la capacità specificata e il comparatore.
4. Gli ultimi tre costruttori creano code che sono inizializzate con gli elementi della collezione passata in c. In tutti i casi, la capacità cresce automaticamente mentre gli elementi vengono aggiunti.

Se nessun comparatore è specificato quando una PriorityQueue è costruita, allora il comparatore predefinito per il tipo di dati memorizzati nella coda è utilizzato. Il comparatore predefinito ordinerà la coda in ordine ascendente. Così, la testa della coda sarà il valore più piccolo. Tuttavia, fornendo un comparatore personalizzato, si può specificare uno schema di ordinamento diverso. Per esempio, quando si memorizzano elementi che includono un timestamp, si potrebbe prioritizzare la coda in modo tale che gli elementi più vecchi siano primi nella coda.

Si può ottenere un riferimento al comparatore utilizzato da una PriorityQueue chiamando il suo metodo comparator(), mostrato qui:

Comparator<? super E> comparator()

Restituisce il comparatore. Se l'ordinamento naturale è utilizzato per la coda invocante, null è restituito.

Una parola di cautela: Sebbene tu possa iterare attraverso una PriorityQueue utilizzando un iteratore, l'ordine di quella iterazione è indefinito. Per utilizzare correttamente una PriorityQueue, devi chiamare metodi come offer() e poll(), che sono definiti dall'interfaccia Queue.

Vediamo un esempio di utilizzo di una PriorityQueue. In questo esempio, creeremo una PriorityQueue di interi e la utilizzeremo per memorizzare i numeri in ordine crescente:

import java.util.PriorityQueue;

public class EsempioPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> coda = new PriorityQueue<>();

        // Aggiungi elementi alla coda
        coda.offer(5);
        coda.offer(1);
        coda.offer(3);

        // Rimuovi e stampa gli elementi in ordine
        while (!coda.isEmpty()) {
            System.out.println(coda.poll());
        }
    }
}

In questo esempio, abbiamo creato una PriorityQueue di interi e abbiamo aggiunto tre numeri. Quando rimuoviamo gli elementi dalla coda utilizzando il metodo poll(), gli elementi vengono restituiti in ordine crescente, poiché la coda è ordinata in base al loro valore naturale.

L'output dell'esempio sarà:

1
3
5

La Classe ArrayDeque

La classe ArrayDeque estende AbstractCollection e implementa l'interfaccia Deque. Non aggiunge metodi propri.

ArrayDeque crea un array dinamico e non ha restrizioni di capacità. L'interfaccia Deque supporta implementazioni che limitano la capacità, ma non richiede tali restrizioni. ArrayDeque è una classe generica che ha questa dichiarazione:

class ArrayDeque<E>

Qui, E specifica il tipo di oggetti memorizzati nella collezione.

ArrayDeque definisce i seguenti costruttori:

ArrayDeque()
ArrayDeque(int dimensione)
ArrayDeque(Collection<? extends E> c)

Il primo costruttore costruisce un deque vuoto. La sua capacità iniziale è 16. Il secondo costruttore costruisce un deque che ha la capacità iniziale specificata. Il terzo costruttore crea un deque che è inizializzato con gli elementi della collezione passata in c. In tutti i casi, la capacità cresce secondo necessità per gestire gli elementi aggiunti al deque.

Il seguente programma dimostra l'uso di un ArrayDeque utilizzandolo per creare uno stack:

// Dimostrazione ArrayDeque.
import java.util.*;

class DemoArrayDeque {

    public static void main(String[] args) {
        // Crea un array deque.
        ArrayDeque<String> adq = new ArrayDeque<String>();

        // Usa un ArrayDeque come uno stack.
        adq.push("A");
        adq.push("B");
        adq.push("D");
        adq.push("E");
        adq.push("F");

        System.out.print("Estrazione dallo stack: ");
        while (adq.peek() != null)
            System.out.print(adq.pop() + " ");
        System.out.println();
    }

}

L'output è mostrato qui:

Estrazione dallo stack: F E D B A