Chociaż pisanie gier to świetna zabawa i dobry sposób na naukę programowania, to nie samymi grami człowiek żyje. Aby utrwalić wiedzę zdobytą na studiach postanowiłem napisać na blogu serię artykułów. Przedstawię w nich struktury danych w JavaScripcie – stos, to pierwsza opisana struktura. Jest to bardzo popularny, a zarazem prosty system reprezentowania danych. Opiszę na jakich zasadach działa jakie ma możliwości. Oczywiście pokażę też implementacje stosu w JavaScripcie.
Stosy są strukturą danych powszechnie wykorzystywaną w implementacji języków programowania oraz w kompilatorach. Są używane do zarządzania pamięcią lub wywołaniami funkcji. Jest to struktura danych typu LIFO (Last In First Out). Oznacza to, ze usuwamy i dodajemy elementy na tym samym „końcu” stosu. Jako przykład możemy użyć stosu książek. Możemy położyć lub zdjąć książkę tylko ze szczytu stosu. Jeśli jakaś książka jest wewnątrz stosu, nie mamy do niej dostępu, musimy najpierw ściągnąć, te które leżą nad nią. Tak samo działa stos. Proste? No to zabierzmy się za implementacje w JavaScripcie.
Najpierw musimy określić jak chcemy aby nasz stos się zachowywał. Przede wszystkim musimy być w stanie dodawać i usuwać elementy. Potrzebujemy też sposobu na sprawdzenie jaki element znajduje się na szczycie stosu. Przydatne też okażą się możliwości sprawdzenia rozmiaru stosu oraz opróżnienia całości.
Podsumujmy, oto metody, które będziemy potrzebować:
|
1 2 3 4 5 |
dodanie elementu usuniecie elementu wyświetlenie elementu ze szczytu opróżnienie całego stosu sprawdzenie rozmiaru stosu |
Najlepszym rozwiązaniem będzie stworzenie naszego stosu jako obiekt / klasę. To pozwoli nam na łatwe wykorzystywanie go w przyszłości.
|
1 2 3 |
function Stack() { this.data = []; } |
Tak będzie wyglądał konstruktor klasy stosu. Wewnątrz od razu dodałem pole data. Jest to tablica, w której będą przechowywane wszystkie elementy stosu. Tablice w JavaScripcie maja metody, które bardzo pomogą nam w implementacji naszego stosu. Ok zabierzmy się za dodanie metod.
|
1 2 3 |
Stack.prototype.add = function(element) { this.data.push(element); } |
Pierwsza metoda to dodawanie elementów. Nic prostszego używamy JavaScriptowej metody tablicy – push. Doskonale nadaje się do tego zadania. Ta metoda, dodaje przekazany jej element na koniec tablicy. Dokładnie to czego chcemy.
|
1 2 3 |
Stack.prototype.remove = function() { return this.data.pop(); } |
Kolejna metoda, którą dodamy do klasy Stack, odpowiada za usuwanie elementów. Tutaj, również nie dziej się nic nadzwyczajnego. Tak jak w przypadku add korzystamy z wbudowanej do JavaScriptu metody. Tym razem jest to pop. Usuwa ona ostatni element tablicy, w której jest wywołana. W tym przypadku z naszego pola data. Jak widzicie, implementacja stosu w JSie idzie dość gładko 🙂
Następna metoda, będzie zwracać nam element na szczycie stosu. Czyli ostatni element w tablicy data.
|
1 2 3 |
Stack.prototype.view = function() { return this.data[(this.data.length)-1] } |
Ta metoda zwraca nam ostatni element tablicy data. Ponieważ length zwraca nam dokładną ilość elementów tablicy, odejmujemy od tego jeszcze jeden. To dlatego, że elementy tablicy indeksujemy od zera, ale myślę, że to już każdy wie 🙂
|
1 2 3 |
Stack.prototype.reset = function() { this.data = []; } |
Metoda na opróżnienie całego stosu, też daje się zaimplementować bez problemu. Po prostu do tablicy w polu data przypisujemy pusta tablicę.
Gdy to jest gotowe dodajmy kolejną metodę.
|
1 2 3 |
Stack.prototype.size = function() { return this.data.length; } |
Ta metoda zwraca nam ilość elementów na stosie. Używamy do tego właściwości tablicy length.
Na koniec możemy dodać jeszcze jedna metodę. Będzie ona sprawdzała czy stos jest pusty, czy zawiera jakieś elementy.
|
1 2 3 |
Stack.prototype.isPopulated = function() { return this.data.length != 0 } |
Jeżeli tablica w polu data zawiera jakieś elementy, metoda zwraca true, w innym wypadku zwraca false.
I to by było na tyle jeśli chodzi o stos! Zobaczmy jak się spisuje
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
var psy = new Stack; console.log(psy.isPopulated()) //zwraca false psy.add("maja"); //dodajemy element console.log(psy.view()); // wyświetlamy element na szczycie psy.add("milus"); // kolejny element console.log(psy.view()); // znów wyświetlamy console.log("usuwam: "+ psy.remove()); // usuwamy element ze szczytu stosu console.log(psy.view()); // wyświetlamy //dodajemy wiele psów psy.add("dzeki"); psy.add("rambo"); psy.add("misiek"); console.log(psy.view()); // wyświetlamy console.log(psy.size()); // wyświetlamy ilość elementów w stosie psy.reset(); // resetujemy stos console.log(psy.view()); // wyświetlamy - stos pusty wiec undefined console.log(psy.size()); // stos pusty ilość = zero |
Jak widzimy Stackspisuje się bardzo dobrze. Dzięki temu, će zaimplementowaliśmy go jako klasę, jest bardzo łatwo stworzyć wiele odmiennych stosów, z których każdy będzie obsługiwany, przez te same metody.
W następnym poście, zaprezentuje dłuższe programy wykorzystujące naszą klasę Stack. Dzięki tej strukturze danych rozwiążemy parę często spotykanych wyzwań programistycznych 🙂
Hej
Ciekawy wpis. Mam pytanie trochę akademickie, zdefiniowałeś klasę Stack() a później rozszerzejąc jej prototyp dodawałeś nowe metody do niej, jak np.:
Stack.prototype.add = function(element) {
this.data.push(element);
}
A czy było by jakąś różnicą gdyby te metody zdefiniować bezpośrednio w ciele klasy (z założeniem o ile się nie mylę zmiany kontekstu wywołania wewnętrznej funkcji), np.:
function Stack() {
var that = this;
this.data = [];
this.add = function (element) {
that.data.push(element);
};
//tu dodanie kolejnych metod
}
Dzięki 🙂 Jeśli chodzi o Twoje pytanie, zacząłem pisać odpowiedź, ale okazała się tak obszerna, że zrobię tego osobny wpis 🙂 powinien pojawić się na dniach.
W skrócie: przypisywanie bezpośrednio do obiektu powoduje dwie rzeczy. Po pierwsze: obniżenie wydajności (metoda przypisywana jest oddzielnie do każdej instancji). Po drugie, w razie zmiany treści metody, trzeba by było zmienić ją w każdej instancji (vs zmiany tylko w prototypie, z którego dziedziczą).
Więcej szczegółów i jakieś jasne przykłady wrzucę do posta na ten temat 🙂