Eine Warteschlange ist eine andere Art linearer Datenstruktur, die wie jede andere Datenstruktur zum Speichern von Elementen verwendet wird, jedoch auf eine bestimmte Weise. Mit einfachen Worten können wir sagen, dass die Warteschlange eine Art Datenstruktur in der Programmiersprache Java ist, die Elemente derselben Art speichert. Die Komponenten in einer Warteschlange werden in einem FIFO-Verhalten (First In, First Out) gespeichert. Es gibt zwei Enden in der Warteschlangensammlung, nämlich vorne und hinten. Die Warteschlange hat zwei Enden, nämlich vorne und hinten.
Die folgende Abbildung beschreibt perfekt die FIFO-Eigenschaft (First In, First Out) der Java-Warteschlange.
Wie im vorherigen Bild erläutert, können wir sehen, dass die Warteschlange eine lineare Datenstruktur mit zwei Terminals ist, nämlich Start (vorne) und Ende (hinten). Komponenten werden am hinteren Ende der Warteschlange in die Warteschlange eingefügt und am vorderen Ende der Warteschlange entnommen.
Die Queue ist eine Schnittstelle im Java das gehört zum Java.util-Paket. Es erweitert auch die Collection-Schnittstelle.
Die generische Darstellung der Java Queue-Schnittstelle ist unten dargestellt:
public interface Queue extends Collection
Da wir oben besprochen haben, dass die Warteschlange eine Schnittstelle ist, können wir auch sagen, dass die Warteschlange nicht instanziiert werden kann, weil Schnittstellen nicht instanziiert werden können. Wenn ein Benutzer die Funktionalität der Queue-Schnittstelle in Java implementieren möchte, ist es zwingend erforderlich, über einige solide Klassen zu verfügen, die die Queue-Schnittstelle implementieren.
In der Programmiersprache Java gibt es zwei verschiedene Klassen, die zur Implementierung der Queue-Schnittstelle verwendet werden. Diese Klassen sind:
Eigenschaften der Java-Warteschlange
Die Java-Warteschlange kann als eine der wichtigsten Datenstrukturen in der Programmierwelt angesehen werden. Java Queue ist aufgrund seiner Eigenschaften attraktiv. Die wesentlichen Eigenschaften der Java-Warteschlangen-Datenstruktur sind wie folgt:
- Die Java-Warteschlange folgt dem FIFO-Prinzip (First In, First Out). Es zeigt an, dass Elemente am Ende in die Warteschlange eingegeben und von vorne entfernt werden.
- Die Java Queue-Schnittstelle stellt alle Regeln und Prozesse der Collection-Schnittstelle bereit, wie Einschluss, Löschung usw.
- Es gibt zwei verschiedene Klassen, die zur Implementierung der Queue-Schnittstelle verwendet werden. Diese Klassen sind LinkedList und PriorityQueue.
- Abgesehen von diesen beiden gibt es eine Klasse, nämlich Array Blocking Queue, die zur Implementierung der Queue-Schnittstelle verwendet wird.
- Es gibt zwei Arten von Warteschlangen: unbegrenzte Warteschlangen und begrenzte Warteschlangen. Die Warteschlangen, die Teil des Pakets java.util sind, werden als unbegrenzte Warteschlangen bezeichnet, und begrenzte Warteschlangen sind die Warteschlangen, die im Paket java.util.concurrent vorhanden sind.
- Die Deque oder (doppelendige Warteschlange) ist ebenfalls eine Art Warteschlange, die das Einschließen und Löschen von Elementen an beiden Enden ermöglicht.
- Die Deque gilt auch als Thread-sicher.
- Blockierende Warteschlangen gehören ebenfalls zu den Arten von Warteschlangen, die ebenfalls threadsicher sind. Die Blocking Queues werden zur Implementierung der Producer-Consumer-Abfragen verwendet.
- Blockierungswarteschlangen unterstützen keine Nullelemente. Wenn in Blockierungswarteschlangen eine Arbeit versucht wird, die Nullwerten ähnelt, wird auch die NullPointerException ausgelöst.
Implementierung der Warteschlange
Klassen, die bei der Implementierung von Queue verwendet werden
Die Klassen, die zur Implementierung der Funktionalitäten der Warteschlange verwendet werden, sind wie folgt angegeben:
Schnittstellen, die bei der Implementierung von Queue verwendet werden
Die Java-Schnittstellen werden auch bei der Implementierung der Java-Warteschlange verwendet. Die Schnittstellen, die zur Implementierung der Funktionalitäten der Warteschlange verwendet werden, sind wie folgt angegeben:
- Worüber
- Blockierungswarteschlange
- Deque blockieren
Methoden der Java-Warteschlangenklasse
In der Java-Warteschlange gibt es viele Methoden, die sehr häufig verwendet werden. Die Queue-Schnittstelle unterstützt verschiedene Methoden wie Einfügen, Löschen, Peek usw. Einige der Vorgänge der Java-Warteschlange lösen eine Ausnahme aus, während einige dieser Vorgänge einen bestimmten Wert zurückgeben, wenn das Programm abgeschlossen ist.
Nick Pulos schwarzer Blitz
Hinweis – In Java SE 8 werden keine Änderungen an der Java-Warteschlangensammlung vorgenommen. Diese unter definierten Methoden werden in den nachfolgenden Versionen der Programmiersprache Java weiter vorbereitet. Zum Beispiel Java SE 9.
Im Folgenden werden verschiedene Methoden der Java Queue definiert:
| Methode | Methodenprototyp | Beschreibung |
|---|---|---|
| hinzufügen | boolescher Wert add(E e) | Fügt Element e der Warteschlange am Ende (Ende) der Warteschlange hinzu, ohne die Kapazitätsbeschränkungen zu verletzen. Gibt bei Erfolg „true“ oder „IllegalStateException“ zurück, wenn die Kapazität erschöpft ist. |
| spähen | E peek() | Gibt den Kopf (Vorderseite) der Warteschlange zurück, ohne ihn zu entfernen. |
| Element | E-Element() | Führt den gleichen Vorgang wie die peek()-Methode aus. Löst eine NoSuchElementException aus, wenn die Warteschlange leer ist. |
| entfernen | E entfernen() | Entfernt den Kopf der Warteschlange und gibt ihn zurück. Löst eine NoSuchElementException aus, wenn die Warteschlange leer ist. |
| Umfrage | E-Umfrage() | Entfernt den Kopf der Warteschlange und gibt ihn zurück. Wenn die Warteschlange leer ist, wird null zurückgegeben. |
| Angebot | boolesches Angebot (E e) | Fügen Sie das neue Element e in die Warteschlange ein, ohne die Kapazitätsbeschränkungen zu verletzen. |
| Größe | int size() | Gibt die Größe oder Anzahl der Elemente in der Warteschlange zurück. |
Implementierung eines Java-Warteschlangenarrays
Die Warteschlangenimplementierung ist nicht so einfach wie eine Stack-Implementierung.
Um eine Warteschlange mithilfe von Arrays zu implementieren, deklarieren wir zunächst ein Array, das n Elemente enthält.
Dann definieren wir die folgenden Operationen, die in dieser Warteschlange ausgeführt werden sollen.
1) Einreihen: Eine Operation zum Einfügen eines Elements in die Warteschlange ist Enqueue (Funktionswarteschlange Enqueue im Programm). Um ein Element am hinteren Ende einzufügen, müssen wir zunächst prüfen, ob die Warteschlange voll ist. Wenn es voll ist, können wir das Element nicht einfügen. Wenn hinten 2) Schwanz: Die Operation zum Löschen eines Elements aus der Warteschlange ist Dequeue (Funktionswarteschlange Dequeue im Programm). Zuerst prüfen wir, ob die Warteschlange leer ist. Damit der Vorgang zum Entfernen aus der Warteschlange funktioniert, muss sich mindestens ein Element in der Warteschlange befinden. 3) Vorderseite: Diese Methode gibt den Anfang der Warteschlange zurück. 4) Anzeige: Diese Methode durchläuft die Warteschlange und zeigt die Elemente der Warteschlange an. Das folgende Java-Programm demonstriert die Implementierung von Queue. QueueArrayImplementation.java Da wir im obigen Programm die Warteschlangendatenstruktur mithilfe von Arrays implementiert haben, können wir die Warteschlange auch mithilfe einer verknüpften Liste implementieren. Wir werden in diesem Programm die gleichen Methoden „enqueue“, „dequeue“, „front“ und „display“ implementieren. Der Unterschied besteht darin, dass wir die Datenstruktur „Linked List“ anstelle von Array verwenden. Das folgende Programm demonstriert die Linked-List-Implementierung von Queue in Java. QueueLLImplementation.java Ausgabe: Java-Warteschlangenprogramm
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> Implementierung einer Java-Warteschlangen-verknüpften Liste
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
Latexschrift