Algoritmai ir duomenų struktūros

Eilė (angl. queue) yra struktūrinis duomenų tipas, pagrįstas „pirmas atėjo – pirmas išėjo“ (angl. First-In-First-Out, FIFO) principu. Šis reiškia, kad elementai eilėje išdėstomi pagal jų įterpimo tvarką, o pirmas įterptas elementas bus pirmas pašalintas. Eilės duomenų struktūra ypač tinka scenarijams, kai reikia valdyti procesų, užduočių ar išteklių laukimą (pvz., klientų aptarnavime, procesorių planavime).

Java kalboje eilė yra realizuojama naudojant Queue sąsają, kuri priklauso Java kolekcijų karkasui (angl. Java Collections Framework) ir siūlo metodus, skirtus darbui su eilės struktūra. Queue sąsajos įgyvendinimus galima rasti įvairiose klasėse, tokiose kaip LinkedList, PriorityQueue, ArrayDeque, kurios kiekviena siūlo skirtingas eilės naudojimo galimybes.

1. Eilės sąsaja Java kalboje

Java kalboje Queue yra sąsaja (angl. interface), kurią įgyvendina įvairios klasės. Queue sąsajoje apibrėžti pagrindiniai metodai, reikalingi darbui su eilės struktūra:

• add(E e): Įterpia elementą į eilės galą. Jei eilė turi nustatytą talpą ir yra pilna, metodas sukelia išimtį.
• offer(E e): Taip pat įterpia elementą į eilės galą, tačiau, priešingai nei add(), nekelia išimties, jei elementas negali būti pridėtas (pavyzdžiui, grąžina false, jei eilė pilna).
• poll(): Pašalina ir grąžina pirmą eilės elementą. Jei eilė tuščia, grąžina null.
• remove(): Taip pat pašalina ir grąžina pirmą eilės elementą, tačiau, jei eilė tuščia, sukelia išimtį.
• peek(): Grąžina pirmą eilės elementą, tačiau jo nepašalina. Jei eilė tuščia, grąžina null.
• element(): Panašus į peek(), grąžina pirmą eilės elementą, tačiau sukelia išimtį, jei eilė tuščia.

2. Eilės įgyvendinimo klasės

Queue sąsają Java kalboje gali įgyvendinti kelios klasės, kurios siūlo skirtingas funkcijas priklausomai nuo naudojimo scenarijaus:

a) LinkedList kaip eilė

LinkedList klasė dažnai naudojama kaip eilės struktūra, nes natūraliai palaiko FIFO veikimo principą:

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.poll());  // Grąžina ir pašalina 1
System.out.println(queue.peek());  // Grąžina 2 (nepašalina)
System.out.println("Likę elementai: " + queue);

b) PriorityQueue

PriorityQueue yra eilės įgyvendinimas, kuris rikiuoja elementus pagal jų prioritetą. Priešingai nei įprasta FIFO eilė, čia pašalinami elementai su aukščiausiu prioritetu:

Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(5);
priorityQueue.add(1);
priorityQueue.add(3);
System.out.println(priorityQueue.poll());  // Grąžina ir pašalina 1 (mažiausias elementas)
System.out.println("Likę elementai: " + priorityQueue);

c) ArrayDeque kaip eilė

ArrayDeque klasė yra lanksti, efektyvi dvikryptė eilė, kuri gali būti naudojama tiek kaip eilė, tiek kaip dėklas:

Queue<String> dequeQueue = new ArrayDeque<>();
dequeQueue.offer("A");
dequeQueue.offer("B");
dequeQueue.offer("C");
System.out.println(dequeQueue.poll());  // Grąžina ir pašalina "A"
System.out.println(dequeQueue.peek());  // Grąžina "B" (nepašalina)
System.out.println("Likę elementai: " + dequeQueue);

3. Eilės veikimo principas

Eilė veikia remiantis FIFO (pirmas atėjo – pirmas išėjo) principu. Tai reiškia, kad pirmas įterptas elementas bus pirmas pašalintas. Tipinis eilės scenarijus apima šiuos žingsnius:

