Java Stack: Dátová štruktúra a trieda Stack (zásobník) v Jave

Java Stack je jedna z množstva dátových štruktúr (kolekcií) na jednoduchšiu manipuláciu s dátami. V rámci nášho seriálu o dátových štruktúrach si predstavíme jednotlivé štruktúry, ukážeme si ich použitie, dostupné metódy, výhody a nevýhody, a poskytneme tipy, kedy je vhodné ich použiť.

V tejto časti sa budeme venovať kolekcii, ktorá reprezentuje zásobník  – Java Stack.

Java Stack – predstavenie dátovej štruktúry

Kolekcia Stack je implementovaná ako trieda v balíku java.util. Ide o potomka triedy Vector, od ktorej preberá jej vlastnosti a zároveň pridáva funkcie špecifické pre zásobníkový prístup k dátam.

Trieda Stack inkorporuje princíp LIFO (Last In, First Out), čo znamená, že posledný pridaný prvok je zároveň prvým, ktorý je zo zásobníka odstránený. Tento algoritmus je vhodný v situáciách, keď potrebujeme dodržiavať poradie operácií (napríklad pri výpočte výrazov či implementácii rekurzie) a funguje v konštantnom čase.

Typickým príkladom použitia Stacku je Stack trace pri debugovaní kódu. Posledná navštívená metóda je pridaná ako posledná na vrch zásobníka a keď ju opustíme, tak sa z neho odstráni a navrchu zásobníka sa ocitne metóda, ktorá volala predchádzajúcu.

Aj keď je Stack založený na triede Vector a zdedil jej dynamické správanie (automatické zväčšovanie kapacity), ide o štruktúru, ktorá je v súčasnosti v moderných aplikáciách menej používaná, pretože rozhranie Deque a jej implementácie ako je napríklad ArrayDeque z java.util dokáže svojou implementáciou LIFO prístupu a kompletným a konzistentným súborom operácií Stack úplne nahradiť.

Konštruktor triedy Stack

Trieda Stack poskytuje jediný jednoduchý konštruktor, ktorý vytvorí prázdny zásobník. Kapacita zásobníka je na počiatku nastavená na fixnú hodnotu 10 a podobne ako pri vektore sa pri presiahnutí celkovej veľkosti zásobníka zväčší na dvojnásobok. Rozdiel oproti vektoru je ten, že po odstránení prvkov zo zásobníka sa nikdy nezmenší.

Prázdny zásobník

Vytvorí prázdny zásobník s kapacitou 10 (default hodnota).

Základné operácie s kolekciou Stack

Medzi základné operácie s kolekciou Stack patria:

Vkladanie prvkov (push)

Pridá nový prvok na vrchol zásobníka.

Odstránenie prvku (pop)

Odstráni a vráti vrchný prvok. Ak je táto operácia volaná na prázdnom zásobníku, vyhodí výnimku EmptyStackException.

Pohľad na vrchný prvok (peek)

Vráti vrchný prvok bez jeho odstránenia.

Kontrola, či je zásobník prázdny (empty)

Vráti true, ak zásobník neobsahuje žiadne prvky, inak false.

Hľadanie prvku (search)

Vyhľadá prvok a vráti jeho vzdialenosť od vrchu zásobníka. Vzdialenosť najvrchnejšieho elementu je 1. Toho pod ním 2 atď. Ak sa prvok nenachádza, vráti hodnotu -1.

Java Stack: Príklady základných operácií

Pridávanie elementov

Pridávanie prvkov do stacku môžeme robiť po jednom prvku alebo hromadne.

Pridanie jedného prvku

stack.push(1);

Pridanie viacerých prvkov naraz

List<Integer> values = Arrays.asList(2, 3, 4, 5);
stack.addAll(values);

Pohľad na vrchný prvok

Ak sa chceme pozrieť, ktorý prvok je aktuálne na vrchu zásobníku použijeme metódu peek().

Informácia o vrchnom prvku

stack.peek();

V našom príklade vráti hodnotu 5.

Kontrola prázdnosti zásobníka

Ak sa nás zaujíma, či zásobník obsahuje vôbec nejaké prvky, tak môžeme zavolať metódu empty().

stack.empty();

V našom príklade vráti hodnotu false, keďže obsahuje prvky.

Vyhľadávanie prvkov

Ak chceme zistiť, či zásobník obsahuje konkrétny prvok X, tak môžeme zavolať metódu search(X).

stack.search(X);

stack.search(7) => vráti -1

stack.search(2) => vráti 4

Odstránenie prvkov

Najčastejšie potrebujeme odstrániť vrchný prvok zásobníka – to spravíme zavolaním metódy pop(). Operácie z triedy Vector nám však ponúkajú aj iné možnosti.

Odstránenie a vrátenie vrchného prvku

