Stos (informatyka)

Z Wikipedii, wolnej encyklopedii
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. 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[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<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[edytuj | edytuj kod]

Class 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[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.

W języku JavaScript można używać tablic jak stosu, dzięki metodom tablic push oraz pop.

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.

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]