Co to jest Stos (ang. stack)?

Mentos

Źródło: https://www.flickr.com/photos/hellokitae/4291992600

Jedną z podstawowych struktura danych w informatyce jest stos (ang. stack). Chociaż nie jest on często stosowany w kodzie aplikacji (częściej spotkasz się z listami, setami oraz mapami) to bez niego nie funkcjonowałaby maszyna wirtualna Javy oraz komputery.

Dlaczego? Otóż stos wykorzystywany jest w celu “zlezienia drogi powrotnej” po wykonaniu metody, funkcji czy też instrukcji procesora. W momencie wywołania metody “A” adres aktualnego miejsca w programie jest odkładany na stos wywołania programu, następnie wykonywane są instrukcje z metody “B” (jeżeli w jej ciele odwołujemy się do kolejnej metody (“C”) to odkładamy na stos adres metody “B”, żeby wykonać metodę “C”). Kiedy metoda “B” zostanie wykonana, do końca JVM pobiera adres, do którego ma wrócić ze stosu wykonania… i wraca, zwracając wartość wyliczoną przez metodę “B”. Tak w sporym uproszczeniu można opisać, jak działa JVM.

Innym bardziej “namacalnym” zastosowaniem stosu jest tzw. StackTrace (tzn. stos wywołań) który możesz zobaczyć na ekranie w momencie wystąpienia wyjątku (ang. exception) w programie.

Jak sobie wyobrazić taki stos? Wyobraź sobie (lub po prostu kup) Mentos’a najlepiej “wieloowocowego”. Jest on tak zapakowany, że nie możesz dostać się do dowolnego cukierka. Żeby wsiąść np. czwarty, musisz najpierw wyciągnąć pierwsze trzy. Tak samo nie wiesz też jaki ten czwarty cukierek będzie. Jedyne co możesz zrobić to “zajrzeć”, jaki będzie następny, który będziesz mógł wyciągnąć.

Zostało jeszcze nam zastanowić się nad wkładaniem cukierków. Taka czynność jest bardzo utrudniona w rzeczywistości (raz wciągnięty cukierek ciężko jest włożyć ponownie). Jednak jeżeli użyjemy trochę wyobraźni, to zauważymy, że nie możemy włożyć cukierka na dowolną pozycję, zawsze musimy włożyć go na koniec (początek) “kolejki”.

Tak samo jest ze stosem w programowaniu. Przede wszystkim zachowuje on kolejność, w jakiej zostały do niego włożone elementy, ale pozwala je pobrać w kolejności odwróconej (pierwszy, który został włożony, zostanie pobrany jako ostatni). Czyli zawsze mamy szybki dostęp do elementu, który został włożony jako ostatni. Dodatkowo możemy podejrzeć, jaki będzie następny element możliwy do pobrania.

Przejdźmy teraz do tego, jak w Java używać stosów. JVM dostarcza nam implementację stosu pod postacią sparametryzowanej (lub generycznej) klasy java.util.Stack. Trzy najważniejsze metody pozwalające nam używać stosu to:

  • push(element) – pozwala nam włożyć element na “wierzchołek” stosu,
  • pop() – ta metoda wykonuje tak naprawdę dwie operacje. Po pierwsze “ściąga” (usuwa) ostatni element ze stosu oraz zwraca jego wartość (czyli tak jak by wyciągnąć cukierek z opakowania Mentosów),
  • peek() – pozwala nam podejrzeć ostatni element, jaki znajduje się w stosie. Wywołanie tej metody zwróci ten sam obiekt co pop(), z tym że nie usunie go ze stosu (czyli jest to takie zajrzenie do środka Mentosa, żeby sprawdzić jaki cukierek będzie następny).

Dodatkowo dostępne mamy jeszcze:

  • search(element) – pozwala znaleść dany element w stosie. Zwróci nam “numer” pozycji, na której znajduje się podany obiekt (element) lub wartość -1, gdy ten obiekt nie znajduje się w secie,
  • empty() – pozwala sprawdzić, czy stos jest pusty.

Przykład wykorzystania stosu:

Wynikiem wykonania tego kodu będzie:

W ten oto sposób używa się klasy java.util.Stack. Gdyby coś było jeszcze nie jasne, zapraszam do zadawania pytań w komentarzach.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *