Dodaj tę stronę do książki
Pokaż książkę (0 stron)
Proponowane strony
Stos (ang. Stack) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane (bufor typu LIFO, Last In, First Out; ostatni na wejściu, pierwszy na wyjściu). Ideę stosu danych można zilustrować jako stos położonych jedna na drugiej książek – nowy egzemplarz kładzie się na wierzch stosu i z wierzchu stosu zdejmuje się kolejne egzemplarze. Elementy stosu poniżej wierzchołka można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.
Stos jest stosowany w systemach komputerowych na wszystkich poziomach funkcjonowania systemów informatycznych. Używany jest przez procesory do chwilowego zapamiętywania rejestrów procesora, do przechowywania zmiennych lokalnych, a także w programowaniu wysokopoziomowym.
Przeciwieństwem stosu jest kolejka, bufor typu FIFO (ang. First In, First Out; pierwszy na wejściu, pierwszy na wyjściu), w którym dane obsługiwane są w takiej kolejności, w jakiej zostały dostarczone (jak w kolejce do kasy).
Spis treści |
Stos został wymyślony i opracowany przez niemieckiego naukowca informatyka Friedricha L. Baura w 1955 a opatentowany w 1957. Za ten wynalazek Friedrich L. Bauer, dostał w 1988 od IEEE nagrodę Computer Society Pioneer Award
W powyższym opisie pojawiły się pewne operacje, jakie można wykonywać na stosie. Oto ich formalny zapis:
Strukturami danych służącymi do reprezentacji stosu mogą być tablice (gdy znamy maksymalny rozmiar stosu), tablice dynamiczne lub listy. Złożoność obliczeniowa operacji na stosie zależy od konkretnej implementacji, ale w większości przypadków jest to czas stały O(1).
Class Stos
{
Tablica[0..MAX_ROZMIAR]; //tablica elementow stosu o rozmiarze MAX_ROZMIAR
licznik = 0;
Push(Wartosc) {
Tablica[licznik] = Wartosc;
licznik = licznik + 1;
};
Pop() {
licznik = licznik - 1;
return Tablica[licznik];
};
};
Class Element_stosu
poprzednik // Wskaznik na poprzedni element stosu
wartosc // Wartość przechowywana w danym elemencie stosu
Class Stos
Top = NULL //Wierzchołek stosu
Push(Wartosc) //dodanie elementu
nowy = new element stosu
nowy.wartosc = Wartosc
nowy.poprzednik = Top
Top = nowy
Pop() //ściągnięcie elementu
wartosc = Top.wartosc
pomocnik = Top
Top = Top.poprzednik
usun(pomocnik) //usuń ściągnięty wierzchołek
return wartosc
Stos znajduje zastosowanie przy obliczaniu wyrażeń zapisanych za pomocą odwrotnej notacji polskiej (RPN). Algorytm wygląda następująco:
Jest wykorzystywany między innymi przez język Forth.
Jedną z implementacji stosu jako struktury danych jest obszar w pamięci wydzielony dla danego wątku, służący do przechowywania adresów powrotu i zmiennych lokalnych. Wielkość stosu jest stała w czasie wykonywania programu, ustalana w czasie kompilacji, stąd zdarza się, że program chce zapisać w nim więcej niż przewidziano. Mówimy wówczas o przepełnieniu stosu.
Obsługa stosu jest zapewniana przez procesor. Jego umiejscowienie i rozmiar są określone przez wartości dwóch rejestrów:
Do obsługi stosu natomiast służą instrukcje:
Powoduje umieszczenie wartości na szczycie stosu. Odpowiada on przesunięciu rejestru ESP o odpowiednią ilość bajtów (w zależności od rozmiaru rejestru, którego wartość przenosimy na stos) w tył i zapisanie w tym miejscu żądanej wartości.
Powoduje zdjęcie wartości ze stosu. Odpowiada on zapisaniu odpowiedniej ilości bajtów (zależącej od rozmiaru rejestru, do którego przenosimy wartość) w rejestrze i przesunięciu ESP o tyleż bajtów do przodu.
Instrukcje wywołania procedury call, przerwań programowych Int oraz sprzętowych odkładają na stosie adres do którego procesor ma powrócić po wykonaniu procedury. Dane te zdejmuje ze stosu instrukcją powrotu z procedury ret.
