Perché e quando dovrei utilizzare le strutture di dati stack o code invece di matrici/elenchi? Puoi per favore mostrare un esempio per uno stato che sarà meglio se userai lo stack o la coda?Stack e code, perché?
Perché aiutano a gestire i dati in un modo particolare rispetto agli array e agli elenchi.
coda è first in, first out (FIFO)
Stack è ultima in, first out (LIFO)
array e le liste sono ad accesso casuale. Sono molto flessibili e anche facilmente corruttibili. Se vuoi gestire i tuoi dati come FIFO o LIFO è meglio usare quelli, già implementati, collezioni.
"Elenco" quando distinto da "matrice" generalmente implica un elenco collegato, quindi non esattamente accesso casuale. – Porculus
@Porculus: dipende dall'ambiente. .Net presenta una raccolta List <> generica e una classe ArrayList dalla 1.0 che consente l'accesso casuale tramite l'operatore []. L'implementazione dell'elenco collegato è denominata in modo specifico LinkedList –
Direi che le interfacce più semplici danno alle loro implementazioni più spazio. E c'è sempre l'esempio classico di ricerca, in cui la profondità diventa dapprima prima larghezza sostituendo una coda per uno stack e un'altra ancora con una coda di priorità. – wowest
Quando si desidera applicare un determinato schema di utilizzo nella struttura dati. Significa che quando si esegue il debug di un problema, non ci si deve chiedere se qualcuno abbia inserito un elemento in modo casuale nel mezzo della lista, facendo confusione con alcuni invarianti.
È una questione di intenti. Gli stack e le code vengono spesso implementati utilizzando matrici e elenchi, ma l'aggiunta e la cancellazione di elementi è definita in modo più preciso.
Uno stack o una coda è una struttura dati logica; sarebbe implementato sotto le coperture con una struttura fisica (ad esempio elenco, array, albero, ecc.)
Se si desidera, è possibile eseguire il rollover oppure sfruttare un'astrazione già implementata.
Oltre all'applicazione dell'utilizzo che altri hanno già menzionato, esiste anche un problema di prestazioni. Quando si desidera rimuovere qualcosa dall'inizio di una matrice o di una lista (ArrayList), di solito richiede O (n) tempo, ma per una coda ci vuole O (1) tempo. Questo può fare una grande differenza se ci sono molti elementi.
La domanda è ambigua poiché è possibile rappresentare il tipo di dati astratto di uno stack o di una coda utilizzando una matrice o una struttura di dati collegata.
La differenza tra un'implementazione di elenchi collegati di uno stack o di una coda e un'implementazione di array ha lo stesso compromesso di base di qualsiasi array rispetto alla struttura di dati dinamica.
Una coda collegata/stack collegato ha inserimenti/eliminazioni flessibili ad alta velocità con un'implementazione ragionevole, ma richiede più spazio di archiviazione rispetto a una matrice. Gli inserimenti/eliminazioni sono poco costosi alle estremità di un array finché non si esaurisce lo spazio; un'implementazione dell'array di una coda o uno stack richiederà più lavoro di ridimensionamento, dal momento che è necessario copiare l'originale in una struttura più grande (o fallire con un errore di overflow).
Gli array/elenchi e gli stack/code non sono concetti che si escludono a vicenda. Infatti, qualsiasi stack o implementazione di code che trovi sono quasi certamente utilizzando sia array che liste sotto il cofano.
Le strutture di array e di elenchi forniscono una descrizione del modo in cui i dati vengono archiviati, un lungo periodo con garanzie della complessità delle operazioni fondamentali sulle strutture.
Stack e code forniscono una descrizione di livello elevato di come gli elementi vengono inseriti o rimossi. FIFO per le code, FILO per le pile.
Ad esempio. se stai implementando una coda di messaggi, userai una coda. Ma la coda stessa può memorizzare ogni messaggio in un elenco. "Spingendo" un messaggio in cima alla lista, "scatta" un messaggio dalla fine della lista.
Lo stack e la coda sono modi più avanzati di gestire una raccolta che la matrice stessa, che non stabilisce alcun ordine nel modo in cui gli elementi si comportano all'interno della raccolta.
Lo Stack (LIFO - Last in first out) e una coda (FIFO - First in First out) stabiliscono e ordinano in cui i tuoi elementi vengono inseriti e rimossi da una raccolta.
È possibile utilizzare una matrice o un elenco collegato come struttura di archiviazione per implementare il modello di stack o coda. O persino creare con quelle strutture di base modelli più complessi come Alberi binari o code di priorità, che potrebbero anche portare non solo un ordine nell'inserimento e nella rimozione di elementi, ma anche nell'ordinarli all'interno della raccolta.
Sei stato in una caffetteria, giusto? e ho visto una pila di piatti? Quando una piastra pulita viene aggiunta alla pila, viene messa sopra. Quando una piastra viene rimossa, viene rimossa dall'alto. Quindi è chiamato Last-In-First-Out (LIFO). Una pila di computer è così, tranne che contiene numeri, e se ne può fare uno da una matrice o da una lista. (Se la pila di piatti ha una molla al di sotto, ti dicono di "spingerla" sulla parte superiore, e quando ne rimuovi una, la "spegni". Ecco da dove provengono.)
Nella caffetteria, vai dietro, dove lavano i piatti. Hanno un nastro trasportatore in cui mettono i piatti da lavare in un'estremità e ne escono dall'altra parte, nello stesso ordine. Questa è una coda o FIFO (First-In-First-Out). Puoi anche creare uno di questi da un array o da un elenco, se lo desideri.
A cosa servono? Supponiamo che tu abbia una struttura dati ad albero (che è come un vero albero fatto di legno eccetto che capovolto), e vuoi scrivere un programma per attraversarlo completamente, in modo da stampare tutte le foglie.
Un modo è quello di fare una passeggiata in profondità. Parti dal tronco e vai al primo ramo, quindi vai al primo ramo di quel ramo, e così via, fino a quando arrivi a una foglia e stampalo. Ma come fai a fare il backup per arrivare al prossimo ramo? Bene, ogni volta che vai giù per un ramo, "spingi" alcune informazioni nel tuo stack, e quando esegui il backup lo "fai fuori" di nuovo, e questo ti dice quale ramo prendere dopo. È così che tieni traccia di quale ramo fare in seguito in ogni punto.
Un altro modo è un larghezza a piedi. Partendo dal bagagliaio, annulli tutti i rami dal tronco e metti quei numeri nella coda. Poi prendi un numero dall'altra parte, vai a quel ramo, e per ogni ramo che esce da è, di nuovo li numeri (consecutivamente con il primo) e li metti in coda. Mentre continui a fare questo, visiterai prima i rami che sono 1 ramo lontano dal tronco. Quindi visiterai tutti i rami distanti 2 rami dal tronco e così via. Alla fine arriverete alle foglie e potrete stamparle.
Questi sono due concetti di base nella programmazione.
Penso che stack e coda siano entrambi concetti di accesso alla memoria che vengono utilizzati in base alla domanda dell'applicazione. D'altra parte, array e liste sono due tecniche di accesso alla memoria e sono utilizzate per implementare concetti di stack (LIFO) e di coda (FIFO).
stack e code sono implementati con matrici ed elenchi. – Yada
Potrebbe essere utile consultare un testo su Strutture dati. Questo è in genere un requisito di base per tutti gli studenti CS e DP. –