Z Wikipedii

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 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, a także w językach programowania wysokiego poziomu.

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

[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 wierzchołek

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