Stos (informatyka)
Z Wikipedii
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 stosu 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żywane są 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 |
[edytuj] Historia
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
[edytuj] Podstawowe operacje
W 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.
[edytuj] Implementacja
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).
[edytuj] Tablica statyczna
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];
};
[edytuj] Lista
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
[edytuj] Przykład – stos i odwrotna notacja polska
Stos 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.
[edytuj] Stos procesora
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.
[edytuj] Obsługa stosu przez procesory x86
Obsł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:
[edytuj] push
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.
[edytuj] pop
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.
