Čakalna vrsta je druga vrsta linearne podatkovne strukture, ki se uporablja za shranjevanje elementov tako kot katera koli druga podatkovna struktura, vendar na določen način. Z enostavnimi besedami lahko rečemo, da je čakalna vrsta vrsta podatkovne strukture v programskem jeziku Java, ki shranjuje elemente iste vrste. Komponente v čakalni vrsti so shranjene v načinu FIFO (First In, First Out). Zbirka čakalne vrste ima dva konca, tj. sprednji in zadnji. Čakalna vrsta ima dva konca, in sicer sprednji in zadnji.

Naslednja slika odlično opisuje lastnost FIFO (First In, First Out) čakalne vrste Java.

format niza java

Kot je razloženo na prejšnji sliki, lahko vidimo, da je čakalna vrsta linearna podatkovna struktura z dvema terminaloma, tj. začetek (spredaj) in konec (zadaj). Komponente se v čakalno vrsto dodajajo z zadnjega dela čakalne vrste, komponente pa se ekstrahirajo s sprednjega dela čakalne vrste.

Čakalna vrsta je vmesnik v Java ki pripada paketu Java.util. Prav tako razširja vmesnik zbirke.

Splošna predstavitev vmesnika Java Queue je prikazana spodaj:

 public interface Queue extends Collection 

Kot smo razpravljali zgoraj, je čakalna vrsta vmesnik, zato lahko tudi rečemo, da čakalne vrste ni mogoče instancirati, ker vmesnikov ni mogoče instancirati. Če želi uporabnik implementirati funkcionalnost vmesnika Queue v Javi, mora imeti nekaj trdnih razredov, ki implementirajo vmesnik Queue.

V programskem jeziku Java obstajata dva različna razreda, ki se uporabljata za implementacijo vmesnika Queue. Ti razredi so:

uri proti url

• LinkedList
• PriorityQueue

Značilnosti čakalne vrste Java

Java Queue lahko štejemo za eno najpomembnejših podatkovnih struktur v svetu programiranja. Java Queue je privlačna zaradi svojih lastnosti. Pomembne lastnosti podatkovne strukture Java Queue so podane takole:

• Java Queue upošteva način FIFO (First In, First Out). Označuje, da so elementi vneseni v čakalno vrsto na koncu in izločeni od začetka.
• Vmesnik Java Queue ponuja vsa pravila in procese vmesnika Collection, kot so vključitev, brisanje itd.
• Obstajata dva različna razreda, ki se uporabljata za implementacijo vmesnika čakalne vrste. Ta razreda sta LinkedList in PriorityQueue.
• Razen teh dveh obstaja razred, to je Array Blocking Queue, ki se uporablja za implementacijo vmesnika Queue.
• Obstajata dve vrsti čakalnih vrst, neomejene čakalne vrste in omejene čakalne vrste. Čakalne vrste, ki so del paketa java.util, so znane kot neomejene čakalne vrste, omejene čakalne vrste pa so čakalne vrste, ki so prisotne v paketu java.util.concurrent.
• Deque ali (double-ended queue) je tudi vrsta čakalne vrste, ki vključuje vključevanje in brisanje elementov z obeh koncev.
• Deque velja tudi za varno na niti.
• Čakalne vrste za blokiranje so prav tako ena od vrst čakalnih vrst, ki so tudi varne za niti. Čakalne vrste za blokiranje se uporabljajo za izvajanje poizvedb proizvajalec-potrošnik.
• Čakalne vrste za blokiranje ne podpirajo ničelnih elementov. Če se v čakalnih vrstah za blokiranje poskusi kakršno koli delo, podobno ničelnim vrednostim, se vrže tudi izjema NullPointerException.

Implementacija čakalne vrste

Razredi, uporabljeni pri implementaciji čakalne vrste

Razredi, ki se uporabljajo za izvajanje funkcionalnosti čakalne vrste, so podani na naslednji način:

• ArrayDeque
• LinkedList
• PriorityQueue

Vmesniki, uporabljeni pri implementaciji čakalne vrste

Vmesniki Java se uporabljajo tudi pri implementaciji čakalne vrste Java. Vmesniki, ki se uporabljajo za izvajanje funkcionalnosti čakalne vrste, so podani na naslednji način:

• O čem
• Čakalna vrsta za blokiranje
• Blokiranje Deque

Metode razreda Java Queue

V čakalni vrsti Java je veliko metod, ki se zelo pogosto uporabljajo. Vmesnik Queue spodbuja različne metode, kot so vstavljanje, brisanje, pokukanje itd. Nekatere operacije čakalne vrste Java povzročijo izjemo, medtem ko nekatere od teh operacij vrnejo določeno vrednost, ko je program dokončan.

Opomba – V Javi SE 8 v zbirki čakalne vrste Java ni sprememb. Te metode, ki so definirane pod, so nadalje pripravljene v naslednjih različicah programskega jezika Java. Na primer Java SE 9.

Spodaj so definirane različne metode čakalne vrste Java:

Implementacija niza čakalnih vrst Java

Implementacija čakalne vrste ni tako enostavna kot implementacija sklada.

Za izvedbo čakalne vrste z uporabo matrik najprej deklariramo matriko, ki vsebuje n elementov.

Nato definiramo naslednje operacije, ki jih je treba izvesti v tej čakalni vrsti.

1) V čakalno vrsto: Operacija za vstavljanje elementa v čakalno vrsto je Enqueue (v programu funkcija čakalne vrste Enqueue). Za vstavljanje elementa na zadnji strani moramo najprej preveriti, ali je čakalna vrsta polna. Če je poln, elementa ne moremo vstaviti. Če zadaj

