Stack (czyli stos) jest chyba najlepszym wprowadzeniem w świat algorytmów i struktur danych. Jest bardzo prosty w implementacji, dzięki czemu szybko można podłapać o co tak na prawdę chodzi z tymi strukturami 😎.

Stack jest pewną wariacją zwykłej kolekcji (np. tablicy), która działa w dość specyficzny sposób. Elementy, które są do niej dodawane / odejmowane obsługiwane są zgodnie z zasadą Last In First Out (LIFO). Oznacza to, że obiekt dodany do kolekcji jako ostatni będzie jednocześnie pierwszym, który zostanie z niej pobrany jeżeli zajdzie taka potrzeba. Bardzo dobrze ilustruje to poniższy obrazek:

 

Źródło: Link

 

Stack stosowany jest na przykład w stack trace (dosłownie jest to tłumaczone na ślad stosu), czyli strukturze przechowującej listę wywołanych metod w wybranym momencie działania naszej aplikacji. Bardzo przydatne narzędzie do debugowania. Jak nam się apka sypnie to możemy podejrzeć, które wywołania spowodowały powstanie błędu 😉. Stack może się również przydać przy rozwiązywaniu zadania rekrutacyjnego, kiedy będziemy musieli odwrócić kolejność liter w danym słowie. Wystarczy wszystkie literki kolejno wepchnąć na stos, a następnie pobierać je jedna po drugiej. Inne ciekawe zastosowanie to przeglądarka internetowa. Każda odwiedzona przez nas strona jest składowana na stosie (a konkretnie jej adres url). Kiedy będziemy chcieli się cofnąć za pomocą przycisku „wstecz”, to adres ostatnio odwiedzonej strony zostanie pobrany właśnie ze stacka 🤩.

Do działania stos wykorzystuje dwie główne metody – push() oraz pop(). Pierwsza dodaje element na samą górę (koniec struktury), natomiast druga pobiera pierwszą dostępną wartość (czyli tę końca kolekcji). Do tego dochodzą jeszcze:

peek() – możemy sprawdzić co jest na górze stosu bez usuwania elementu.

count() – zwraca ilość elementów znajdujących się w strukturze.

isEmpty() – sprawdza, czy dana struktura jest pusta.

isFull() – bardzo rzadko spotykane – jeżeli na stos zostały nałożone ograniczenia pojemności, to za pomocą tej metody sprawdzimy, czy nasz stack jest już pełny. Mała zagadka – domyślacie się skąd wzięła się nazwa Stack Overflow? 🤔

A teraz konkrety. Tak będzie wyglądała implementacja stosu w Swift:

 

 

W przykładzie, do przechowywania naszych wartości, wykorzystaliśmy klasyczna tablicę, jako że w Swift tablica posiada kilka przydatnych metod, takich jak na przykład popLast(), która pobierze dla nas ostatni obiekt w kolekcji. Implementacja naszego stosu jest generyczna (generic), co oznacza, że będziemy mogli tworzyć struktury dla dowolnych typów (ale w ramach jednej kolekcji muszą być takie same). Oznacza to, że na stos możemy wrzucić Stringi, Int’y, czy też typy, które sami utworzyliśmy.

Tak wygląda przykładowe zastosowanie:

 

 

Musicie przyznać, że stack jest bardzo prostą i elegancką strukturą 😎.

 

Na sam koniec kilka słów o „kosztach” operacji wykonywanych na stosie. Nowe elementy dodawane są na końcu struktury, dzięki czemu nie ma konieczności przestawiania wszystkich wartości w pamięci, tak jak miałoby to miejsce w przypadku dodawania nowego obiektu na początku kolekcji. Koszt dodania nowego elementu wynosi O(1), co oznacza, że jest stały. Koszt dodania elementu na sam początek struktury jest równy O(n), ponieważ każdorazowo konieczna jest iteracja przez całą kolekcję.

Jak sami widzicie stos nie jest niczym skomplikowanym, a może przydać się w codziennych zastosowaniach. W następnym wpisie przyjrzymy się bliżej Linear Search 😏.


 

Dodaj komentarz

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