Il Corso Typescript Completo è online!

Deque in Java

Edoardo Midali
Edoardo Midali

Deque (Double Ended Queue) rappresenta una delle strutture dati più versatili di Java, permettendo inserimenti e rimozioni efficienti da entrambe le estremità. Questa flessibilità la rende ideale per implementare sia stack (LIFO) che queue (FIFO) con una singola struttura dati, oltre a supportare pattern più complessi come sliding window e undo/redo operations.

Concetti Fondamentali

Deque estende l’interfaccia Queue aggiungendo metodi per operare sulla “tail” (coda) della struttura dati. Mentre Queue permette inserimenti solo in coda e rimozioni solo dalla testa, Deque offre operazioni simmetriche su entrambe le estremità.

Operazioni Simmetriche

Come Queue, Deque fornisce due varianti per ogni operazione: metodi che lanciano eccezioni e metodi che restituiscono valori speciali.

Operazioni sulla Testa (Head):

  • addFirst() / offerFirst() - inserimento
  • removeFirst() / pollFirst() - rimozione
  • getFirst() / peekFirst() - ispezione

Operazioni sulla Coda (Tail):

  • addLast() / offerLast() - inserimento
  • removeLast() / pollLast() - rimozione
  • getLast() / peekLast() - ispezione
Deque<String> deque = new ArrayDeque<>();

// Inserimenti da entrambe le estremità
deque.addFirst("primo");
deque.addLast("ultimo");

// Risultato: [primo, ultimo]

// Accesso simmetrico
String head = deque.peekFirst(); // "primo"
String tail = deque.peekLast();  // "ultimo"

// Rimozioni da entrambe le estremità
String fromHead = deque.pollFirst(); // "primo"
String fromTail = deque.pollLast();  // "ultimo"

Versatilità come Stack e Queue

Deque può fungere sia da Stack che da Queue, offrendo un’API unificata per entrambi i pattern:

Come Stack (LIFO):

  • push() equivale a addFirst()
  • pop() equivale a removeFirst()
  • peek() equivale a peekFirst()

Come Queue (FIFO):

  • offer() equivale a addLast()
  • poll() equivale a removeFirst()
  • peek() equivale a peekFirst()

Implementazioni Principali

ArrayDeque - L’Implementazione Preferita

ArrayDeque è l’implementazione più efficiente di Deque, basata su un array circolare ridimensionabile. È la scelta raccomandata per la maggior parte dei casi d’uso grazie alle sue eccellenti performance e efficienza di memoria.

Vantaggi di ArrayDeque:

  • Performance O(1) amortizzate per tutte le operazioni alle estremità
  • Minore overhead di memoria rispetto a LinkedList
  • Cache-friendly grazie alla memoria contigua
  • Nessuna limitazione di capacità oltre la memoria disponibile
  • Non permette elementi null (caratteristica di sicurezza)

Caratteristiche tecniche:

  • Utilizza un array circolare interno che si ridimensiona dinamicamente
  • Capacità iniziale default di 16 elementi
  • Raddoppia la capacità quando necessario
  • Non è thread-safe
// Inizializzazione con capacità specifica per performance ottimali
Deque<Integer> numbers = new ArrayDeque<>(1000);

// Uso come stack
numbers.push(1);
numbers.push(2);
numbers.push(3);
int top = numbers.pop(); // 3

// Uso come queue
numbers.offer(10);
numbers.offer(20);
int first = numbers.poll(); // 10

LinkedList come Deque

LinkedList implementa Deque oltre a List, offrendo flessibilità ma con performance inferiori rispetto ad ArrayDeque per operazioni alle estremità.

Quando preferire LinkedList:

  • Quando serve anche l’interfaccia List per accesso posizionale
  • Quando gli inserimenti/rimozioni al centro sono frequenti
  • Quando si necessita di iteratori che supportano modifiche strutturali

Limitazioni:

  • Maggiore overhead di memoria per i puntatori
  • Performance inferiori per operazioni alle estremità
  • Cache performance peggiori

ConcurrentLinkedDeque

Per ambienti multi-thread, Java fornisce ConcurrentLinkedDeque, un’implementazione thread-safe basata su algoritmi lock-free.

Caratteristiche:

  • Thread-safe senza uso di lock
  • Performance eccellenti in scenari concurrent
  • Supporta tutte le operazioni Deque
  • Dimensione illimitata
