Queue, Deque, Stack: lavorare con code e pile

1. Interfaccia Queue: coda classica (FIFO)

Nella programmazione, come nella vita reale, capita che non basti memorizzare un insieme di elementi, ma sia importante gestire l’ordine della loro elaborazione. Immagina la coda al supermercato: chi è più vicino all’inizio viene servito prima. Questo è il principio FIFO — «primo ad entrare — primo ad uscire». Una pila di piatti nell’armadio funziona invece secondo il principio LIFO — «ultimo ad entrare — primo ad uscire». In Java a questi principi corrispondono le collezioni: le code Queue, le code a due estremità Deque e le pile Stack.

Dove si usa:

• Elaborazione dei task in ordine di arrivo (coda dei task, stampa di documenti, gestione degli eventi).
• Implementazione di annulla/ripristina (undo/redo) — pila.
• Parsing di espressioni, attraversamento di alberi e grafi (ricerca in ampiezza/profondità) e molto altro.

Che cos’è una coda?

Una coda (Queue) è una collezione basata sul principio FIFO. Gli elementi si aggiungono in coda e si estraggono dalla testa. Come in un negozio: chi è arrivato prima viene servito per primo.

Metodi principali dell’interfaccia Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Hai notato coppie di metodi con comportamento simile. La differenza è nella «morbidezza»: offer, poll, peek restituiscono un valore speciale in caso di insuccesso (di solito null o false) e non lanciano eccezioni, mentre add, remove, element le lanciano in situazioni limite (coda vuota, talvolta overflow).

Esempio: coda di task

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Lavare i denti");
        tasks.offer("Fare ginnastica");
        tasks.offer("Bere un caffè");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // Prendiamo il task dall'inizio della coda
            System.out.println("Eseguo: " + task);
        }
    }
}

Output:

Eseguo: Lavare i denti
Eseguo: Fare ginnastica
Eseguo: Bere un caffè

Perché si usa spesso LinkedList?

Un’interfaccia è un contratto e può avere più implementazioni. Si usa spesso LinkedList perché aggiunge/rimuove velocemente da entrambe le estremità. Tuttavia un’ottima alternativa è ArrayDeque. Esistono anche varianti specializzate: PriorityQueue (coda con priorità), di cui parleremo più avanti.

2. Interfaccia Deque: coda a doppia estremità

Deque (Double‑Ended Queue, «dek») è una coda in cui si possono aggiungere e rimuovere elementi da entrambe le estremità: dalla testa e dalla coda. Come un autobus con due porte: si può entrare/uscire da qualsiasi lato.

Deque = un tuttofare universale: può funzionare come una coda (FIFO), come una pila (LIFO) e come un ibrido.

Metodi principali dell’interfaccia Deque

addFirst(e)

ochered.addFirst("A")

addLast(e)

ochered.addLast("B")

removeFirst()

ochered.removeFirst()

removeLast()

ochered.removeLast()

peekFirst()

ochered.peekFirst()

peekLast()

ochered.peekLast()

offerFirst(e)

ochered.offerFirst("C")

offerLast(e)

ochered.offerLast("D")

