Recentemente, in un'intervista mi è stato chiesto lo svantaggio di utilizzare la coda circolare. Non potevo pensare a nessuno. Cercando su Internet l'unica risposta che ho trovato è che è difficile da implementare rispetto alla coda lineare :). C'è qualche altro svantaggio?Svantaggio della coda circolare?
Mi sembra che qualsiasi codice che attraversa la coda debba tenere traccia del primo nodo per rilevare la fine della traversa. Ma in un ambiente multi-thread un altro thread potrebbe rimuovere il primo nodo, il che farebbe entrare il thread di movimento in un ciclo infinito. Quindi il thread di movimento dovrebbe mantenere il primo nodo bloccato per tutta la durata del suo ciclo attraverso la coda.
Quindi, di solito, ci sono rischi nell'usare qualsiasi tipo di lista durante l'enumerazione. Ad esempio, la coda di un normale elenco collegato potrebbe essere cancellata e spostata in testa (non raro quando si tratta di code), che potrebbe interrompere un iteratore. – nneonneo
Non succederà nel caso della memoria condivisa tra più processi? Chiedo come si menziona esplicitamente * threads * – asheeshr
@AshRj Sì, potrebbe certamente accadere con più processi. –
Direi che il più grande svantaggio di una coda circolare è che è possibile memorizzare solo gli elementi di lunghezza. Se lo si utilizza come buffer, si limita la profondità della cronologia.
Un altro piccolo svantaggio è che è difficile distinguere una coda vuota da una coda completa senza conservare ulteriori informazioni.
Non così difficile. Vedi i commenti sulla domanda. Ci sono almeno 2 modi per farlo ... –
La risposta che l'intervistatore cercava probabilmente dipende da un contesto aggiuntivo che non è nella domanda di cui sopra.
Ad esempio, spesso le code circolari sono considerate per sistemi produttore/consumatore altamente concorrenti. Quando la coda è piena, le operazioni nella parte anteriore e posteriore della coda possono contendersi per le stesse linee di cache e questo può essere un problema in contesti come questo.
O forse l'intervistatore voleva che tu parlassi di quanto è più semplice in un linguaggio raccolto con garbage per creare una coda collegata bloccata rispetto a una coda circolare basata su array.
O forse si tratta solo di come si può fare un uso migliore dei contenitori vettoriali forniti dalla propria lingua se si utilizza una coda lineare con spostamento periodico anziché una coda circolare.
seconda realizzazione, potrebbe essere necessario lasciare un nodo vuoto in una coda circolare, mentre una coda lineare ca essere riempita completamente. Non è uno svantaggio, a meno che ogni nodo non sia gigantesco! – asheeshr
perché un nodo deve essere lasciato vuoto? –
Dipende da come si implementa la coda circolare. Se si memorizzano i dati in ogni nodo, non esiste un modo semplice per distinguere tra una lista vuota e una lista completa. – asheeshr