Qual è la differenza tra una matrice e uno stack?

Bene, puoi certamente implementare uno stack con un array. La differenza è nell'accesso. In un array, hai una lista di elementi e puoi accedervi in qualsiasi momento. (Pensa a un mucchio di blocchi di legno disposti tutti in fila.)

Ma in una pila, non ci sono operazioni di accesso casuale; ci sono solo Push , Peek e Pop , che si occupano esclusivamente dell'elemento in cima allo stack. (Pensa ai blocchi di legno accatastati verticalmente ora. Non puoi toccare nulla sotto la cima della torre o cadrà sopra.)

In una pila pura, le uniche operazioni consentite sono Push , Pop e Peek ma in termini pratici, non è esattamente vero. O meglio, l'operazione Peek spesso ti permette di guardare qualsiasi posizione sullo stack, ma il problema è che è relativo a un estremo dello stack.

Quindi, come altri hanno detto, un array è ad accesso casuale e tutto è riferito all'inizio dell'array .

In una pila, puoi aggiungere / rimuovere solo alla fine di lavoro della pila, ma hai ancora accesso casuale a lettura ma si fa riferimento al lato di lavoro . Questa è la differenza fondamentale.

Ad esempio, quando si passano i parametri su una pila a una funzione, il chiamato non deve escludere i parametri per guardarli. Spinge semplicemente le variabili locali nello stack e fa riferimento a tutte le variabili locali e ai parametri in base a un offset dal puntatore dello stack. Se si stesse usando solo un array, come avrebbe potuto sapere il chi calle dove cercare i suoi parametri? Quando il callee è terminato, apre le sue variabili locali, inserisce un valore di ritorno, restituisce il controllo al chiamante e il chiamante fa scattare il valore di ritorno (se presente), quindi apre i parametri dallo stack. Il bello è che funziona indipendentemente dal numero di chiamate all'interno delle chiamate di funzione (supponendo che non si esaurisca lo spazio disponibile).

Questo è un particolare uso / implementazione, ma illustra la differenza: l'array è sempre referenziato dall'inizio ma gli stack sono sempre referenziati da qualche posizione finale funzionante.

Una possibile implementazione di uno stack è un array più un indice per ricordare dove si trova la fine del lavoro.

Penso che la più grande confusione in corso qui sia l'implementazione rispetto alle strutture dati di base.