Esempio: Deque come coda e come pila

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Usiamo come coda (FIFO)
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("Coda (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Usiamo come pila (LIFO)
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Pila (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Output:

Coda (FIFO):
A
B
C
Pila (LIFO):
3
2
1

Perché ArrayDeque?

ArrayDeque è un’implementazione Deque veloce e compatta basata su array. Per pila e coda è in genere più veloce e affidabile del vecchio Stack e non ha dimensione fissa (limitata solo dalla memoria).

3. Stack: pila — ultimo ad entrare, primo ad uscire (LIFO)

La pila è una collezione secondo il principio LIFO: si preleva l’elemento superiore, cioè l’ultimo aggiunto. In programmazione la pila è utile per la cronologia delle azioni (undo), l’attraversamento di strutture ricorsive (alberi/grafi), il calcolo di espressioni, ecc.

Classe Stack (e perché non conviene usarla)

In Java esiste la classe Stack, che estende il vecchio Vector. Oggi non è consigliata nei nuovi progetti. È preferibile Deque/ArrayDeque.

Metodi della pila (Deque)

push(e)

pop()

peek()

Attenzione: in Deque queste operazioni corrispondono ai metodi addFirst/removeFirst/peekFirst, ma per compatibilità esistono anche i nomi «da stack» push/pop/peek.

Esempio: pila con ArrayDeque

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Primo");
        stack.push("Secondo");
        stack.push("Terzo");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Output:

Terzo
Secondo
Primo

Perché non Stack?

• Stack è sincronizzato (più lento) ed estende il vecchio Vector.
• ArrayDeque è spesso più veloce e compatto, non blocca i thread.
• Se vedi Stack nel nuovo codice — di solito è un candidato da sostituire con ArrayDeque.

4. Quando usare cosa

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Esempi reali:

• Coda in banca — Queue.
• Cronologia delle azioni in un editor — Stack.
• Coda di autobus, ingresso/uscita da entrambi i lati — Deque.

5. Esempi di codice: implementiamo coda e pila in mini‑applicazioni

Esempio 1: Coda di stampa dei documenti

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("Documento1.pdf");
        printQueue.offer("Documento2.docx");
        printQueue.offer("Documento3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("In stampa: " + doc);
        }
    }
}

Esempio 2: Pila di annullamento azioni (undo)

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Inserimento di testo");
        undoStack.push("Modifica del colore");
        undoStack.push("Eliminazione dell'immagine");

        System.out.println("Ultima azione: " + undoStack.peek()); // Eliminazione dell'immagine

        while (!undoStack.isEmpty()) {
            System.out.println("Annullamento: " + undoStack.pop());
        }
    }
}

Esempio 3: Coda a doppia estremità

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("Estraiamo dall'inizio: " + deque.removeFirst()); // C
        System.out.println("Estraiamo dalla fine: " + deque.removeLast());   // D
        System.out.println("Rimasto: " + deque); // [A, B]
    }
}

6. Particolarità di implementazione e dettagli

• ArrayDeque — l’implementazione di coda/pila più veloce e universale per la maggior parte dei casi.
• LinkedList — implementa anch’esso Deque; può essere utile, ma per code corte di solito è più lento di ArrayDeque.
• PriorityQueue — coda a priorità: l’ordine è determinato dalla priorità (naturale o tramite Comparator); non è una coda FIFO normale.
• Stack — obsoleto, sincronizzato; nei nuovi progetti è preferibile ArrayDeque.
• Deque è comodo perché consente di lavorare sia con l’inizio sia con la fine della struttura, coprendo scenari di code e pile con un’unica astrazione.

7. Errori tipici nell’uso di code e pile

Errore n. 1: usare Stack invece di Deque.
Molti principianti vedono la classe Stack e la scelgono «per il nome». Nei progetti moderni al suo posto si usa ArrayDeque (o LinkedList) con i metodi push/pop.

Errore n. 2: violazione del principio di funzionamento della struttura.
Si tenta di accedere agli elementi della coda/pila per indice, ad esempio queue.get(0) o stack.get(0). Non si deve fare — usa i metodi appropriati per code e pile (peek, poll, pop, ecc.).

Errore n. 3: uso di remove()/element()/add() senza controlli.
I metodi remove, element, add possono lanciare un’eccezione con strutture vuote/sature. È più sicuro usare i metodi «morbidi» offer, poll, peek, che restituiscono valori speciali.

Errore n. 4: uso di ArrayDeque con elementi null.
ArrayDeque non consente null. Un tentativo di aggiungere null porterà a NullPointerException.

Errore n. 5: usare PriorityQueue come una coda normale.
In PriorityQueue l’ordine è determinato dalle priorità (naturali o definite tramite Comparator). Per un FIFO rigoroso usa ArrayDeque o LinkedList.

Errore n. 6: modificare la coda/pila durante l’iterazione con for-each.
Rimuovere elementi dalla collezione durante un for-each può portare a ConcurrentModificationException. Per rimuovere usa un iteratore o i metodi poll/pop in un ciclo, come mostrato negli esempi.