1. Įterpimas į eilę: Elementai įterpiami į eilės galą naudojant add() arba offer() metodą.
2. Pašalinimas iš eilės: Elementai pašalinami iš eilės pradžios naudojant poll() arba remove() metodą.
3. Prieiga prie pirmo elemento: Pirmas eilės elementas gali būti pasiektas be pašalinimo naudojant peek() arba element() metodą.

4. Kodas su visų pagrindinių Queue metodų pavyzdžiais

Kodas, parodantis visų pagrindinių Queue sąsajos metodų naudojimą:

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue queue = new LinkedList<>();

        // Įterpimas į eilę
        queue.add("Pirmas");
        queue.offer("Antras");
        queue.offer("Trečias");

        // Prieiga prie pirmo elemento be pašalinimo
        System.out.println(queue.peek());   // Grąžina "Pirmas"
        System.out.println(queue.element());  // Grąžina "Pirmas"

        // Pašalinimas iš eilės
        System.out.println("Pašalintas: " + queue.poll());   // Pašalina ir grąžina "Pirmas"
        System.out.println("Pašalintas: " + queue.remove());  // Pašalina ir grąžina "Antras"

        // Likę elementai eilėje
        System.out.println("Likę elementai: " + queue);  // Likęs "Trečias"
    }
}

5. Eilės naudojimo atvejai

Eilės duomenų struktūra tinka situacijoms, kai duomenys turi būti apdorojami tokia tvarka, kokia jie atėjo. Pavyzdžiui:

Spausdinimo užduočių tvarkymas (print queue)

• Spausdintuvo užduotys: Kai kompiuteryje kelios programos siunčia dokumentus spausdinti, spausdintuvas prideda kiekvieną užduotį į eilę. Užduotys apdorojamos tokia tvarka, kokia jos buvo pateiktos, siekiant išvengti užduočių praleidimo ar spausdinimo be tvarkos.

Procesų ir užduočių planavimas operacinėse sistemose

• Procesų tvarkaraščiai: Operacinėse sistemose vykdomi procesai dažnai tvarkomi FIFO tvarka, kad užtikrintų teisingą naudojimąsi procesoriaus laiku. Tai ypač svarbu realaus laiko sistemose, kur užduotys turi būti atliktos pagal numatytą grafiką.
• Naudotojų procesų valdymas: Sistemoje procesai, pateikti vienu metu, gali būti pridedami į eilę ir laukti, kol bus paskirti procesoriaus resursai.

Tinklo duomenų srautai ir paketų tvarkymas (network packet queuing)

• Maršrutizatoriai ir tinklo įrenginiai: Maršrutizatoriai duomenų paketus priima ir nukreipia FIFO tvarka. Kiekvienas duomenų paketas siunčiamas ir priimamas tokia tvarka, kokia atkeliauja, kad būtų užtikrintas duomenų perdavimo nuoseklumas.
• DDoS atakų valdymas: Kai tinklo apkrova yra didelė, eilės struktūra gali padėti filtruoti paketus ir sumažinti šlamšto srautą, praleidžiant tik tuos paketus, kurie yra įtraukti į FIFO struktūrą.

Įvykių tvarkymas (event handling)

• GUI programose: Grafinės naudotojo sąsajos (GUI) programose įvykiai, tokie kaip mygtukų paspaudimai ar pelės judesiai, yra laikomi FIFO eilėje. Taip programa apdoroja įvykius tokia tvarka, kokia jie buvo atlikti, užtikrindama, kad naudotojo veiksmai būtų vykdomi logiškai.
• Žaidimai: Vaizdo žaidimuose įvykiai, tokie kaip žaidėjo komandos ar įvykiai žaidimo pasaulyje, yra įtraukiami į eilę. Šis būdas leidžia žaidimui tvarkingai apdoroti visus įvykius, išlaikant nuoseklumą ir žaidimo stabilumą.

