Introduzione a Java ArrayDeque

1. Panoramica

In questo tutorial, mostreremo come utilizzare la classe ArrayDeque di Java, che è un'implementazione dell'interfaccia Deque .

Un ArrayDeque (noto anche come "Array Double Ended Queue", pronunciato come "ArrayDeck") è un tipo speciale di array espandibile che ci consente di aggiungere o rimuovere un elemento da entrambi i lati.

Un'implementazione di ArrayDeque può essere utilizzata come Stack (Last-In-First-Out) o Queue (First-In-First-Out).

2. L'API in sintesi

Per ogni operazione abbiamo fondamentalmente due opzioni.

Il primo gruppo è costituito da metodi che generano un'eccezione se l'operazione non riesce. L'altro gruppo restituisce uno stato o un valore:

Operazione Metodo Eccezione di lancio del metodo
Inserimento dalla testa offerFirst (e) addFirst (e)
Rimozione dalla testa pollFirst () removeFirst ()
Recupero da Head peekFirst () getFirst ()
Inserimento dalla coda offerLast (e) addLast (e)
Rimozione dalla coda pollLast () removeLast ()
Recupero dalla coda peekLast () getLast ()

3. Utilizzo di metodi

Diamo un'occhiata ad alcuni semplici esempi di come possiamo utilizzare ArrayDeque .

3.1. Utilizzo di ArrayDeque come stack

Inizieremo con un esempio di come possiamo trattare la classe come uno Stack e spingere un elemento:

@Test public void whenPush_addsAtFirst() { Deque stack = new ArrayDeque(); stack.push("first"); stack.push("second"); assertEquals("second", stack.getFirst()); } 

Vediamo anche come possiamo estrarre un elemento da ArrayDeque , se usato come Stack:

@Test public void whenPop_removesLast() { Deque stack = new ArrayDeque(); stack.push("first"); stack.push("second"); assertEquals("second", stack.pop()); } 

Il metodo pop genera NoSuchElementException quando uno stack è vuoto.

3.2. Utilizzo di ArrayDeque come coda

Cominciamo ora con un semplice esempio che mostra come possiamo offrire un elemento in un ArrayDeque - se usato come una semplice coda :

@Test public void whenOffer_addsAtLast() { Deque queue = new ArrayDeque(); queue.offer("first"); queue.offer("second"); assertEquals("second", queue.getLast()); } 

E vediamo come possiamo eseguire il polling di un elemento da un ArrayDeque , anche se usato come Queue :

@Test public void whenPoll_removesFirst() { Deque queue = new ArrayDeque(); queue.offer("first"); queue.offer("second"); assertEquals("first", queue.poll()); } 

Il metodo poll restituisce un valore nullo se una coda è vuota.

4. Come viene implementato ArrayDeque

Sotto il cofano, ArrayDeque è supportato da un array che raddoppia le sue dimensioni quando viene riempito.

Inizialmente, l'array viene inizializzato con una dimensione di 16. Viene implementato come una coda a doppia estremità in cui mantiene due puntatori, ovvero una testa e una coda.

Vediamo questa logica in azione - ad alto livello.

4.1. ArrayDeque come Stack

Come si può vedere, quando un utente aggiunge un elemento utilizzando il metodo push , sposta il puntatore della testa di uno.

Quando inseriamo un elemento, imposta l'elemento nella posizione della testa come nullo in modo che l'elemento possa essere raccolto in modo indesiderato, quindi sposta indietro il puntatore della testa di uno.

4.2. ArrayDeque come coda

Quando aggiungiamo un elemento utilizzando il metodo dell'offerta , sposta il puntatore di coda di uno.

Mentre quando l'utente esegue il polling di un elemento, imposta l'elemento nella posizione di intestazione su null in modo che l'elemento possa essere sottoposto a garbage collection, quindi sposta il puntatore di intestazione.

4.3. Note su ArrayDeque

Infine, alcune altre note che vale la pena comprendere e ricordare su questa particolare implementazione:

  • Non è thread-safe
  • Gli elementi nulli non sono accettati
  • Funziona molto più velocemente dello Stack sincronizzato
  • È una coda più veloce di LinkedList a causa della migliore località di riferimento
  • La maggior parte delle operazioni ha ammortizzato la complessità temporale costante
  • Un Iterator restituito da un ArrayDeque è veloce
  • ArrayDeque raddoppia automaticamente la dimensione di un array quando il puntatore head e tail si incontrano durante l'aggiunta di un elemento

5. conclusione

In questo breve articolo, abbiamo illustrato l'utilizzo dei metodi in ArrayDeque .

L'implementazione di tutti questi esempi può essere trovata nel progetto GitHub; questo è un progetto basato su Maven, quindi dovrebbe essere facile da importare ed eseguire così com'è.