Zásobníky sú lineárne dátové štruktúry, ktoré sa riadia princípom LIFO. LIFO znamená posledný dnu, prvý von, čo znamená, že posledná pridaná položka je prvá, ktorá sa odstráni. Táto dátová štruktúra je pomenovaná zásobník ako analógia k zásobníkom zo skutočného sveta, napr. stoh sušienok v nádobe na sušienky alebo stoh kníh na poličke. Vkladanie a vyberanie stohu sa môže vykonávať iba na jednom konci, t. j. na vrchu stohu. Napríklad, ak chceme zjesť koláčik, dáme si najskôr vrchný a potom druhý a tak ďalej.
Tento príspevok bude celý o implementácii zásobníka v JavaScripte. Keďže pracujeme s JavaScriptom, nebudeme sa obávať veľkosti zásobníka, pretože veľkosť objektov JavaScriptu môže dynamicky rásť.
Implementácia Stack v JavaScripte
Na implementáciu dátovej štruktúry zásobníka použijeme triedu JavaScript. The stoh trieda bude vo svojom konštruktore obsahovať pole, ktoré sa použije na ukladanie prvkov do zásobníka. Trieda bude tiež definovať rôzne metódy, ktoré sa použijú na manipuláciu s údajmi uloženými v zásobníku. Najzákladnejšie metódy poľa sú vložiť() a extrakt() metódy, ktoré sa používajú na pridávanie a odstraňovanie prvkov z hornej časti zásobníka.
The stoh triedy definuje aj ďalšie metódy ako napr nahliadnuť () , je prázdny() , jasný() , tlačiť () a veľkosť () tiež:
zásobník triedy {
konštruktér ( ) {
toto.prvky = [ ] ;
}
// Umiestňuje položku na vrch stohu
vložiť ( prvok ) {
toto.prvky.tlačia ( prvok ) ;
}
// Odstráni položku z hornej časti stohu
extrakt ( ) {
toto.prvky.pop ( ) ;
}
// Vráti najvyšší prvok zásobníka
nahliadnuť ( ) {
vrátiť toto.prvky [ this.elements.length - 1 ] ;
}
// Kontroly ak zásobník je prázdny
je prázdny ( ) {
vrátiť dĺžka týchto.prvkov == 0 ;
}
// Vytlačí celý stoh
vytlačiť ( ) {
pre ( nech i = 0 ; i < táto.dĺžka.prvkov; i++ ) {
konzola.log ( toto.prvky [ i ] ) ;
}
}
// Vráti veľkosť zo zásobníka
veľkosť ( ) {
vrátiť táto.dĺžka.prvkov;
}
// vymaže zásobník
jasný ( ) {
toto.prvky = [ ] ;
}
}
Tlačenie a vyskakovanie prvkov zo zásobníka
Najzákladnejšou operáciou stohu je vkladanie a vyberanie prvkov z vrchu stohu. Trieda zásobníka poskytuje dve metódy pre tieto operácie:
Prvý riadok vyššie uvedeného kódu deklaruje nový zásobník s názvom s . Potom vložiť() metóda sa používa na vloženie štyroch prvkov do stohu, z ktorých dva sú potom odstránené pomocou extrakt() metóda.
Ako získať horný prvok zo zásobníka
The stoh trieda definuje nahliadnuť () metóda na získanie horného prvku zo zásobníka:
Ako skontrolovať, či je zásobník prázdny?
Trieda tiež definuje metódu, ktorú možno použiť na kontrolu, či je zásobník prázdny:
Ako vytlačiť celý stoh?
The tlačiť () metódu možno zavolať na tlač celého stohu
Ako skontrolovať veľkosť zásobníka?
The veľkosť () metóda využíva .dĺžka vlastnosť na získanie veľkosti zásobníka:
Ako vyčistiť celý zásobník?
Jednoducho vyvolajte jasný() metóda na odstránenie každého prvku zásobníka:
Záver
Zásobníky sú užitočné dátové štruktúry s mnohými aplikáciami v reálnom svete, ako je história prehliadača, tlačidlo Späť v textových editoroch a protokoly hovorov. Všetky tieto aplikácie sa riadia princípom LIFO, napr. tlačidlom Späť v prehliadači sa vrátite na poslednú navštívenú stránku a prvý záznam v denníku hovorov je vždy posledný hovor.
Implementácia zásobníka v JavaScripte je skutočne jednoduchá, pretože má vstavaný TLAČIŤ a pop metódy pre polia. Tento článok demonštruje proces implementácie zásobníka v JavaScripte.