Stos (informatyka)


Stos (informatyka) w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do 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).

Spis treści

Historia | 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 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 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 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 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 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 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 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 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 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 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 kod

Na podstawie artykułu: "Stos (informatyka)" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy