Algoritmai ir duomenų struktūros

Dvipusė eilė (angl. double ended queue, arba deque) yra struktūrinis duomenų tipas, leidžiantis pridėti ir pašalinti elementus iš abiejų jos galų, tiek iš pradžios, tiek iš galo. Dėl šios savybės dvipusė eilė yra lankstesnė už įprastą eilę (queue), kurioje duomenys paprastai tvarkomi tik pagal FIFO (pirmas atėjo – pirmas išėjo) principą, arba už steką (stack), kur veikia LIFO (paskutinis atėjo – pirmas išėjo) principas.

Java kalboje dvipusė eilė įgyvendinama per Deque sąsają, kuri yra Java kolekcijų karkaso (angl. Java Collections Framework) dalis. Deque siūlo metodus, leidžiančius atlikti įterpimo ir pašalinimo operacijas tiek iš priekio, tiek iš galo, todėl ji gali būti naudojama kaip eilė, kaip dėklas arba kaip jų derinys.

1. Deque sąsajos pagrindinės savybės

Deque sąsaja turi kelias pagrindines savybes:

• Pridėjimas ir pašalinimas iš abiejų galų: Deque leidžia pridėti elementus tiek į priekį, tiek į galą, taip pat leidžia juos pašalinti iš bet kurios pusės.
• Naudojimas kaip eilė arba dėklas: Deque gali veikti tiek kaip FIFO eilė (su pridėjimu viename gale ir pašalinimu kitame), tiek kaip LIFO dėklas (su pridėjimu ir pašalinimu iš to paties galo).
• Tvarkos išlaikymas: Skirtingai nuo aibės (angl. Set), dvipusė eilė išlaiko elementų tvarką, todėl galima tiksliai kontroliuoti, kur įterpti ir iš kur pašalinti elementus.

2. Deque sąsajos pagrindiniai metodai

Java Deque sąsaja apima metodus, kurie leidžia atlikti įprastas operacijas su dvipusėmis eilėmis. Šie metodai yra suskirstyti į keturias pagrindines grupes pagal veiksmą ir jų atlikimo vietą:

Pridėjimas į dvipusę eilę

• addFirst(E e): Prideda elementą į pradžią. Jei eilė pilna, sukelia išimtį.
• addLast(E e): Prideda elementą į galą. Jei eilė pilna, sukelia išimtį.
• offerFirst(E e): Prideda elementą į pradžią. Jei eilė pilna, grąžina false, o jei pridėjimas sėkmingas – true.
• offerLast(E e): Prideda elementą į galą. Jei eilė pilna, grąžina false, o jei pridėjimas sėkmingas – true.

Pašalinimas iš dvipusės eilės

• removeFirst(): Pašalina ir grąžina elementą iš pradžios. Jei eilė tuščia, sukelia išimtį.
• removeLast(): Pašalina ir grąžina elementą iš galo. Jei eilė tuščia, sukelia išimtį.
• pollFirst(): Pašalina ir grąžina elementą iš pradžios. Jei eilė tuščia, grąžina null.
• pollLast(): Pašalina ir grąžina elementą iš galo. Jei eilė tuščia, grąžina null.

Prieiga prie dvipusės eilės elementų

• getFirst(): Grąžina elementą iš pradžios, jo nepašalindamas. Jei eilė tuščia, sukelia išimtį.
• getLast(): Grąžina elementą iš galo, jo nepašalindamas. Jei eilė tuščia, sukelia išimtį.
• peekFirst(): Grąžina elementą iš pradžios, jo nepašalindamas. Jei eilė tuščia, grąžina null.
• peekLast(): Grąžina elementą iš galo, jo nepašalindamas. Jei eilė tuščia, grąžina null.

Kiti metodai

• isEmpty(): Patikrina, ar dvipusė eilė yra tuščia.
• size(): Grąžina dvipusės eilės elementų skaičių.
• clear(): Pašalina visus dvipusės eilės elementus.

3. Dvipusės eilės įgyvendinimai Java kalboje

Java kalboje Deque sąsają gali įgyvendinti dvi pagrindinės klasės: ArrayDeque ir LinkedList. Abi klasės palaiko dvipusės eilės operacijas ir siūlo skirtingus našumo privalumus.

a) ArrayDeque

ArrayDeque yra dvipusės eilės įgyvendinimas, pagrįstas masyvu, kuris automatiškai padidėja, jei trūksta vietos. ArrayDeque yra efektyvi ir naudojama dažniau nei LinkedList dvipusėms eilėms realizuoti.

• Privalumai: Greitos operacijos su abiem galais, nes ArrayDeque struktūroje nėra sinchronizacijos.
• Trūkumai: Neleidžia turėti null reikšmių ir nėra sinchronizuota (netinkama naudoti kelių gijų aplinkoje be papildomo sinchronizavimo).

