Struktury danych w JavaScript – Stos. Wersja alternatywna

W ostatnim poście przedstawiłem implementacje klasy, odzwierciedlającej popularna strukturę danych – stos. Teraz przedstawię alternatywną wersję.

Stos

Nie wykorzystuję tutaj javascriptowych metod pop i push tablicy. Zamiast nich wprowadzam nową zmienną top, którą dodaje do klasy Stack. Zmienna ta wskazuje nam na szczyt stosu, a właściwie, na następne „puste” miejsce w tablicy. Użyłem cudzysłowia, ponieważ nie musi być ono naprawdę puste. Ważne, ze stos traktuje je jako wolne. Działa to podobnie do dysku twardego komputera. Nawet jeśli pewne komórki fizycznie zawierają jakieś dane, są oznaczone jako puste, ponieważ je usunięto w systemie. Ok, przejdźmy do implementacji, aby wszystko wyjaśnić. Tym razem od razu przedstawiam cały kod klasy Stack.

Jak w popzedniej implementacji i tutaj konstruktor klasy zawiera pole data, które przechowuje tablice. W tej tablicy będą mieścić się wszelkie elementy dodane do naszego stosu. Oprócz data mamy tu tez pole top. Podczas tworzenia nowej instancji obiektu, top ustawiamy na zero. W tej implementacji, jest to najważniejszy, po tablicy data element klasy.

Spójrzmy na metodę add. Przekazany element, przypisywany jest do tablic data, na pozycji top. W tym samym momencie inkrementujemy top. Należy zwrócić specjalna uwagę na tę inkrementacje. Najpierw zwracamy pole top a dopiero potem inkrementujemy jego wartość. Dzięki temu element jest przypisywany na sama gore stosu, a top „wskazuje” na kolejne miejsce w tablicy.

Kolejna metoda remove również wykorzystuje nasze top. Metoda zwraca i „usuwa” element. Tym razem najpierw dekrementujemy top, a następnie zwracamy to na co wskazuje. Pamiętajcie, ze top wskazuje, na pierwsze wolne miejsce w stosie! Pomimo tego, ze nic nie usuwamy z tablicy data, ten element dla stosu nie jest już widoczny. Następne wywołanie add, nadpisze ten element. Warto poświecić trochę czasu aby dokładnie zrozumieć, co tu się dzieje. Wbrew pozorom nie są to skomplikowane rzeczy.

Spójrzmy na obrazek:

Stack

Najpierw dodajemy do stosu „0”. Top wskazuje na miejsce nad dodanym elementem, zarazem na miejsce, w które wpadnie kolejny element. Następnie dodajemy kolejny element do stosu, „1”. Zajmuje on miejsce, na które wskazuje top. Top natomiast przechodzi o jedno pole w górę. Kolejny krok to wywołanie metody remove. Powoduje, że top spada o jedno miejsce i zwraca element na który wskazuje. Na końcu dodajemy nowy element „0”, który zajmuje miejsce wcześniej wskazywane przez top, nadpisując to co było w tej komórce. Top znów jest inkrementowane i grzecznie wskazuje, nam kolejną wolną przestrzeń.

Mam nadzieję, że powyższy przykład pomoże w zrozumieniu tego mechanizmu. Przejdźmy do opisu dalszych metod:

Metody view i size działają podobnie jak w poprzedniej implementacji. View zwraca nam element który jest najwyżej w tablicy data, czyli o jedno pole przed tym, na które wskazuje top. Size zwraca wartość top, które zawsze będzie równe ilości elementów na stosie.

Reset wygląda trochę inaczej niż w poprzedniej implementacji. Przede wszystkim, metoda ta ustawia wartość top na zero. Właściwie to by wystarczyło, ponieważ wszystkie pola na tablicy data nad tym, na które wskazuje top są traktowane przez stos, tak jakby były puste. Jeśli top jest równe zero, to znaczy, ze pod nim tez nic nie ma. Mamy pusty stos. Jednak dla jasności, ustawiamy również długość tablicy data na zero. To rozwiązanie jest podobne do wcześniejszego.

Na koniec mamy jeszcze metodę isEmpty. Zwraca ona wynik porównania top do zera. Jeśli top będzie równe zero, zwraca ona true, w innym wypadku zwraca false.

I to już cala klasa. Szczerze mówiąc, to rozwiązanie podoba mi się bardziej. Jest bardziej uniwersalne. Zrozumienie go, daje nam konkretne pojecie o działaniu stosu. Poprzednie opierało się na metodach javascriptowych, co tez nie jest złe, ponieważ pozwala z kolei na dobre zrozumienie języka. Sami zdecydujcie, którą implementacje wolicie.

One thought on “Struktury danych w JavaScript – Stos. Wersja alternatywna”

Dodaj komentarz

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