Java ArrayDeque

ArrayDeque<E> è un array circolare che cresce su richiesta. Implementa sia Queue<E> che Deque<E>, quindi può svolgere il ruolo di coda FIFO, stack LIFO o coda a doppia estremità senza modifiche al codice. Il Javadoc di Stack raccomanda Deque al posto della classe legacy; il Javadoc di Deque aggiunge la raccomandazione pratica che ArrayDeque dovrebbe essere la tua implementazione predefinita. È quasi sempre più veloce di LinkedList, occupa meno memoria ed è la scelta preferita dalla libreria standard quando non hai bisogno dell'interfaccia List.

Perché un array circolare

Una classica "coda da array" incorre in un problema: dopo alcuni cicli di aggiunta in coda e rimozione dalla testa, l'array si riempie in fondo mentre si accumulano slot vuoti all'inizio. Una soluzione ingenua consisterebbe nello spostare tutto verso sinistra ad ogni dequeue — O(n) per rimozione, con prestazioni pessime.

Il trucco dell'array circolare risolve il problema. La classe mantiene due indici, head e tail, e li lascia avvolgere intorno:

slots:   [ . . . D E F G H A B C ]
                         ^head     ^... wraps to slot 0 ... ^tail

addFirst decrementa head, addLast incrementa tail, entrambi modulo la lunghezza dell'array. removeFirst e removeLast fanno il contrario. Ogni operazione è O(1); l'unico costo è il raddoppio dell'array di supporto quando head colliderebbe con tail, il che è ammortizzato.

Il risultato: nessuna allocazione di nodi per elemento, nessun inseguimento di puntatori, accesso cache-friendly. Questa è la ragione ingegneristica per cui ArrayDeque è solitamente la scelta più veloce per carichi di lavoro con code e stack.

Riepilogo dell'interfaccia Deque

Un Deque ha due estremità. Ogni operazione esiste in tre varianti:

Inoltre, i sinonimi per Queue e stack si mappano sull'estremità della testa:

Quindi Deque è un'unica interfaccia che espone sia una coda che uno stack contemporaneamente, a seconda del nome con cui si chiama la testa. Abbiamo trattato queste mappature nei capitoli su Queue e Stack; Deque è il punto in cui si incontrano.

Cosa aggiunge ArrayDeque

In pratica, molto poco a livello di API — è proprio questo il punto. La classe espone il contratto Deque onestamente: le due estremità, i tre stili di errore per operazione, e clear(), iterator(), descendingIterator(), contains, size, isEmpty. L'iterazione con l'iteratore standard va dalla testa alla coda; descendingIterator è il modo economico per percorrere dalla coda alla testa senza invertire.

I costruttori rispecchiano quelli di ArrayList:

Deque<String> a = new ArrayDeque<>();          // initial capacity 16
Deque<String> b = new ArrayDeque<>(1_000);     // pre-sized
Deque<String> c = new ArrayDeque<>(other);     // from any Collection (head = first iter element)

Dimensiona preventivamente quando conosci il carico di lavoro. Il valore predefinito di 16 viene arrotondato alla potenza di due successiva, e la crescita raddoppia l'array — quindi un milione di chiamate offerLast da un deque di dimensione predefinita scatena circa 16 crescite con copia.

Le regole: niente null, non thread-safe, fail-fast

Tre regole da interiorizzare:

1. ArrayDeque non consente elementi null. Ogni inserimento lancia NullPointerException. Così pollFirst() che restituisce null per una coda vuota rimane inequivocabile.
2. Non è thread-safe. Due thread che mutano lo stesso ArrayDeque lo corromperanno. Per l'uso concorrente, guarda ConcurrentLinkedDeque (lock-free, illimitato) o LinkedBlockingDeque (limitato, bloccante).
3. Iterazione fail-fast. Modificare il deque all'esterno dell'iteratore durante l'iterazione lancia ConcurrentModificationException. Usa Iterator.remove() o removeIf per mutazioni sicure.

Quando scegliere ArrayDeque rispetto alle alternative

Il flusso decisionale:

• Hai bisogno di una Queue? → ArrayDeque. Predefinito.
• Hai bisogno di uno stack? → ArrayDeque. Predefinito. Usa push / pop / peek.
• Hai bisogno di un Deque? → ArrayDeque. Predefinito.
• Hai bisogno sia della semantica Deque che di List sullo stesso oggetto? → LinkedList. Raro.
• Hai bisogno di un ordine di priorità? → PriorityQueue. Astrazione diversa.
• Hai bisogno di accesso concorrente? → ConcurrentLinkedDeque (illimitato) o LinkedBlockingDeque (limitato). La scelta giusta dipende da se hai bisogno di back-pressure.

Il Javadoc esprime la raccomandazione in testo chiaro: "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." Viene direttamente dagli autori del JDK; vale la pena prenderlo alla lettera.

Un esempio pratico: coda, stack, deque, finestra scorrevole

Il programma seguente usa un'istanza di ArrayDeque come coda FIFO, un'altra come stack LIFO e una terza come struttura di supporto per un massimo con finestra scorrevole — un problema classico per cui ArrayDeque è la risposta canonica perché si ha bisogno di mutazioni economiche su entrambe le estremità.

Cosa si può ricavare da questa esecuzione:

• Le sezioni 1 e 2 sono la stessa classe che svolge due compiti chiamando metodi diversi. Coda FIFO: offerLast / pollFirst. Stack LIFO: push / pop. Non c'è nessuna classe separata da imparare.
• descendingIterator() è la scansione inversa economica — utile quando hai costruito un deque come stack e vuoi stamparlo dal basso verso l'alto.
• La funzione di finestra scorrevole usa entrambe le estremità nello stesso ciclo — pollFirst per eliminare gli indici usciti dalla finestra, pollLast per mantenere uno stack monotono decrescente, peekFirst per leggere il massimo corrente. Quell'accesso a doppia estremità è il motivo per cui esiste ArrayDeque; tentare di fare questo con un ArrayList sarebbe quadratico.

Cosa c'è dopo

Hai visto come ArrayDeque implementa entrambe le estremità della storia coda/stack. L'interfaccia che ha implementato per tutto questo tempo merita un capitolo proprio — Deque è il contratto che unisce tutto ciò che abbiamo trattato sulle collezioni simili a code. Lo affronteremo nella prossima sessione.

Esercitazione