LIFO vs FIFO
LIFO sta per Last In, First Out. Come in, l'ultimo oggetto messo nella pila è il primo oggetto estratto dalla pila.
Ciò che hai descritto con l'analogia dei tuoi piatti (nella prima revisione ), è una coda o FIFO, in primo luogo In, First Out.
La principale differenza tra i due, essendo che il LIFO / stack spinge (inserisce) e schiocca (rimuove) dalla stessa estremità, e una coda / coda FIFO fa da estremità opposte.
// Both:
Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]
// Stack // Queue
Pop() Pop()
-> [a, b] -> [b, c]
Il puntatore dello stack
Diamo un'occhiata a cosa sta succedendo sotto il cofano della pila.
Ecco un po 'di memoria, ogni scatola è un indirizzo:
...[ ][ ][ ][ ]... char* sp;
^- Stack Pointer (SP)
E c'è un puntatore stack che punta nella parte inferiore dello stack attualmente vuoto (se lo stack cresce o diminuisce non è particolarmente rilevante qui, quindi lo ignoreremo, ma ovviamente nel mondo reale, ciò determina quale operazione aggiunge e che sottrae dallo SP).
Quindi riproviamo di nuovo a, b, and c . Grafica a sinistra, operazione di "alto livello" nel mezzo, pseudo codice C-ish a destra:
...[a][ ][ ][ ]... Push('a') *sp = 'a';
^- SP
...[a][ ][ ][ ]... ++sp;
^- SP
...[a][b][ ][ ]... Push('b') *sp = 'b';
^- SP
...[a][b][ ][ ]... ++sp;
^- SP
...[a][b][c][ ]... Push('c') *sp = 'c';
^- SP
...[a][b][c][ ]... ++sp;
^- SP
Come puoi vedere, ogni volta che push , inserisce l'argomento nella posizione in cui il puntatore dello stack sta puntando al momento e regola il puntatore dello stack in modo che punti alla posizione successiva.
Ora facciamo un salto:
...[a][b][c][ ]... Pop() --sp;
^- SP
...[a][b][c][ ]... return *sp; // returns 'c'
^- SP
...[a][b][c][ ]... Pop() --sp;
^- SP
...[a][b][c][ ]... return *sp; // returns 'b'
^- SP
Pop è l'opposto di push , regola il puntatore dello stack in modo che punti alla posizione precedente e rimuove l'elemento che era lì (in genere per restituirlo a chiunque abbia chiamato pop ).
Probabilmente hai notato che b e c sono ancora in memoria. Voglio solo assicurarti che quelli non sono errori di battitura. Torneremo su questo a breve.
Vita senza un puntatore dello stack
Vediamo cosa succede se non abbiamo un puntatore allo stack. Iniziando con lo spingere di nuovo:
...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]... Push(a) ? = 'a';
Er, hmm ... se non abbiamo un puntatore stack, allora non possiamo spostare qualcosa all'indirizzo a cui punta. Forse possiamo usare un puntatore che punta alla base anziché alla cima.
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
...[a][ ][ ][ ]... Push(a) *bp = 'a';
^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]... Push(b) *bp = 'b';
^- bp
Uh oh. Poiché non possiamo modificare il valore fisso della base dello stack, abbiamo appena sovrascritto a premendo b nella stessa posizione.
Bene, perché non teniamo traccia di quante volte abbiamo spinto. E dovremo anche tenere traccia dei tempi che abbiamo spuntato.
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
int count = 0;
...[a][ ][ ][ ]... Push(a) bp[count] = 'a';
^- bp
...[a][ ][ ][ ]... ++count;
^- bp
...[a][b][ ][ ]... Push(a) bp[count] = 'b';
^- bp
...[a][b][ ][ ]... ++count;
^- bp
...[a][b][ ][ ]... Pop() --count;
^- bp
...[a][b][ ][ ]... return bp[count]; //returns b
^- bp
Funziona bene, ma in realtà è molto simile a prima, eccetto *pointer è più economico di pointer[offset] (senza aritmetica extra), per non dire che è meno da digitare. Mi sembra una perdita.
Proviamo di nuovo. Invece di utilizzare lo stile di stringa Pascal per trovare la fine di una raccolta basata su array (tenendo traccia di quanti elementi sono presenti nella raccolta), proviamo lo stile di stringa C (scansione dall'inizio alla fine):
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
...[ ][ ][ ][ ]... Push(a) char* top = bp;
^- bp, top
while(*top != 0) { ++top; }
...[ ][ ][ ][a]... *top = 'a';
^- bp ^- top
...[ ][ ][ ][ ]... Pop() char* top = bp;
^- bp, top
while(*top != 0) { ++top; }
...[ ][ ][ ][a]... --top;
^- bp ^- top return *top; // returns '('
Potresti aver già indovinato il problema qui. Non è garantito che la memoria non inizializzata sia pari a 0. Quindi, quando cerchiamo la parte superiore per posizionare a , finiamo per ignorare una serie di posizioni di memoria inutilizzate che contengono elementi casuali. Allo stesso modo, quando eseguiamo la scansione verso l'alto, finiamo per saltare oltre il a che abbiamo appena spinto fino a quando non troviamo finalmente un'altra posizione di memoria che è appena 0 , e torniamo indietro e restituiamo la spazzatura casuale poco prima.
Questo è abbastanza facile da correggere, dobbiamo solo aggiungere operazioni a Push e Pop per assicurarci che la cima dello stack sia sempre aggiornata per essere contrassegnata con 0 , e dobbiamo inizializzare lo stack con un tale terminatore. Ovviamente ciò significa anche che non possiamo avere un 0 (o qualsiasi valore che prendiamo come terminatore) come un valore reale nello stack.
Inoltre, abbiamo anche cambiato le operazioni di O (1) in operazioni O (n).
TL; DR
Il puntatore dello stack tiene traccia della parte superiore della pila, dove si verifica tutto dell'azione. Ci sono modi per risolverlo ( bp[count] e top sono essenzialmente ancora il puntatore dello stack), ma entrambi finiscono per essere più complicati e più lenti del semplice puntatore dello stack. E non sapere dove sia la cima della pila significa che non puoi usare lo stack.
Nota: il puntatore dello stack che punta al "fondo" dello stack di runtime in x86 potrebbe essere un equivoco relativo all'intero stack di runtime capovolto. In altre parole, la base della pila viene posizionata su un indirizzo di memoria elevato e la punta della pila si riduce a indirizzi di memoria inferiori. Il puntatore dello stack fa punta sulla punta dello stack in cui si verifica tutta l'azione, solo quel suggerimento si trova su un indirizzo di memoria inferiore rispetto alla base dello stack.