Stos (informatyka)
Z Wikipedii
Stos (ang. LIFO, Last In First Out; ostatni na wejściu, pierwszy na wyjściu) – liniowa struktura danych, w której dane dokładane są na wierzch stosu i z wierzchołka stosu są pobierane. 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 LIFO 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.
[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] 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.