ConcurrentLinkedDeque<Task> concurrentDeque = new ConcurrentLinkedDeque<>();

// Sicuro da usare da thread multipli
concurrentDeque.addFirst(new Task("high-priority"));
concurrentDeque.addLast(new Task("low-priority"));

Pattern di Utilizzo Avanzati

Sliding Window Algorithm

Deque è ideale per implementare sliding window algorithms, dove si mantiene una finestra di elementi di dimensione fissa che scorre attraverso una sequenza di dati.

public class SlidingWindowMax {

    public static List<Integer> findMaxInWindows(int[] array, int windowSize) {
        List<Integer> result = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>(); // Memorizza indici

        for (int i = 0; i < array.length; i++) {
            // Rimuovi elementi fuori dalla finestra
            while (!deque.isEmpty() && deque.peekFirst() < i - windowSize + 1) {
                deque.pollFirst();
            }

            // Rimuovi elementi più piccoli dall'attuale (non saranno mai massimi)
            while (!deque.isEmpty() && array[deque.peekLast()] < array[i]) {
                deque.pollLast();
            }

            deque.addLast(i);

            // Se la finestra è completa, aggiungi il massimo
            if (i >= windowSize - 1) {
                result.add(array[deque.peekFirst()]);
            }
        }

        return result;
    }
}

Undo/Redo System

La natura double-ended di Deque la rende perfetta per implementare sistemi di undo/redo dove le operazioni possono essere annullate e ripristinate.

public class UndoRedoManager<T> {
    private final Deque<Command<T>> undoStack = new ArrayDeque<>();
    private final Deque<Command<T>> redoStack = new ArrayDeque<>();

    public void executeCommand(Command<T> command) {
        command.execute();
        undoStack.addFirst(command);
        redoStack.clear(); // Pulisce la redo stack
    }

    public boolean undo() {
        if (undoStack.isEmpty()) {
            return false;
        }

        Command<T> command = undoStack.removeFirst();
        command.undo();
        redoStack.addFirst(command);
        return true;
    }

    public boolean redo() {
        if (redoStack.isEmpty()) {
            return false;
        }

        Command<T> command = redoStack.removeFirst();
        command.execute();
        undoStack.addFirst(command);
        return true;
    }

    public boolean canUndo() { return !undoStack.isEmpty(); }
    public boolean canRedo() { return !redoStack.isEmpty(); }
}

interface Command<T> {
    void execute();
    void undo();
}

Palindrome Checking

Deque facilita l’implementazione di algoritmi che richiedono confronti simmetrici, come il controllo di palindromi.

public class PalindromeChecker {

    public static boolean isPalindrome(String text) {
        Deque<Character> deque = new ArrayDeque<>();

        // Rimuovi spazi e converti in minuscolo
        String cleaned = text.replaceAll("\\s+", "").toLowerCase();

        // Aggiungi tutti i caratteri
        for (char c : cleaned.toCharArray()) {
            deque.addLast(c);
        }

        // Confronta caratteri dalle estremità
        while (deque.size() > 1) {
            if (!deque.pollFirst().equals(deque.pollLast())) {
                return false;
            }
        }

        return true;
    }
}

Work Stealing Algorithm

Deque è fondamentale nell’implementazione di work stealing algorithms utilizzati in framework come ForkJoinPool.

public class WorkStealingQueue<T> {
    private final Deque<T> localQueue = new ArrayDeque<>();

    // Il thread proprietario aggiunge/rimuove dalla testa (LIFO per locality)
    public void pushLocal(T task) {
        localQueue.addFirst(task);
    }

    public T popLocal() {
        return localQueue.pollFirst();
    }

    // Altri thread "rubano" dalla coda (FIFO per fairness)
    public T steal() {
        return localQueue.pollLast();
    }

    public boolean isEmpty() {
        return localQueue.isEmpty();
    }
}

Performance e Considerazioni di Design

Confronto delle Performance

ArrayDeque vs LinkedList:

  • ArrayDeque: O(1) amortizzato per operazioni alle estremità, migliore cache locality
  • LinkedList: O(1) per operazioni alle estremità, ma overhead di puntatori

Memory Overhead:

  • ArrayDeque: Circa 25% di spazio extra per crescita dell’array
  • LinkedList: 24 byte per nodo (8 byte per elemento + 16 byte per puntatori su JVM 64-bit)

Capacity Planning

