Algoritmai ir duomenų struktūros

Dėklas (angl. stack) yra struktūrinis duomenų tipas, kuris pagrįstas principu „paskutinis atėjo – pirmas išėjo“ (angl. Last-In-First-Out, LIFO). Tai reiškia, kad elementas, įdėtas į dėklą paskutinis, bus pašalintas pirmas. Ši duomenų struktūra naudojama įvairiose situacijose, kai svarbu tvarkyti duomenis arba atlikti operacijas tokiu būdu, kad paskutinis pridėtas elementas būtų pirmas pasiektas.

Java kalboje dėklas įgyvendinamas naudojant Stack klasę, kuri yra Java kolekcijų karkaso (angl. Java Collections Framework) dalis. Stack klasė paveldi Vector klasę, todėl jos elementai saugomi tvarkingai ir prie jų galima prieiti pagal indeksus.

1. Dėklo operacijos

Java Stack klasė siūlo keletą pagrindinių metodų, kurie leidžia valdyti dėklo struktūrą:

• push(E item): Įdeda elementą į dėklo viršų.
• pop(): Pašalina ir grąžina elementą iš dėklo viršaus. Jei dėklas tuščias, metodas sukelia EmptyStackException išimtį.
• peek(): Grąžina elementą iš dėklo viršaus, bet jo nepašalina. Jei dėklas tuščias, metodas sukelia EmptyStackException išimtį.
• isEmpty(): Patikrina, ar dėklas yra tuščias, grąžina true, jei taip, arba false, jei ne.
• search(Object o): Grąžina elemento poziciją dėkle (LIFO tvarka), skaičiuojant nuo viršaus. Jei elementas nerandamas, grąžina -1.

2. Dėklo veikimo principas

Dėklo struktūra veikia LIFO principu, todėl nauji elementai dedami į viršų ir pašalinami iš viršaus. Tai leidžia greitai prieiti prie naujausio elemento, tačiau pasiekti bet kurį kitą elementą yra sudėtinga. Dėklas naudoja šias pagrindines operacijas:

1. Įdėjimas į dėklą (push): Naujas elementas įdedamas į viršų. Tai efektyvi O(1) operacija.
2. Pašalinimas iš dėklo (pop): Elementas pašalinamas iš viršaus ir grąžinamas. Tai taip pat yra O(1) operacija.
3. Prieiga prie viršutinio elemento (peek): Galima pasiekti viršutinį elementą jo nepašalinant, ir tai yra taip pat O(1) operacija.

3. Dėklo sukūrimas ir naudojimas Java kalboje

Kodas, demonstruojantis dėklo sukūrimą ir naudojimą Java kalboje:

import java.util.Stack;

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

        // Įdėjimas į dėklą
        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Viršutinis elementas: " + stack.peek());  // Grąžina 30

        // Pašalinimas iš dėklo
        System.out.println("Pašalintas elementas: " + stack.pop());  // Pašalina ir grąžina 30
        System.out.println("Viršutinis elementas po pašalinimo: " + stack.peek());  // Grąžina 20

        // Patikrinimas, ar dėklas tuščias
        System.out.println("Ar dėklas tuščias? " + stack.isEmpty());
    }
}

4. Dėklo panaudojimo atvejai

Dėklas yra naudinga struktūra įvairiose situacijose, kai reikia laikytis LIFO principo. Štai keli dažni dėklo naudojimo atvejai:

Funkcijų iškvietimų valdymas ir rekursija

• Rekursija: Kai naudojama rekursija, sistemos dėklas laiko kiekvieną rekursyvų iškvietimą kaip naują įrašą dėkle. Grįžtant atgal, funkcijos iškeliamos iš dėklo viena po kitos LIFO tvarka, o tai leidžia korektiškai užbaigti rekursyvų veiksmą.
• Programos vykdymo seka: Dėklas naudojamas valdyti funkcijų iškvietimų seką, leidžiant tvarkingai grįžti į ankstesnes funkcijas.

Atgalinės naršymo funkcijos (Undo / Redo)

• Tekstų redaktoriai: Redaktoriai, tokie kaip Word ar Notepad, naudoja dėklus, kad išsaugotų ankstesnes naudotojo veiklas. „Undo“ funkcija pašalina naujausią veiksmą, o tai yra natūrali LIFO funkcija.
• Naršyklės istorija: Naršyklės naudoja du dėklus, kad leistų naršyti pirmyn ir atgal tarp apsilankytų puslapių.

Matematinės išraiškos ir operacijos

• Išraiškų analizė: Dėklas yra naudojamas matematinėms ir loginėms išraiškoms vertinti. Pavyzdžiui, dėklas naudojamas išraiškoms konvertuoti iš infiksinės (pvz., 2 + 3) į postfiksinę formą (pvz., 2 3 +).
• Sintaksės patikrinimas: Dėklas gali būti naudojamas tikrinti skliaustų sintaksės korektiškumą. Įvedant skliaustų poras, kiekvienas atidaromas skliaustas dedamas į dėklą, o uždaromas skliaustas pašalinamas tik tada, kai jis atitinka paskutinį atidarytą skliaustą.

Darbas su duomenų struktūromis, pvz., medžiais ir grafais

• Medžių peržvalga: Dėklas naudojamas peržvelgti dviejų vaikų (dvejetainius) medžius, pvz., atliekant paiešką į gylį (angl. Depth-First Search, DFS).
• Grįžimas atgal grafuose: Dėklas padeda naršyti grafus, nes jį galima naudoti kaip struktūrą atliekant paiešką į gylį (DFS).

5. Dėklo privalumai ir trūkumai

Privalumai:

• LIFO operacijos: Dėklas leidžia lengvai pasiekti ir valdyti paskutinį pridėtą elementą, todėl puikiai tinka operacijoms, kai reikia tokios tvarkos.
• Greitos operacijos: Dėl savo struktūros dėklas užtikrina greitą elementų įterpimą ir pašalinimą (O(1) laiko sudėtingumas).
• Naudinga rekursijos valdymui: Dėklas yra puikus būdas valdyti rekursyvias funkcijas, kadangi jis palaiko tinkamą iškvietimų seką.

Trūkumai:

• Ribota prieiga: Galima pasiekti tik viršutinį elementą, todėl jei reikia prieiti prie kitų elementų, tai tampa sudėtinga.
• Klasės apribojimai: Stack klasė paveldi Vector klasę, todėl yra laikoma senesnio tipo struktūra Java kolekcijų karkase. Java rekomenduoja naudoti Deque sąsają (ArrayDeque klasę), kai reikia lankstesnės ir greitesnės dėklo versijos.
• Neefektyvus didelių duomenų valdymas: Kai dėkle yra labai daug duomenų, gali prireikti daugiau atminties ir laiko valdyti dėklo elementus.

6. Alternatyvos dėklui Java kalboje

Nors Stack klasė yra oficialus Java dėklo įgyvendinimas, daugelis programuotojų naudoja ArrayDeque kaip efektyvesnę alternatyvą:

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // Įdėjimas į dėklą
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Pašalinimas iš dėklo
        System.out.println("Pašalintas elementas: " + stack.pop());  // Pašalina ir grąžina 30
        System.out.println("Viršutinis elementas: " + stack.peek()); // Grąžina 20 (nepašalina)
    }
}

ArrayDeque siūlo greitesnį našumą, nes ji nėra sinchronizuota, kaip yra Stack klasės atveju.