Pavyzdys su ArrayDeque:

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

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Pridėjimas į pradžią ir galą
        deque.addFirst("Apple");
        deque.addLast("Banana");
        deque.offerFirst("Cherry");
        deque.offerLast("Date");

        System.out.println("Dvipusė eilė: " + deque);  // Gali būti tvarka [Cherry, Apple, Banana, Date]

        // Pašalinimas iš pradžios ir galo
        System.out.println("Pašalintas iš pradžios: " + deque.pollFirst());  // Pašalina "Cherry"
        System.out.println("Pašalintas iš galo: " + deque.pollLast());  // Pašalina "Date"

        System.out.println("Dvipusė po pašalinimų: " + deque);  // Gali būti tvarka [Apple, Banana]
    }
}

b) LinkedList

LinkedList taip pat gali būti naudojamas kaip dvipusė eilė, nes ji natūraliai palaiko įterpimą ir pašalinimą iš abiejų galų dėl sąrašo su ryšiais struktūros.

• Privalumai: Leidžia greitai įterpti ir pašalinti elementus iš abiejų galų, nes operacijos vykdomos su nuorodomis.
• Trūkumai: Lėtesnė prieiga prie elementų pagal poziciją, nes reikia pereiti per sąrašą.

Pavyzdys su LinkedList:

import java.util.Deque;
import java.util.LinkedList;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();

        // Pridėjimas į pradžią ir galą
        deque.addFirst(10);
        deque.addLast(20);
        deque.addFirst(5);
        deque.addLast(25);

        System.out.println("Dvipusė eilė: " + deque);  // Gali būti tvarka [5, 10, 20, 25]

        // Pašalinimas iš pradžios ir galo
        System.out.println("Pašalintas iš pradžios: " + deque.removeFirst());  // Pašalina 5
        System.out.println("Pašalintas iš galo: " + deque.removeLast());  // Pašalina 25

        System.out.println("Dvipusė eilė po pašalinimų: " + deque);  // Gali būti tvarka [10, 20]
    }
}

4. Dvipusės eilės naudojimo atvejai

Dvipusė eilė yra labai lanksti struktūra, todėl tinka įvairioms situacijoms, kai reikia įterpti arba šalinti duomenis iš abiejų galų. Štai keletas naudojimo atvejų:

• Dvikryptis tvarkymas: Kai reikia dirbti su duomenimis iš abiejų galų, pvz., plėtojant navigacijos istoriją (eiti pirmyn ir atgal tarp naršyklės puslapių).
• Dekoratoriaus šablonas (angl. Decorator Pattern): Kai dekoratoriaus šablone norime pridėti arba pašalinti dekoratorius iš bet kurio duomenų galo.
• Paieška į plotį (angl. Breadth-First Search, BFS): Algoritmuose, pvz., taikant paieškos į plotį algoritmą grafuose ar medžiuose, Deque naudojama kaip eilė, kur duomenys tvarkomi FIFO principu.
• Simuliacijos ar žaidimai: Kai reikalingas lankstus veikėjų ar objektų sąrašas, kuriame veiksmai atliekami abiem kryptimis.

5. Dvipusės eilės privalumai ir trūkumai Java kalboje

Privalumai:

• Dvipusis prieinamumas: Leidžia lengvai pridėti ir šalinti elementus iš abiejų galų.
• Lankstumas: Gali būti naudojama tiek kaip eilė, tiek kaip dėklas, todėl Deque tinka įvairiems duomenų tvarkymo scenarijams.
• Greitos operacijos: Pridėjimo ir šalinimo operacijos iš abiejų galų yra greitos (O(1) laiko sudėtingumas).

Trūkumai:

• Nėra sinchronizacijos: ArrayDeque ir LinkedList nėra sinchronizuotos klasės, todėl jų naudojimas kelių gijų aplinkoje gali būti pavojingas be papildomo sinchronizavimo.
• Atminties panaudojimas: LinkedList reikalauja daugiau atminties, nes kiekvienas elementas turi nuorodas į kitus elementus.
• Negalima naudoti null reikšmių: ArrayDeque nepriima null reikšmių, nes šios gali trukdyti kai kurioms metodų operacijoms.

6. Kodas su pagrindiniais Deque metodais Java kalboje

Štai pavyzdys, kuriame parodoma, kaip naudoti pagrindinius Deque metodus:

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Pridėjimas į pradžią ir galą
        deque.addFirst("A");
        deque.addLast("B");
        deque.offerFirst("C");
        deque.offerLast("D");

        System.out.println("Dvipusė eilė po pridėjimo: " + deque);  // [C, A, B, D]

        // Pašalinimas iš pradžios ir galo
        String firstRemoved = deque.pollFirst();  // Pašalina "C"
        String lastRemoved = deque.pollLast();  // Pašalina "D"

        System.out.println("Dvipusė eilė po pašalinimų: " + deque);  // [A, B]
        System.out.println("Pirmas pašalintas elementas: " + firstRemoved);
        System.out.println("Paskutinis pašalintas elementas: " + lastRemoved);

        // Prieiga prie pradžios ir galo elementų be pašalinimo
        System.out.println("Pirmas elementas: " + deque.peekFirst());  // Grąžina "A"
        System.out.println("Paskutinis elementas: " + deque.peekLast());  // Grąžina "B"
    }
}