LIFO vs FIFO
LIFO oznacza Last In, First Out. Podobnie jak w przypadku, ostatni element włożony do stosu to pierwszy przedmiot wyjęty ze stosu.
To, co opisałeś z analogią swoich potraw (w pierwszej wersji ), to kolejka lub FIFO, pierwsze wejście, pierwsze wyjście.
Główna różnica między nimi polega na tym, że LIFO / stos wypycha (wstawia) i wyskakuje (usuwa) z tego samego końca, a FIFO / kolejka robi to z przeciwnych końców.
// Both:
Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]
// Stack // Queue
Pop() Pop()
-> [a, b] -> [b, c]
Wskaźnik stosu
Rzućmy okiem na to, co dzieje się pod maską stosu. Oto trochę pamięci, każde pole to adres:
...[ ][ ][ ][ ]... char* sp;
^- Stack Pointer (SP)
I jest wskaźnik stosu wskazujący na dole aktualnie pustego stosu (to, czy stos rośnie czy rośnie, nie jest tutaj szczególnie istotne, więc zignorujemy to, ale oczywiście w prawdziwym świecie, który określa, która operacja dodaje i który odejmuje od SP).
Więc pchnijmy a, b, and cjeszcze raz. Grafika po lewej, operacja „wysokiego poziomu” po środku, pseudo-kod C po prawej:
...[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
Jak widać, za każdym razem pushwstawia on argument w miejscu, w którym aktualnie wskazuje wskaźnik stosu, i dostosowuje wskaźnik stosu, aby wskazywał w następnym miejscu.
Teraz pop:
...[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
Popjest przeciwieństwem push, dostosowuje wskaźnik stosu, aby wskazywał na poprzednią lokalizację i usuwa przedmiot, który tam był (zwykle w celu zwrócenia go temu, kto zadzwonił pop).
Pewnie to zauważyłeś bi cwciąż jesteś w pamięci. Chcę was zapewnić, że to nie są literówki. Wrócimy do tego wkrótce.
Życie bez wskaźnika stosu
Zobaczmy, co się stanie, jeśli nie będziemy mieć wskaźnika stosu. Zaczynając od ponownego naciśnięcia:
...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]... Push(a) ? = 'a';
Eee, hmm ... jeśli nie mamy wskaźnika stosu, nie możemy przenieść czegoś na adres, na który wskazuje. Może możemy użyć wskaźnika, który wskazuje na podstawę zamiast na górę.
...[ ][ ][ ][ ]... 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
O o. Ponieważ nie możemy zmienić stałej wartości podstawy stosu, po prostu nadpisaliśmy ają, przesuwając bw to samo miejsce.
Dlaczego nie śledzimy, ile razy pchaliśmy. Będziemy także musieli śledzić czasy, w których pojawiliśmy się.
...[ ][ ][ ][ ]... 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
Cóż, działa, ale w rzeczywistości jest dość podobny do wcześniejszego, z wyjątkiem tego, że *pointerjest tańszy niż pointer[offset](bez dodatkowej arytmetyki), nie wspominając już o mniejszym pisaniu. Wydaje mi się to stratą.
Spróbujmy ponownie. Zamiast używać stylu łańcucha Pascal do znajdowania końca kolekcji opartej na tablicy (śledzenie liczby elementów w kolekcji), spróbujmy stylu łańcucha C (skanowanie od początku do końca):
...[ ][ ][ ][ ]... 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 '('
Być może odgadłeś już tutaj problem. Niezainicjowana pamięć nie ma gwarancji, że wynosi 0. Więc kiedy szukamy góry do miejsca a, w końcu pomijamy kilka nieużywanych lokalizacji pamięci, które zawierają losowe śmieci. Podobnie, gdy skanujemy do góry, kończymy przeskakiwanie daleko poza to, aco właśnie popchnęliśmy, aż w końcu znajdujemy inną lokalizację pamięci, która akurat się znajduje 0, i cofamy się i zwracamy losowe śmieci tuż przed tym.
Łatwo to naprawić, musimy tylko dodać operacje Pushi Popupewnić się, że góra stosu jest zawsze aktualizowana, aby oznaczać ją 0, i musimy zainicjować stos za pomocą takiego terminatora. Oczywiście oznacza to również, że nie możemy mieć 0(lub jakiejkolwiek wartości, którą wybieramy jako terminator) jako rzeczywistej wartości na stosie.
Ponadto zmieniliśmy również operacje O (1) na operacje O (n).
TL; DR
Wskaźnik stosu śledzi górę stosu, w którym zachodzi cała akcja. Istnieją sposoby, aby się go pozbyć ( bp[count]i topzasadniczo nadal są wskaźnikiem stosu), ale oba są bardziej skomplikowane i wolniejsze niż zwykły wskaźnik stosu. I nie wiedząc, gdzie jest góra stosu, oznacza, że nie możesz użyć stosu.
Uwaga: Wskaźnik stosu wskazujący na „dół” stosu wykonawczego w x86 może być nieporozumieniem związanym z odwróceniem całego stosu wykonawczego. Innymi słowy, podstawa stosu jest umieszczona pod wysokim adresem pamięci, a wierzchołek stosu rośnie do niższych adresów pamięci. Wskaźnik stosu robi punkt na czubku stosu gdzie występuje cała akcja, tylko, że końcówka jest na adres pamięci niższej niż podstawy stosu.