Per ArrayDeque, la scelta della capacità iniziale può influenzare significativamente le performance:

// Per workload conosciuti, specifica capacità iniziale
Deque<String> optimizedDeque = new ArrayDeque<>(expectedSize);

// Per workload variabili, usa capacità conservativa
Deque<String> generalDeque = new ArrayDeque<>(); // Default: 16

Thread Safety Considerations

Single-Thread: ArrayDeque è la scelta ottimale per performance pure.

Multi-Thread:

  • ConcurrentLinkedDeque per operazioni lock-free
  • Collections.synchronizedDeque() per wrapping sincrono (meno efficiente)
  • Implementazioni custom con granular locking per casi specifici

Operazioni di Bulk e Iterazione

Iterazione Bidirezionale

Deque supporta iterazione in entrambe le direzioni attraverso iteratori specializzati:

Deque<String> deque = new ArrayDeque<>();
deque.addAll(Arrays.asList("a", "b", "c", "d"));

// Iterazione normale (head -> tail)
Iterator<String> forward = deque.iterator();
while (forward.hasNext()) {
    System.out.println(forward.next());
}

// Iterazione inversa (tail -> head)
Iterator<String> backward = deque.descendingIterator();
while (backward.hasNext()) {
    System.out.println(backward.next());
}

Operazioni di Ricerca

Deque eredita da Collection metodi per ricerca e manipolazione bulk:

Deque<Integer> numbers = new ArrayDeque<>();
numbers.addAll(Arrays.asList(1, 2, 3, 2, 4));

// Ricerca (scansiona dall'head)
boolean contains = numbers.contains(3); // true

// Rimozione di occorrenze specifiche
numbers.removeFirstOccurrence(2); // Rimuove il primo 2
numbers.removeLastOccurrence(2);  // Rimuove l'ultimo 2

// Conversione a array
Integer[] array = numbers.toArray(new Integer[0]);

Best Practices e Linee Guida

Preferisci ArrayDeque: Usa ArrayDeque come implementazione di default per Deque a meno che non servano funzionalità specifiche di altre implementazioni.

Specifica Capacità Iniziale: Per workload con dimensioni prevedibili, specifica la capacità iniziale per evitare ridimensionamenti.

Usa l’API Appropriata: Sfrutta i metodi specifici di Deque (addFirst, pollLast, etc.) invece dei metodi generici di Collection per chiarezza semantica.

Gestisci Null Safety: ArrayDeque non permette elementi null; considera questo nella progettazione delle API.

Considera Thread Safety: Valuta le necessità di concorrenza fin dall’inizio e scegli l’implementazione appropriata.

Documenta l’Uso: Chiarisci se stai usando Deque come Stack, Queue, o per pattern più complessi come sliding window.

Limitazioni e Considerazioni

Null Elements: ArrayDeque non supporta elementi null, che potrebbero essere necessari in alcuni design.

Random Access: Deque non fornisce accesso casuale efficiente; per questo usa List.

Memory Growth: ArrayDeque può consumare più memoria del necessario dopo picchi di utilizzo (non si riduce automaticamente).

Iteration Stability: Modifiche strutturali durante l’iterazione causano ConcurrentModificationException.

Confronto con Altre Strutture Dati

vs Stack: Deque è più versatile e performante della classe Stack legacy.

vs ArrayList: Deque eccelle per operazioni alle estremità, ArrayList per accesso casuale.

vs Queue: Deque offre tutte le funzionalità di Queue plus operazioni sulla tail.

vs PriorityQueue: PriorityQueue per ordinamento automatico, Deque per controllo manuale dell’ordine.

Conclusione

Deque rappresenta una delle strutture dati più versatili ed efficienti di Java, combinando le funzionalità di Stack e Queue in un’interfaccia unificata. ArrayDeque, in particolare, offre performance eccellenti e dovrebbe essere la scelta di default per la maggior parte dei casi d’uso.

La capacità di operare efficientemente su entrambe le estremità rende Deque ideale per algoritmi avanzati come sliding window, work stealing, e pattern undo/redo. La comprensione delle sue caratteristiche e limitazioni è essenziale per sfruttarne appieno il potenziale in applicazioni di produzione.

La scelta tra le diverse implementazioni dipende dai requisiti specifici di thread safety, performance e funzionalità aggiuntive, ma ArrayDeque rimane la raccomandazione generale per scenari single-thread.

PrecedenteQueueSuccessivoIteratori