Stos (informatyka)
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 używany w systemach komputerowych na wszystkich poziomach funkcjonowania systemów informatycznych. Stosowany 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).
Historia
edytujStos został wymyślony i opracowany przez niemieckiego naukowca informatyka Friedricha L. Bauera w 1955 roku, a opatentowany w 1957. Za ten wynalazek Friedrich L. Bauer dostał w 1988 roku od IEEE nagrodę Computer Society Pioneer Award.
Podstawowe operacje
edytujW powyższym opisie pojawiły się pewne operacje, jakie można wykonywać na stosie. Oto ich formalny zapis:
- push(obiekt) – czyli odłożenie obiektu na stos;
- pop() – ściągnięcie obiektu ze stosu i zwrócenie jego wartości;
- isEmpty() – sprawdzenie czy na stosie znajdują się już jakieś obiekty.
Implementacja
edytujStrukturami 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).
Tablica statyczna
edytujclass Stos<E> {
Object[] tablica; //tablica elementow stosu
licznik = 0;
public Stos(int rozmiar) {
this.tablica = new Object[rozmiar]; // tworzenie tablicy na elementy
}
public void poloz(E wartosc) {
this.tablica[licznik] = wartosc;
this.licznik = this.licznik + 1;
};
public E sciagnij() {
this.licznik = this.licznik - 1;
return (E) this.tablica[this.licznik];
};
};
Lista
edytujClass Element_stosu poprzednik // Wskaźnik 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) // usunięcie ściągniętego wierzchołka return wartosc
Przykład – stos i odwrotna notacja polska
edytujStos znajduje zastosowanie przy obliczaniu wyrażeń zapisanych za pomocą odwrotnej notacji polskiej (RPN). Algorytm wygląda następująco:
- Wyzeruj stos.
- Dla wszystkich symboli z wyrażenia RPN wykonuj:
- jeśli i-ty symbol jest liczbą, to odłóż go na stos,
- jeśli i-ty symbol jest operatorem to:
- zdejmij ze stosu jeden element (ozn. a),
- zdejmij ze stosu kolejny element (ozn. b),
- odłóż na stos wartość b operator a.
- Zdejmij ze stosu wynik.
Jest wykorzystywany między innymi przez język Forth.
W języku JavaScript można używać tablic jak stosu, dzięki metodom tablic push oraz pop.
Stos procesora
edytujJedną 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 przez procesory x86
edytujObsługa stosu jest zapewniana przez procesor. Jego umiejscowienie i rozmiar są określone przez wartości dwóch rejestrów:
- SS – rejestr segmentowy, wskazujący na początek stosu, czyli krańcową wartość, jaką może przyjąć ESP.
- ESP (SP w architekturze 16-bitowej) – rejestr wskazujący na element znajdujący się na szczycie stosu.
Do obsługi stosu natomiast służą instrukcje:
push
edytujPowoduje 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.
pop
edytujPowoduje 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 używające stosu
edytujInstrukcje 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.
Zobacz też
edytujLinki zewnętrzne
edytuj- Więcej informacji na temat programowania stosu na stronie poświęconej assemblerowi dla systemu Linux.. rudy.mif.pg.gda.pl. [zarchiwizowane z tego adresu (2009-09-29)].
- Link do wersji dla systemu DOS. rudy.mif.pg.gda.pl. [zarchiwizowane z tego adresu (2008-12-07)].