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 stosu można wyłącznie obejrzeć, aby je ściągnąć, trzeba najpierw po kolei ściągnąć to, co jest nad nimi.

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

1 Podstawowe operacje
2 Implementacja
- 2.1 Tablica statyczna
- 2.2 Lista
3 Przykład – stos i odwrotna notacja polska

[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 elemntow 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

Klasa Stos
    Top = NULL       //Wierzchołek stosu 
    
    Push(Wartosc)    //dodanie elementu 
       nowy = Nowy element stosu 
       nowy.wartosc = Wartosc
       nowy.poprzednik = Top
       Top = nowy 
    Pop()            //sciagniecie elementu
       wartosc = Top.wartosc 
       pomocnik = Top
       Top = Top.poprzednik
       usun(pomocnik) //usun sciagniety wierzcholek

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

NETBSD