Een wachtrij is een ander soort lineaire datastructuur die wordt gebruikt om elementen op te slaan, net als elke andere datastructuur, maar op een bepaalde manier. In eenvoudige bewoordingen kunnen we zeggen dat de wachtrij een soort gegevensstructuur is in de Java-programmeertaal die elementen van dezelfde soort opslaat. De componenten in een wachtrij worden opgeslagen in een FIFO-gedrag (First In, First Out). Er zijn twee uiteinden in de wachtrijverzameling, namelijk voor en achter. De wachtrij heeft twee uiteinden: voor en achter.
De volgende afbeelding beschrijft perfect de FIFO-eigenschap (First In, First Out) van de Java-wachtrij.
iteratie van de kaart in Java
Zoals uitgelegd in de voorgaande afbeelding, kunnen we zien dat de wachtrij een lineaire datastructuur is met twee terminals, dat wil zeggen begin (voorkant) en einde (achterkant). Componenten worden aan de achterkant van de wachtrij aan de wachtrij toegevoegd en de componenten worden aan de voorkant van de wachtrij geëxtraheerd.
De wachtrij is een interface in het Java dat hoort bij het Java.util-pakket. Het breidt ook de collectie-interface uit.
De algemene weergave van de Java Queue-interface wordt hieronder weergegeven:
public interface Queue extends Collection
Zoals we hierboven hebben besproken, is de wachtrij een interface. Daarom kunnen we ook zeggen dat de wachtrij niet kan worden geïnstantieerd omdat interfaces niet kunnen worden geïnstantieerd. Als een gebruiker de functionaliteit van de Queue-interface in Java wil implementeren, is het verplicht om een aantal solide klassen te hebben die de Queue-interface implementeren.
In de Java-programmeertaal zijn er twee verschillende klassen die worden gebruikt om de Queue-interface te implementeren. Deze klassen zijn:
Kenmerken van de Java-wachtrij
De Java Queue kan worden beschouwd als een van de belangrijkste datastructuren in de programmeerwereld. Java Queue is aantrekkelijk vanwege zijn eigenschappen. De belangrijke eigenschappen van de Java Queue-gegevensstructuur worden als volgt weergegeven:
- Java Queue volgt de FIFO-methode (First In, First Out). Het geeft aan dat elementen aan het einde in de wachtrij worden geplaatst en aan de voorkant worden geëlimineerd.
- De Java Queue-interface geeft alle regels en processen van de Collection-interface, zoals opname, verwijdering, enz.
- Er zijn twee verschillende klassen die worden gebruikt om de Queue-interface te implementeren. Deze klassen zijn LinkedList en PriorityQueue.
- Naast deze twee is er een klasse Array Blocking Queue die wordt gebruikt om de Queue-interface te implementeren.
- Er zijn twee soorten wachtrijen: onbegrensde wachtrijen en begrensde wachtrijen. De wachtrijen die deel uitmaken van het java.util-pakket staan bekend als de onbegrensde wachtrijen en begrensde wachtrijen zijn de wachtrijen die aanwezig zijn in het java.util.concurrent-pakket.
- De Deque of (dubbele wachtrij) is ook een soort wachtrij die het opnemen en verwijderen van elementen van beide kanten mogelijk maakt.
- De deque wordt ook als draadveilig beschouwd.
- Blokkeerwachtrijen zijn ook een van de soorten wachtrijen die ook thread-safe zijn. De blokkeringswachtrijen worden gebruikt om de producenten-consumentenquery's te implementeren.
- Blokkeerwachtrijen ondersteunen geen nulelementen. Als in Blokkeerwachtrijen werk wordt geprobeerd dat lijkt op null-waarden, wordt ook de NullPointerException gegenereerd.
Implementatie van wachtrij
Klassen die worden gebruikt bij de implementatie van Queue
De klassen die worden gebruikt om de functionaliteiten van de wachtrij te implementeren, worden als volgt gegeven:
Interfaces gebruikt bij de implementatie van Queue
De Java-interfaces worden ook gebruikt bij de implementatie van de Java-wachtrij. De interfaces die worden gebruikt om de functionaliteiten van de wachtrij te implementeren, worden als volgt weergegeven:
- Over wat
- Wachtrij blokkeren
- Blokkeren Deque
Methoden voor Java-wachtrijklassen
In de Java-wachtrij zijn er veel methoden die zeer vaak worden gebruikt. De Queue-interface promoot verschillende methoden, zoals invoegen, verwijderen, peeken, enz. Sommige bewerkingen in de Java-wachtrij veroorzaken een uitzondering, terwijl sommige van deze bewerkingen een bepaalde waarde retourneren wanneer het programma is voltooid.
Opmerking - In Java SE 8 zijn er geen wijzigingen aangebracht in de Java-wachtrijverzameling. Deze methoden die hieronder worden gedefinieerd, worden verder voorbereid in de volgende versies van de Java-programmeertaal. Bijvoorbeeld Java SE 9.
Hieronder worden verschillende methoden van de Java Queue gedefinieerd:
| Methode | Methode Prototype | Beschrijving |
|---|---|---|
| toevoegen | Booleaanse optelling(E e) | Voegt element e toe aan de wachtrij aan het einde (staart) van de wachtrij zonder de beperkingen op de capaciteit te schenden. Retourneert waar als het lukt, of IllegalStateException als de capaciteit is uitgeput. |
| kijkje | E kijkje() | Retourneert de kop (voorkant) van de wachtrij zonder deze te verwijderen. |
| element | E-element() | Voert dezelfde bewerking uit als de peek()-methode. Genereert NoSuchElementException wanneer de wachtrij leeg is. |
| verwijderen | E verwijderen() | Verwijdert de kop van de wachtrij en retourneert deze. Genereert NoSuchElementException als de wachtrij leeg is. |
| opiniepeiling | E-peiling() | Verwijdert de kop van de wachtrij en retourneert deze. Als de wachtrij leeg is, retourneert deze null. |
| Aanbod | Booleaanse aanbieding(E e) | Voeg het nieuwe element e in de wachtrij in zonder de capaciteitsbeperkingen te schenden. |
| maat | int-grootte() | Retourneert de grootte of het aantal elementen in de wachtrij. |
Implementatie van Java Queue Arrays
Wachtrijimplementatie is niet zo eenvoudig als een stapelimplementatie.
Om wachtrijen te implementeren met behulp van arrays, declareren we eerst een array die n aantal elementen bevat.
Vervolgens definiëren we de volgende bewerkingen die in deze wachtrij moeten worden uitgevoerd.
1) In wachtrij: Een bewerking om een element in de wachtrij in te voegen is Enqueue (functie wachtrij Enqueue in het programma). Om een element aan de achterkant in te voegen, moeten we eerst controleren of de wachtrij vol is. Als deze vol is, kunnen we het element niet invoegen. Indien achter 2) Staart: De bewerking om een element uit de wachtrij te verwijderen is Dequeue (functiewachtrij Dequeue in het programma). Eerst controleren we of de wachtrij leeg is. Om de wachtrijbewerking te laten werken, moet er ten minste één element in de wachtrij aanwezig zijn. 3) Voorkant: Deze methode retourneert de voorkant van de wachtrij. 4) Weergave: Deze methode doorloopt de wachtrij en geeft de elementen van de wachtrij weer. Het volgende Java-programma demonstreert de implementatie van Queue. QueueArrayImplementation.java Omdat we in het bovenstaande programma de wachtrijgegevensstructuur hebben geïmplementeerd met behulp van arrays, kunnen we de wachtrij ook implementeren met behulp van Linked List. We zullen in dit programma dezelfde methoden implementeren, in de wachtrij plaatsen, uit de wachtrij halen, fronten weergeven. Het verschil is dat we de Linked List-gegevensstructuur zullen gebruiken in plaats van Array. Het onderstaande programma demonstreert de Linked List-implementatie van Queue in Java. QueueLLImplementatie.java Uitgang: Java Queue-programma
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
'); 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 & 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(); } } </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> Implementatie van gekoppelde lijst met Java Queue
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(); } } 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
microlithische kern