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.

Czym są struktury danych?

Zaczynając przygodę z programowaniem, warto zaznajomić się z kilkoma podstawowymi pojęciami, które są uniwersalne dla wszystkich języków programowania. Jednym z takich pojęć jest właśnie struktura danych. Nie ważne czy będziesz programował w pythonie, c, c++, java script, swift czy objective c zawsze spotkasz się z tym pojęciem. Zastosowanie odpowiedniej struktury danych może przyśpieszyć działanie aplikacji (oczywiście zły wybór takowej może ją spowolnić). Każdy język programowania dostarcza kilka podstawowych struktur danych, dodatkowe mogą zostać dostarczone przez zewnętrzne biblioteki.

Więc czym właściwie są te struktury danych? Najprościej mówiąc, jest to sposób, w jaki przechowywane są dane w pamięci komputera. Każdy z tych sposobów ma swoje plusy i minusy, niestety nie można mieć wszystkiego :).

Jak można sobie wyobrazić takie różne struktury danych? Wyobraź sobie 50 książek oraz cztery osoby z różnym podejściem do kolejności ich czytania.

  • Tomek trzyma książki na kupce w kącie pokoju. Każdą nową pozycję po prostu kładzie “gdzieś” losowo na tej właśnie kupce. Kiedy chce przeczytać kolejną książkę, po prostu bierze pierwszą lepszą z brzegu i czyta.
  • Marian, z drugiej story, woli czytać książki takiej kolejności, w jakiej je kupił. Więc trzyma je ułożone równo na półce. Nowe pozycje dokłada zawsze na końcu, a kiedy chce przeczytać kolejną książkę, bierze po prostu tą “najstarszą”. Dodatkowo Marian może szybko sprawdzić jaką książkę przeczyta następną, patrząc na koniec swojej kolejki ;).
  • Ania, podobnie jak Marian trzyma książki równo ułożone na półce, z tym że gdy chce przeczytać kolejną, zgaduje sobie jakąś liczbę od 1 do 50. Potem odlicza ją od prawej strony i wyciąga książkę z tej pozycji.
  • Gosia z kolei czyta książki bazując na rekomendacjach znajomych. Pyta ich o kolejny tytuł do przeczytania, a potem na podstawie tego tytułu odnajduje daną książkę na półce i ją czyta.

Każde z powyższych podejść można zaimplementować z wykorzystaniem prostej tablicy. Niestety przy każdym z nich będziemy musieli się “namęczyć” (tj. napisać dużo wlanego kodu), żeby osiągnąć dany efekt.

Pierwszy problem, jaki napotkamy przy każdej implementacji to to, że tablica ma określny rozmiar, którego w Java nie można zmienić “w locie”. Trzeba najpierw zdeklarować nową tablicę o większym lub mniejszym rozmiarze, a potem przepisać wszystkie elementy (plus lub minus jeden) do nowej tablicy.

  • W przypadku Tomka dodatkowo będziemy musieli losować liczbę po to, żeby wiedzieć, w które miejsce włożyć nową książkę oraz żeby “wiedzieć” jaką książkę przeczytać następną.
  • Jeżeli chodzi o Mariana, to zawsze będziemy przepisywać naszą tablicę książek. Przy każdym dołożeniu nowej książki będziemy musieli zwiększyć jej rozmiar o jeden i dodać na końcu nową pozycję. Natomiast w przypadku wzięcia nowej lektury do czytania, będziemy brać tą z pozycji 0, a potem usuwać ją z tablicy… czyli znowu musimy przepisać całość, tym razem bez pierwszego elementu.
  • Podobnie jest w przypadku Ani, z tym że nie wiemy którą pozycję weźmie ona jako następną, więc nasza operacja przepisania będzie jeszcze bardziej skomplikowana.
  • Natomiast w przypadku Gosi, najlepiej będzie nam mieć drugą tablicę, w której będziemy trzymać tytuły książek w takiej samej kolejności, w jakiej są one w tablicy, która przechowuje “całe” książki… oczywiście w tym przypadku musimy “opiekować” się obiema tablicami oraz pilnować, żeby nie rozjechała się nam kolejność.

Tak jak pisałem wcześniej, wszystko da się zrobić, tylko po co się męczyć… jeżeli wiemy, co chcemy osiągnąć oraz znamy właściwości kilku struktur danych, powyższe problemy rozwiążemy, stosując odpowiedni typ zmiennej w Java (czyli wybierając odpowiedni typ danych). Stosując odpowiednią strukturę danych, nie musimy pisać sami kodu związanego z dodawaniem, usuwaniem oraz pobieraniem elementów. Dodatkowo nie musimy się też martwić o rozmiar danej struktury. Wszystkie te rzeczy zrobione są za nas przez innych programistów. Dodatkowo są one przetestowane oraz zaimplementowane w najbardziej wydajny sposób.

Korzystając ze struktur danych dostępnych w Java, biblioteczki naszych poszczególnych bohaterów można zaimplementować używając:

  • java.util.HashSet – korzystamy tutaj ze struktury danych znanej jako set, która to jest takim workiem, do którego można bardzo szybko coś włożyć, oraz szybko wyciągnąć losowy element. Jeżeli nie obchodzi nas kolejność elementów oraz nigdy nie będziemy chcieli pobrać konkretnego elementu jest to idealna struktura danych.
  • java.util.Stack – czyli stos. Jego podstawowymi właściwościami jest to, że dodawane elementy zawsze lądują na końcu oraz to, umożliwia on łatwy (szybki) dostęp do najstarszego elementu (tego, który został umieszczony tam jako pierwszy) oraz można podejrzeć (bez pobierania/ściągania ze stosu) element, jaki jest na samej górze (tj. najstarszy włożony).
  • java.util.ArrayList – struktura danych, z jakiej korzystamy tutaj to lista. Umożliwia ona szybki dostęp do dowolnego elementu po jego liczbie porządkowej. Porządek w liście trzymany jest według kolejności wkładania elementów tj. kolejne elementy dodawane są na końcu listy.
  • java.util.HashMap – czyli mapa… umożliwia ona mapowanie (łączenie) dowolnego elementu w formie klucz-wartość. W przypadku Gosi kluczem będzie tytuł książki (typ String), a wartością obiekt samej książki.

Reasumując, czym są struktury danych? Jest to sposób, w jaki dane przechowywane są w pamięci komputera, oraz algorytmy umożliwiające wykonywanie operacji takich jak dodawanie, usuwanie oraz pobieranie elementów w najbardziej wydajny sposób. Zastosowanie odpowiedniej struktury danych może przyśpieszyć działanie aplikacji oraz zmniejszy ilość kodu, jaki musimy napisać w celu osiągnięcia działania aplikacji. Biblioteka standardowa Java zawiera wiele różnych struktur danych, jako dobry programista powinieneś znać je wszystkie plus dodatkowo kilka dostarczanych przez zewnętrzne biblioteki jak na przykład Google Guava.