Coda

Per la maggior parte delle persone, la parola "coda" fa venire in mente pochissime associazioni piacevoli. Ma oggi parliamo di code diverse: le code Java. In Java, una coda è tutto ciò che eredita l' interfaccia Queue , che a sua volta estende l'interfaccia Collection . Ciò significa che le code possono essere trattate come raccolte.

Le code in Java supportano due principi operativi: FIFO e LIFO .

Il principio FIFO (First In, First Out) governa una coda regolare: il primo elemento aggiunto alla coda è il primo a lasciarla.

Il principio LIFO (Last In, First Out) descrive il comportamento di uno stack: l'ultimo elemento aggiunto alla coda è il primo a lasciarla. Ad esempio, è così che lavori con un mazzo di carte: togli le carte dalla cima una alla volta finché non raggiungi il fondo del mazzo.

La gerarchia della coda in Java è simile a questa:

Qui puoi vedere che Queue ha 3 classi di implementazione: LinkedList , ArrayDeque e PriorityQueue . LinkedList e ArrayDeque ereditano direttamente non Queue , ma Deque .

Deque è un'interfaccia che è stata aggiunta in Java 6. Include diversi metodi utili per le code e consente a una coda di funzionare come una coda a doppia estremità (o bidirezionale). Ciò significa che può essereFIFOeLIFO.

Uno dei due discendenti dell'interfaccia Deque è ArrayDeque . Supporta una coda a doppia estremità che consente di inserire e rimuovere elementi da entrambe le estremità. È anche un array dinamico che cresce automaticamente di dimensioni.

Esiste anche una classe PriorityQueue , che è una discendente diretta di Queue : si comporta in modo diverso rispetto alle classi che implementano Deque .

PriorityQueue è una coda di priorità che organizza gli elementi in base al loro ordinamento naturale per impostazione predefinita. Qui l'ordinamento utilizza leinterfacce Comparable e Comparator . Il principio è lo stesso di TreeSet o TreeMap , classi che utilizzano l' interfaccia Comparable e hanno il proprio ordinamento.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Se esegui questo esempio, ecco cosa vedrai nella console:

Poiché stiamo lavorando con code e non con raccolte regolari, dobbiamo rimuovere gli elementi dall'elenco. Per farlo usiamo questo costrutto:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

L' interfaccia Deque eredita i metodi Queue e aggiunge molti dei suoi metodi interessanti:

Diamo ora un'occhiata ad alcuni di questi metodi in pratica.

Innanzitutto, aggiungiamo un elemento a una coda:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue

        System.out.println(deque);

Ora prendiamo i valori da una coda:

Deque<String> deque = new ArrayDeque<>();

deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");


        System.out.println("The first element is: "+ deque.getFirst());

        System.out.println("The last element is: " + deque.getLast());

    }

Questo codice visualizza il primo e l'ultimo elemento della coda.

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);

Eseguendo questo codice, otteniamo:

La differenza tra pop() e poll() è che pop() genererà una NoSuchElementException se l'elenco è un elenco vuoto, ma poll() restituirà null .

Consideriamo ora i metodi pollFirst() e pollLast() .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple");
        deque.addFirst("Orange");
        deque.addLast("Pineapple");
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);

Entrambi i metodi restituiscono e rimuovono un valore dalla coda.

Ecco un esempio di utilizzo dei metodi peekFirst() e peekLast() :

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);

Entrambi i metodi restituiscono il primo/ultimo elemento dalla coda e non li rimuovono. Se la coda è vuota, verrà restituito null .

Ben fatto! Oggi abbiamo imparato a lavorare con le code in Java. Ora sai come usarli nella pratica.