2) Rep: Operacija za izbris elementa iz čakalne vrste je Dequeue (funkcija queue Dequeue v programu). Najprej preverimo, ali je čakalna vrsta prazna. Da operacija odstranitve iz čakalne vrste deluje, mora biti v čakalni vrsti vsaj en element.

3) Spredaj: Ta metoda vrne začetek čakalne vrste.

vmesnik v Javi

4) Zaslon: Ta metoda prečka čakalno vrsto in prikaže elemente čakalne vrste.

Program Java Queue

Naslednji program Java prikazuje izvedbo čakalne vrste.

QueueArrayImplementation.java

 class Queue { private static int front, rear, capacity; private static int queue[]; Queue(int size) { front = rear = 0; capacity = size; queue = new int[capacity]; } // insert an element into the queue static void queueEnqueue(int item) { // check if the queue is full if (capacity == rear) { System.out.printf('
Queue is full
'); return; } // insert element at the rear else { queue[rear] = item; rear++; } return; } //remove an element from the queue static void queueDequeue() { // check if queue is empty if (front == rear) { System.out.printf('
Queue is empty
&apos;); return; } // shift elements to the right by one place uptil rear else { for (int i = 0; i <rear 0 4 - 1; i++) { queue[i]="queue[i" + 1]; } set queue[rear] to if (rear < capacity) decrement rear rear--; return; print queue elements static void queuedisplay() int i; (front="=" rear) system.out.printf('queue is empty
'); traverse front and for (i="front;" i rear; system.out.printf(' %d , ', queue[i]); of queuefront() system.out.printf('
front element the queue: %d', queue[front]); public class queuearrayimplementation main(string[] args) create a capacity q="new" queue(4); system.out.println('initial queue:'); q.queuedisplay(); inserting in q.queueenqueue(10); q.queueenqueue(30); q.queueenqueue(50); q.queueenqueue(70); system.out.println('queue after enqueue operation:'); q.queuefront(); insert q.queueenqueue(90); q.queuedequeue(); system.out.printf('
queue two dequeue operations:'); pre> <p> <strong>Output:</strong> </p> <pre> Initial Queue: Queue is Empty Queue after Enqueue Operation: 10 , 30 , 50 , 70 , Front Element of the queue: 10 Queue is full 10 , 30 , 50 , 70 , Queue after two dequeue operations: 50 , 70 , Front Element of the queue: 50 </pre> <h2>Java Queue Linked List Implementation</h2> <p>As we have implemented the Queue data structure using Arrays in the above program, we can also implement the Queue using Linked List.</p> <p>We will implement the same methods enqueue, dequeue, front, and display in this program. The difference is that we will be using the Linked List data structure instead of Array.</p> <p>The below program demonstrates the Linked List implementation of Queue in Java.</p> <p> <strong>QueueLLImplementation.java</strong> </p> <pre> class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front &amp; rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println(&apos;Element &apos; + data+ &apos; removed from the queue&apos;); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println(&apos;Element &apos; + data+ &apos; added to the queue&apos;); } //print front and rear of the queue public void print_frontRear() { System.out.println(&apos;Front of the queue:&apos; + front.data + &apos; Rear of the queue:&apos; + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } </pre> <p> <strong>Output:</strong> </p> <pre> Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9 </pre> <hr></rear>

Izvedba povezanega seznama Java Queue

Ker smo v zgornjem programu implementirali podatkovno strukturo čakalne vrste z uporabo nizov, lahko čakalno vrsto implementiramo tudi s povezanim seznamom.

V tem programu bomo implementirali enake metode za uvrstitev v čakalno vrsto, odstranitev iz čakalne vrste, spredaj in prikaz. Razlika je v tem, da bomo namesto matrike uporabljali podatkovno strukturo povezanega seznama.

Spodnji program prikazuje izvedbo povezanega seznama čakalne vrste v Javi.

QueueLLImplementation.java

sestra kat timpf

 class LinkedListQueue { private Node front, rear; private int queueSize; // queue size //linked list node private class Node { int data; Node next; } //default constructor - initially front & rear are null; size=0; queue is empty public LinkedListQueue() { front = null; rear = null; queueSize = 0; } //check if the queue is empty public boolean isEmpty() { return (queueSize == 0); } //Remove item from the front of the queue. public int dequeue() { int data = front.data; front = front.next; if (isEmpty()) { rear = null; } queueSize--; System.out.println('Element ' + data+ ' removed from the queue'); return data; } //Add data at the rear of the queue. public void enqueue(int data) { Node oldRear = rear; rear = new Node(); rear.data = data; rear.next = null; if (isEmpty()) { front = rear; } else { oldRear.next = rear; } queueSize++; System.out.println('Element ' + data+ ' added to the queue'); } //print front and rear of the queue public void print_frontRear() { System.out.println('Front of the queue:' + front.data + ' Rear of the queue:' + rear.data); } } class QueueLLImplementation{ public static void main(String a[]){ LinkedListQueue queue = new LinkedListQueue(); queue.enqueue(6); queue.enqueue(3); queue.print_frontRear(); queue.enqueue(12); queue.enqueue(24); queue.dequeue(); queue.dequeue(); queue.enqueue(9); queue.print_frontRear(); } } 

Izhod:

 Element 6 added to the queue Element 3 added to the queue Front of the queue:6 Rear of the queue:3 Element 12 added to the queue Element 24 added to the queue Element 6 removed from the queue Element 3 removed from the queue Element 9 added to the queue Front of the queue:12 Rear of the queue:9