Stosy to liniowe struktury danych, które działają zgodnie z zasadą LIFO. LIFO oznacza ostatni na pierwszym, co oznacza, że ostatnio dodany element jest pierwszym, który zostanie usunięty. Ta struktura danych nosi nazwę stos jako analogię do stosów ze świata rzeczywistego, np. stos ciasteczek w słoiku z ciasteczkami lub stos książek na półce z książkami. W stosie wkładanie i wyjmowanie może odbywać się tylko na jednym końcu, tj. na górze stosu. Na przykład, jeśli chcemy zjeść ciastko, najpierw dostaniemy pierwsze, a potem drugie i tak dalej.
Ten post będzie dotyczył implementacji stosu w JavaScript. Ponieważ pracujemy z JavaScriptem, nie będziemy się martwić rozmiarem stosu, ponieważ rozmiar obiektów JavaScript może rosnąć dynamicznie.
Implementacja stosu w JavaScript
Do zaimplementowania struktury danych stosu użyjemy klasy JavaScript. The stos klasa będzie zawierać tablicę w swoim konstruktorze, która będzie używana do przechowywania elementów na stosie. Klasa zdefiniuje również różne metody, które będą używane do manipulowania danymi przechowywanymi w stosie. Najbardziej podstawowe metody tablicy to wstawić() oraz wyciąg() metody używane do dodawania i usuwania elementów ze szczytu stosu.
The stos klasa definiuje również inne metody, takie jak zerkać() , jest pusty() , jasne() , wydrukować() oraz rozmiar() również:
stos klas {
konstruktor ( ) {
this.elements = [ ] ;
}
// Umieszcza przedmiot na szczycie stosu
wstawić ( element ) {
to.elementy.push ( element ) ;
}
// Usuwa przedmiot ze szczytu stosu
wyciąg ( ) {
to.elementy.pop ( ) ;
}
// Zwraca najwyższy element stosu
zerkać ( ) {
zwrócić this.elements [ this.elements.length - 1 ] ;
}
// Czeki jeśli stos jest pusty
jest pusty ( ) {
zwrócić this.elements.length == 0 ;
}
// Drukuje cały stos
wydrukować ( ) {
dla ( wynajmować ja = 0 ; i < to.elementy.długość; i++ ) {
konsola.log ( this.elements [ i ] ) ;
}
}
// Zwraca rozmiar stosu
rozmiar ( ) {
zwrócić to.elementy.długość;
}
// czyści stos
jasne ( ) {
this.elements = [ ] ;
}
}
Wypychanie i wybijanie elementów ze stosu
Najbardziej podstawową operacją stosu jest wstawianie i wyciąganie elementów z wierzchu stosu. Klasa stosu udostępnia dwie metody dla tych operacji:
Pierwsza linia powyższego kodu deklaruje nowy stos o nazwie s . A później wstawić() metoda służy do wkładania czterech elementów do stosu, z których dwa są następnie usuwane przez wyciąg() metoda.
Jak zdobyć górny element ze stosu
The stos klasa definiuje zerkać() metoda pobrania górnego elementu ze stosu:
Jak sprawdzić, czy stos jest pusty?
Klasa definiuje również metodę, za pomocą której można sprawdzić, czy stos jest pusty:
Jak wydrukować cały stos?
The wydrukować() można wywołać metodę, aby wydrukować cały stos
Jak sprawdzić wielkość stosu?
The rozmiar() metoda wykorzystuje .długość właściwość, aby uzyskać rozmiar stosu:
Jak wyczyścić cały stos?
Po prostu przywołaj jasne() sposób usunięcia każdego elementu stosu:
Wniosek
Stosy to przydatne struktury danych z wieloma rzeczywistymi aplikacjami, takimi jak historia przeglądarki, przycisk cofania w edytorach tekstu i dzienniki połączeń. Wszystkie te aplikacje działają zgodnie z zasadą LIFO, np. przycisk Wstecz w przeglądarce powoduje powrót do ostatnio odwiedzanej strony, a pierwszy wpis w rejestrze połączeń jest zawsze najnowszym połączeniem.
Implementacja stosu w JavaScript jest naprawdę łatwa, ponieważ ma wbudowaną naciskać oraz Muzyka pop metody dla tablic. Ten artykuł przedstawia proces implementacji stosu w JavaScript.