Žinučių siuntimas ir eilių valdymas serveriuose

• Eilės žinučių siuntimui: Kai serveriai gauna daugybę užklausų iš klientų, jos tvarkomos FIFO eilėje. Taip serveris užtikrina, kad kiekviena užklausa bus apdorota nuosekliai, o atsakymai bus grąžinti tokia tvarka, kokia buvo pateiktos užklausos.
• Sistemos žinutės: Kai serveris gauna sistemines užduotis arba persiunčia žinutes tarp procesų, FIFO eilė padeda tvarkingai apdoroti šias žinutes ir išvengti duomenų konflikto.

Navigacijos algoritmai ir kelio paieška (pathfinding)

• Kelio paieška ir trumpiausio kelio algoritmai: Pavyzdžiui, paieškos į plotį (angl. Breadth-First Search, BFS) algoritmas naudoja eilę, kad nuosekliai tvarkytų mazgus ir ieškotų trumpiausio kelio grafuose. Eilės struktūra leidžia tvarkingai peržvelgti visus galimus kelius iki galutinio tikslo.

Eilės paslaugoms internete (online queuing systems)

• Registracija internetu: Pavyzdžiui, kai norima prisijungti prie populiarios internetinės paslaugos (pvz., bilietų pirkimo ar registracijos), klientai dažnai patenka į virtualią eilę, kuri apdoroja kiekvieną klientą tokia tvarka, kokia jie prisijungė. Tai užtikrina teisingą eilės principą net ir didelės apkrovos metu.
• Dalyvavimas seminaruose ar renginiuose: Daugelis seminarų registracijos internetu turi FIFO principu veikiančias eilės sistemas, kad užtikrintų registracijos tvarką pagal pirmumo principą.

Užklausų tvarkymas duomenų bazėse

• SQL užklausų tvarkymas: Kai keli naudotojai vienu metu pateikia SQL užklausas, jos gali būti apdorojamos FIFO eilėje, užtikrinant, kad kiekvienas naudotojas gautų atsakymą tokia tvarka, kokia pateikė užklausą.
• Sandorių tvarkymas: Duomenų bazės taip pat naudoja FIFO struktūrą, kad apdorotų sandorius nuosekliai ir išlaikytų duomenų vientisumą.

Riboti ištekliai arba limituota prieiga (Rate Limiting)

• API užklausos: Daugelis API serverių naudoja eiles, kad valdytų gaunamų užklausų srautą ir užtikrintų, kad per vienetą laiko būtų priimtas tik ribotas užklausų skaičius. FIFO eilė čia padeda paskirstyti užklausas taip, kad serveris nebūtų perkrautas.
• Didesnė duomenų apkrova: Jei sistemoje ištekliai riboti, FIFO eilė padeda valdyti apkrovą ir išlaikyti stabilų sisteminį darbą, tvarkant užklausas pagal jų gavimo laiką.

6. Eilės privalumai ir trūkumai Java kalboje

Privalumai:

• Lengva struktūra: Eilė suteikia paprastą būdą valdyti duomenis FIFO principu.
• Naudinga tam tikriems scenarijams: Idealiai tinka užduočių planavimui, duomenų srautams ir išteklių valdymui.
• Įvairūs įgyvendinimai: Java siūlo kelias eilės įgyvendinimo klases, kurios leidžia pasirinkti tinkamą struktūrą pagal poreikius.

Trūkumai:

• Ribota prieiga: Galima pasiekti tik pirmą eilės elementą, todėl nėra galimybės tiesiogiai pasiekti elementų viduryje.
• Atminties valdymas: Kai kuriuose įgyvendinimuose, pavyzdžiui, LinkedList, naudojami papildomi rodyklės laukai, todėl reikia daugiau atminties nei paprasto masyvo struktūroje.
• Ne visada greičiausia alternatyva: Priklausomai nuo naudojimo atvejo, alternatyvios struktūros gali būti efektyvesnės.