Kas yra stack'ai?

Eilutė — tai duomenų struktūra, veikianti pagal LIFO (Last-In, First-Out) principą. Elementai pridedami ir pašalinami tik iš vieno galo, vadinamo stovo viršumi.

Pagrindinės operacijos:

• push: pridėti elementą į stovo viršų.
• pop: pašalinti elementą iš stovo viršaus ir grąžinti jį.
• peek: gauti elemento reikšmę stovo viršuje be pašalinimo.
• isEmpty: patikrinti, ar stovas yra tuščias.

Java stovas yra pateiktas Stack klasės, kuri yra Vector subclass:

// Pavyzdys, kaip naudoti Stack
import java.util.Stack;

public class StackExample {

    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();

        stack.push("Pirmas"); // Pridėti elementus
        stack.push("Antras");
        stack.push("Trečias");

        System.out.println("Stovo viršus: " + stack.peek()); // Peržiūrėti viršutinį elementą

        while (!stack.empty()) { // Kol stovas nėra tuščias
            System.out.println("Pašaliname: " + stack.pop()); // Pašalinti elementus
        }
    }
}

Alternatyva ir šiuolaikinėje Java programavime rekomenduojamas būdas — naudoti ArrayDeque kaip stovą, nes jis užtikrina geresį našumą:

// Pavyzdys, kaip naudoti ArrayDeque kaip stovą
import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeStackExample {

    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>(); // Naudojame Deque kaip stovą

        stack.push("Pirmas"); // Pridėti elementus
        stack.push("Antras");
        stack.push("Trečias");

        System.out.println("Stovo viršus: " + stack.peek()); // Peržiūrėti viršutinį elementą

        while (!stack.isEmpty()) { // Kol stovas nėra tuščias
            System.out.println("Pašaliname: " + stack.pop()); // Pašalinti elementus
        }
    }
}

Stovų taikymas:

• Skaičiavimo išraiškų įvertinimas (pavyzdžiui, atvirkštinė polinė notacija).
• Operacijų atšaukimas/atkūrimas redaktoriuose (Ctrl+Z/Ctrl+Y).
• Funkcijų kvietimų valdymas operacinėje sistemoje.
• Rekursiniai algoritmai.
• grafų ir medžių apėjimas (paieška gylio pirmumo būdu).