Stos (informatyka)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Idea stosu

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[edytuj | edytuj kod]

Stos został wymyślony i opracowany przez niemieckiego naukowca informatyka Friedricha L. Baura 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[edytuj | edytuj kod]

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.

Implementacja[edytuj | edytuj kod]

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).

Tablica statyczna[edytuj | edytuj kod]

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];
        };
     };

Lista[edytuj | edytuj kod]

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

Przykład – stos i odwrotna notacja polska[edytuj | edytuj kod]

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.

Stos procesora[edytuj | edytuj kod]

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 przez procesory x86[edytuj | edytuj kod]

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:

push[edytuj | edytuj kod]

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.

pop[edytuj | edytuj kod]

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 używające stosu[edytuj | edytuj kod]

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.

Linki zewnętrzne[edytuj | edytuj kod]

WiktionaryPl nodesc.svg
Zobacz hasło stos w Wikisłowniku