Nella maggior parte (più lingue di base) una matrice rappresenta un insieme di elementi di lunghezza fissa a cui è possibile accedere in qualsiasi momento. Il fatto che tu abbia un sacco di elementi come questo non ti dice nulla su come dovrebbe essere usato (e francamente un computer non saprà / cura come lo usi, purché tu non violi l'uso).

Una pila è un'astrazione utilizzata per rappresentare i dati che devono essere gestiti in un certo modo. Questo è un concetto astratto perché dice solo che deve avere qualche subroutine / metodo / funzione che può aggiungere in alto o rimuovere dall'alto, mentre i dati al di sotto della parte superiore non vengono toccati. Puramente la tua scelta di utilizzare un array in questo modo.

È possibile creare uno stack con diversi tipi di strutture di dati: array (con dimensioni massime), array dinamici (che possono crescere quando lo spazio è esaurito) o elenchi collegati. Personalmente ritengo che una lista concatenata rappresenti le restrizioni di uno stack il migliore, visto che devi impegnarti un po 'per vedere le cose oltre il primo elemento ed è molto facile aggiungerlo in avanti e rimuoverlo dal davanti.

Quindi puoi usare un array per creare uno stack, ma non sono equivalenti

Their responsibilities are different:

• Lo stack deve essere in grado di far apparire elementi nello stack e spingere gli elementi dallo stack, quindi perché normalmente ha metodi Pop() e Push()

• La responsabilità dell'array è di ottenere / impostare l'elemento su un indice specificato

È possibile recuperare un elemento da qualsiasi indice di un array \ \.

Con uno stack, puoi recuperare un oggetto nel mezzo dello stack A, usando un altro stack: B.

Continui a prendere l'elemento in cima di A e lo metti in B fino a quando non trovi l'oggetto desiderato di A, quindi rimetti gli oggetti da B in cima allo stack A.

Quindi, per i dati che richiedono la possibilità di recuperare un indice arbitrario, lo stack è più difficile da utilizzare.

Nella situazione in cui vuoi il comportamento "last in, first out", uno stack ti darà meno overhead di un array.

Non mi spingerei troppo lontano da dire che sono "molto simili."

Un array viene usato per contenere cose che verranno successivamente consultate in sequenza o attraverso l'indice. La struttura dei dati non implica alcun tipo di metodo di accesso (FIFO, LIFO, FILO, ecc.) Ma può essere usato in questo modo se lo si desidera.

Lo stack è un modo per tenere traccia delle cose mentre vengono generate. Un metodo di accesso è implicito / richiesto in base al tipo di stack creato. Una pila di frame sarebbe un esempio LIFO. Disclaimer - Potrei mescolare qui la tassonomia della struttura dei dati e uno stack potrebbe consentire solo LIFO. Sarebbe un diverso tipo di coda altrimenti.

Quindi potrei usare un array come stack (anche se non lo vorrei), ma non posso usare uno stack come array (a meno che non lavori molto duramente)

È possibile accedere ai dati di un array mediante una chiave o un indice. È possibile accedere ai dati in una pila quando vengono estratti dalla cima della pila. Ciò significa che l'accesso ai dati da un array è facile se si conosce il suo indice. Accedere ai dati da uno stack significa che devi mantenere gli elementi popping finché non trovi quello che stavi cercando, il che significa che l'accesso ai dati può richiedere più tempo.

Un array proviene dal punto di vista dei programmatori, fissato nella posizione e nella dimensione, sai dove ci sei dentro e dove si trova l'intera cosa. Hai accesso a tutto questo.

Con uno stack, ti siedi da un lato ma non hai idea delle sue dimensioni o di quanto lontano puoi andare sicuro. Il tuo accesso ad esso è limitato all'importo che hai assegnato, spesso non sai nemmeno se allocare l'importo desiderato se hai appena sbattuto l'heap o lo spazio del programma. La tua vista di una pila è un piccolo array che ti sei assegnato, la dimensione che volevi, hai il controllo e puoi vedere. La tua porzione non è diversa da una matrice. La differenza sta nel fatto che il tuo array è attaccato su un'estremità di un altro array per ragioni di argomentazione e terminologia, di cui non hai visibilità, non hai idea di quanto grande o piccolo, e non puoi toccarlo senza causare danni. Un array, a meno che non sia globale, viene spesso implementato nello stack in ogni caso, quindi la matrice e lo stack condividono lo stesso spazio per la durata di tale funzione.

Se vuoi entrare nel lato hardware, ovviamente è un processore specifico, ma generalmente l'array è basato su un punto / indirizzo noto, la dimensione è nota al compilatore / programmatore e gli indirizzi sono calcolati in esso, a volte usando l'indirizzamento di offset di registro (carica un valore dall'indirizzo definito da questo valore di registro di base più questo valore di registro di offset, allo stesso modo quando compilato potrebbe essere un offset immediato non necessariamente basato sul registro, dipende ovviamente dal processore) che in l'assemblaggio somiglia molto all'accesso ad un array nel codice di alto livello. Allo stesso modo con lo stack, se disponibile, è possibile utilizzare l'indirizzamento di registro o offset immediato, spesso anche se utilizza un registro speciale, o il puntatore dello stack stesso o un registro riservato dal compilatore / programmatore da utilizzare per accedere allo stack frame per quello funzione. E per alcuni processori vengono utilizzate speciali funzioni di accesso allo stack e / o richieste per accedere allo stack. Hai istruzioni push e pop, ma non vengono utilizzate tutte le volte in cui penseresti e non ti applichi veramente a questa domanda. Per alcuni processori push e pop sono alias per istruzioni che possono essere utilizzate con qualsiasi registro, ovunque, non solo il puntatore dello stack in pila, eliminando ulteriormente il push e il pop dall'essere correlati a questa domanda.