Quando utilizzare la coda sull'arrayist

Question

Un argomento di base per utilizzare una coda su un ArrayList è che Queue garantisce il comportamento FIFO.

Ma se aggiungo 10 elementi a un ArrayList e quindi eseguo un'iterazione sugli elementi a partire dall'elemento 0, quindi recupererò gli elementi nello stesso ordine in cui sono stati aggiunti. Quindi, in sostanza, ciò garantisce un comportamento FIFO.

Cosa c'è di così speciale in Queue rispetto al tradizionale ArrayList?

Answer 1

Se ti ho dato un'istanza Queue, allora sapresti che chiamando iterativamente remove() recupereresti gli elementi nell'ordine FIFO. Se ti ho dato un'istanza ArrayList, non puoi garantire tale garanzia.

Prendere il seguente codice di esempio:

 ArrayList<Integer> list = new ArrayList<Integer>(); 
    list.add(5); 
    list.add(4); 
    list.add(3); 
    list.add(2); 
    list.add(1); 


    list.set(4,5); 
    list.set(3,4); 
    list.set(2,3); 
    list.set(1,2); 
    list.set(0,1); 

    System.out.println(list); 

Se dovessi ora di darvi questa lista, allora il mio l'iterazione 0-4 non otterrebbe gli elementi in ordine FIFO.

Inoltre, direi che un'altra differenza è l'astrazione. Con un'istanza Queue non devi preoccuparti degli indici e questo rende le cose più facili da pensare se non hai bisogno di tutto ciò che ArrayList ha da offrire.

Answer 2

Ad esempio, i metodi Queuepoll() e remove() recuperano l'elemento e lo rimuove dalla coda.

Alcune implementazioni dell'interfaccia Queue (PriorityQueue) consentono di impostare una priorità agli elementi e di recuperarli grazie a questa priorità. È molto più di un comportamento FIFO in quest'ultimo caso.

Answer 3

È possibile guardare lo javadoc here. La differenza principale è un List che ti permette di guardare qualsiasi elemento quando vuoi. Una coda ti consente solo di guardare quella "successiva".

Pensateci come una vera coda o come una fila per il registratore di cassa in un negozio di alimentari. Non chiedi al tizio nel mezzo o alla fine di pagare il prossimo, chiedi sempre al tizio che è di fronte/aspetta più a lungo.

Vale la pena notare che alcune liste sono code. Guarda LinkedList, per esempio.

Answer 4

La differenza è che per una coda, è possibile estrarre gli elementi in ordine FIFO. Per un ArrayList, non hai idea di quale ordine sono stati aggiunti gli elementi. A seconda di come lo si utilizza, è possibile imporre l'ordinamento FIFO su un ArrayList. Potrei anche progettare un wrapper per una coda che mi consenta di estrarre l'elemento che ho sempre voluto.

Il punto che sto cercando di fare è che queste classi sono progettate per essere bravi in ​​qualcosa. Non devi usarli per questo, ma questo è ciò per cui sono stati progettati e ottimizzati. Le code sono molto brave nell'aggiunta e nella rimozione di elementi, ma sono cattive se devi cercarle. Le liste di array, d'altra parte, sono un po 'più lente per aggiungere elementi, ma consentono un facile accesso casuale. Non lo vedrai nella maggior parte delle applicazioni che scrivi, ma spesso c'è una penalizzazione delle prestazioni per scegliere l'una rispetto all'altra.

Answer 5

Le limitazioni imposte a una coda (FIFO, nessun accesso casuale), rispetto a un ArrayList, consentono di ottimizzare la struttura dei dati, di avere una concorrenza migliore e di essere un progetto più appropriato e più pulito quando richiesto.

Per quanto riguarda l'ottimizzazione e la concorrenza, si immagini lo scenario comune in cui un produttore riempie una coda mentre un consumatore lo consuma. Se usassimo un ArrayList per questo, nell'implementazione ingenua ogni rimozione del primo elemento causerebbe un'operazione di spostamento su ArrayList per spostarsi verso il basso ogni altro elemento. Questo è molto inefficiente, specialmente in un'implementazione concorrente poiché l'elenco sarebbe bloccato per la durata dell'intera operazione di cambio.

Per quanto riguarda la progettazione, se gli elementi sono accessibili in modalità FIFO, l'uso di una coda comunica automaticamente tale intenzione, mentre un elenco non lo fa. Questa chiarezza di comunicazione consente una comprensione più semplice del codice e potrebbe rendere il codice più robusto e privo di errori.

Answer 6

Sì!

Avrei usato i metodi poll() e peek() nella coda che restituisce il valore e rimuove, esamina rispettivamente l'elemento head. Anche questi metodi forniscono un valore speciale null se l'operazione fallisce e non genera un'eccezione poiché con remove() il metodo genererà un'eccezione di nosuchelement.

Rif: docs.oracle.com

Answer 7

Si consideri una situazione in cui i processi casuali aggiornare un ArrayList in modo casuale e che siamo tenuti a elaborarli in fifo?

Non c'è assolutamente alcun modo per farlo, ma di cambiare la struttura dati da ArrayList a coda