Non vedo il motivo per avere classi per stack, code e deques se abbiamo l'elenco collegato della struttura dati, dal momento che un elenco collegato può fungere sia da stack che da coda (e ha sempre le funzioni di entrambi, se non appena nominato diversamente).
Quindi questo porta la mia domanda,
C'è una ragione specifica per utilizzare pile e code su un elenco collegato oltre alla leggibilità?
ultimo tidbit, programma in Java e .Net
Stack e code sono modi di lavorare con memoria contigua. Gli elenchi collegati non lo sono. Ora sicuro, qualsiasi problema che puoi risolvere con una struttura potresti risolvere con un altro e schiaffarti abbastanza astrazione su di esso che non potresti dire la differenza. Quindi qual è la vera differenza? Prestazione. La scelta tra queste strutture riguarda ciò che NON fai con loro perché non lo fanno bene.
Gli elenchi collegati rendono facili gli inserimenti nel loro mezzo. Rendono duro il percorso.
Le pile e le code preferiscono fare gli inserimenti e la rimozione alla fine.
Nessuno rende impossibile fare nulla in quanto è possibile ricostruire l'intera struttura. Il problema è il costo che arriva.
Una cosa che mi ha aiutato lungo la strada è questo piccoletto:
Eccounocheincludelestrutturemenopopolari:
Sotto il cofano è tutto un grande array chiamato memoria ad accesso casuale. L'uso di queste strutture non lo cambia. Ma se puoi prevedere ciò di cui non hai bisogno, puoi scegliere la struttura giusta che ti aiuterà a usare quella memoria molto bene.
Adoro CandiedOrange's answer anche se una coda o uno stack possono essere implementati utilizzando un elenco collegato, o un elenco collegato non terminato, o una rappresentazione di array completamente contigua, o qualcos'altro.
Ma voglio essere pienamente d'accordo, echo e affinare una parte che riguarda davvero i progetti che fanno less . Il minimalismo è molto utile per un design in tutti i modi, dall'avere un minor numero di modi per abusare di un progetto per fornirgli più spazio per essere implementato in modo efficiente, per esprimere meglio le tue esigenze nel codice che utilizza un particolare design (uno che fa meno racconta i lettori del tuo codice tutte le cose che non farai).
Le pile LIFO e le code FIFO tipicamente fanno meno di, diciamo, una lista doppiamente collegata e questo non rende i loro progetti inferiori. In un certo numero di casi, potrebbe renderli superiori. E questo vale anche per gli oggetti tangibili nel mondo reale. Ad esempio, qualcuno potrebbe chiedere: "perché usare uno di questi" ?
..."quando ne hai uno?"
Edovrebbeessereabbastanzaovvioinquestocaso.Maciòvaleancheperiprogettinelsoftware.Faredipiùnonènecessariamenteequivalenteasuperiore.Quandositrattadiefficienzagiornaliera,nonsitrattasemprediutilizzarealgoritmiall'avanguardiaecodicivettorialiparallelizzati.Avoltesitrattasolodiassicurartidinonpagarepercosechenontiservono.Usareprogettichefornisconomoltopiùdiquellochetiservespessoestraggonoqueltipodicosto,comequelmultitoolsopraquandotuttociòdicuihaiveramentebisognoèuncoltelloaffilatopertagliareilsashimi.
Enaturalmentequandodichiarichiaramenteituoirequisitidiprogettazioneedici"Tutto ciò di cui ho bisogno è un coltello affilato per tagliare il sashimi", allora gli implementatori possono trovare implementazioni molto più efficienti e affidabili in un breve periodo di tempo per quello una serie ristretta di requisiti che se tu dicessi "Uhh, non so di cosa ho bisogno.Qui c'è una lista di tutte le possibilità di cose che potrei o non potrei avere bisogno", a quel punto potrebbero volerci anni e poi consegnarti Multitool analogico. E naturalmente, se ti vedo portare con te un coltello da sushi, posso dedurre più facilmente che probabilmente stai tagliando il pesce e capisci le tue intenzioni che se avessi in mano un multitool.
Echo del commento @rwong, usando una coda o uno stack
Leggi altre domande sui tag java data-structures theory linked-list