Abstrakcyjne struktury danych: Stos
Tworząc oprogramowanie czasami zapisywanie poszczególnych danych do zwykłych zmiennych, tablicy bądź plików po prostu przestaje wystarczać bądź jest całkowicie nie efektywne. W takich przypadkach na pomoc programiście przychodzi programowanie zorientowane obiektowo i abstrakcyjne struktury danych. W tym artykule zajmiemy się stosem (ang. stack).
Spis treści:
Stos to jedna z najprostszych do zrozumienia abstrakcyjnych struktur danych. Całą ideę jego funkcjonowania można opisać powołując się na prosty przykład ze stosem talerzy. Załóżmy, że mamy kilka talerzy i układamy je jeden na drugim tworząc swego rodzaju stos. Talerz (element), który położyliśmy jako ostatni będziemy ściągać jako pierwszy ponieważ znajduje się on na samej górze. Nie możemy wyciągać żadnych talerzy (elementów) ze środka, ani z dołu ponieważ mogło by to grozić rozbiciem pozostałych. Zasada jest więc bardzo prosta: ostatni talerz (element) jaki został odłożony, ściągamy jako pierwszy.
Jak nie trudno się domyślić na stos możemy odłożyć nieskończenie wiele talerzy (elementów) co jest jedną z kluczowych zalet tej struktury danych. Załóżmy bowiem, że mamy do czynienia z jakimiś danymi, ale w momencie pisania kodu nie wiemy ile ich ostatecznie będzie, wobec czego nie możemy do ich przechowywania zastosować tablicy.
Jeśli chodzi o kwestię techniczną to oczywiście talerze zastępujemy jakimś obiektem (zmienną), który oprócz przechowywanej wartości musi zawierać wskaźnik na element poprzedni czyli talerz odłożony wcześniej oraz element następny czyli talerz położony później. Do prawidłowego funkcjonowania stosu potrzebujemy jeszcze wiedzieć czy zawiera on jakieś elementy czyli czy nie jest pusty oraz znać element ostatnio położony – ten, który jest najwyżej.
Zalety i wady stosowania stosu:
| ZALETY | WADY |
|
|
Uzbrojeni w teorię zabierzmy się więc za implementację prostego stosu w Javie. Na samym początku oczywiście musimy sobie stworzyć szkielet naszego programu:
public class Main {
public static void main(String[] args) {
}
}Powyższego kodu chyba nie trzeba nikomu tłumaczyć, można go wygenerować bezpośrednio w dobrym IDE do Java.