V našom príklade odstráni vrchný prvok zo zásobníka (5) a uloží do premennej element. Na vrchu zásobníka sa bude nachádzať aktuálne prvok 4.

Integer element = stack.pop();

Vyprázdnenie zásobníka

Na vymazanie všetkých prvkov zásobníka existujú dve ekvivalentné metódy: clear(), removeAllElements().

stack.removeAllElements();
stack.clear();

Ostatné operácie

Spomeniem ešte niekoľko ďalších užitočných metód.

Odstránenie prvkov pomocou filtra (lambda výrazu)

stack.removeIf(elem -> elem < 2);

Zistenie počtu prvkov v zásobníku

int size = stack.size();

Index výskytu daného prvku najbližšie k vrcholu zásobníka

stack.lastIndexOf(3);

Dokumentácia metód pre kolekciu Stack

Kompletný prehľad všetkých prístupných metód pre Stack nájdeš tu – dokumentácia Stack.

Výhody a nevýhody dátovej štruktúry Stack

Výhody Stack-u:

• Jednoduchá implementácia LIFO princípu.
• Synchronizácia umožňuje použitie vo viacvláknovom prostredí.
• Odvodenie z triedy Vector pridáva zásobníku dynamické správanie a ďalšie metódy na manipuláciu s dátami.

Nevýhody Stack-u:

• Nízka výkonnosť v porovnaní s modernými dátovými štruktúrami ako ArrayDeque.
• Synchronizácia môže byť zbytočná a neefektívna v aplikáciách, kde nie je požadovaná.
• V modernej Jave používaná zriedkakedy.

Kedy využiť Stack v Jave?

Použitie kolekcie Stack je vhodné v situáciách, kde je potrebné implementovať algoritmy založené na LIFO princípe napr. pri prechádzaní grafov, spätnom sledovaní (backtracking), dá sa využiť v textových editoroch na implementovanie undo a redo operácií, manažovanie histórie webového prehliadača a pri navigácii naspäť/dopredu atď.

Dá sa využiť aj ako synchronizovaná kolekcia vo viacvláknovej aplikácii, kde viaceré vlákna pracujú s tým istým zásobníkom, alebo využiť v starších aplikáciách, ktoré využívajúc synchronizované dátové štruktúry, ale ešte fungujú na zastaralej verzii Java.

Príklad použitia zásobníka Stack v Java programe

Keď už poznáme základné metódy pre kolekciu Stack, môžeme sa s nimi trochu pohrať v nasledovnom programe, ktorý ukazuje použitie zásobníka na vyhodnotenie výrazov pomocou reverznej poľskej notácie (RPN).

Main.java

import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String[] expression = {"2", "3", "+", "4", "*"};
        evaluateRPN(expression);
    }

    public static void evaluateRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        System.out.println("Je zasobnik prazdny? " + stack.empty());
        System.out.println("Vypocet RPN pre vyraz: " + Arrays.toString(tokens));

        for (String token : tokens) {
            if ("+-*/".contains(token)) {
                System.out.println("Vrchny prvok (peek): " + stack.peek());
                int b = stack.pop();
                System.out.println("Odstraneny pravy operand (pop): " + b);

                int a = stack.pop();
                System.out.println("Odstraneny lavy operand (pop): " + a);
                System.out.println("Operacia: " + token);
                switch (token) {
                    case "+" -> stack.push(a + b);
                    case "-" -> stack.push(a - b);
                    case "*" -> stack.push(a * b);
                    case "/" -> stack.push(a / b);
                }

                int topValue = stack.peek();
                System.out.println("Pridany vysledok (push): " + topValue);
            } else {
                stack.push(Integer.parseInt(token));
                System.out.println("Pridany prvok (push): " + token + " -> " + stack);
            }
        }

        System.out.println("Je zasobnik prazdny? " + stack.empty());
        System.out.println("Hladanie (vzdialenosti) prvku 10 (search): " + stack.search(10));
        System.out.println("Hladanie (vzdialenosti) prvku 20 (search): " + stack.search(20));
        System.out.println("Konecny vysledok (pop): " + stack.pop());
        System.out.println("Je zasobnik prazdny? " + stack.empty());
    }
}

Výstup z tohto príkladu je:

Pripravili sme pre teba súbory so spomínaným príkladom vo forme kódu, ktorý si môžeš spustiť priamo v Jave:

Stiahni si príklad kódu Stack v Jave.

O autorovi

Jozef Wagner

Java Developer Senior

Viac ako 10 rokov programujem v Jave, momentálne pracujem v msg life Slovakia ako Java programátor senior a pomáham zákazníkom implementovať ich požiadavky do poistného softvéru Life Factory. Vo voľnom čase si rád oddýchnem v lese, prípadne si zahrám nejakú dobrú počítačovú hru.