Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lernen Warteschlangen-Datenstruktur in Java | Section
Grundlegende Datenstrukturen in Java

Warteschlangen-Datenstruktur in Java

Swipe um das Menü anzuzeigen

Beginnen wir mit einer Queue. Stellen Sie sich eine Warteschlange in einem Geschäft während eines Ausverkaufs vor. Es gibt 10 Personen; die erste Person steht näher an den Ladentüren als die anderen, und die 10. Person ist am weitesten entfernt. Wenn die erste Person das Geschäft betritt, verlässt sie die Warteschlange, wodurch sich die gesamte Warteschlange um eine Person nach vorne verschiebt. Die Java-Queue funktioniert nach einem sehr ähnlichen Prinzip.

Auf diese Weise lassen sich verschiedene Programme umsetzen, bei denen die Warteschlangenlogik durchdacht ist. Zum Beispiel die Implementierung eines Boards mit Plänen und Aufgaben.

Zunächst betrachten wir jedoch die grundlegenden Methoden zur Arbeit mit einer Queue.

Queue ist ein Interface, von dem die Klasse LinkedList erbt, die Ihnen bereits bekannt ist. Daher werden wir diese Implementierung verwenden.

So verwenden Sie das Interface als Objekttyp, aber die Implementierung des Objekts ist LinkedList, da dies eine konkrete Implementierung dieses Objekts ist. (Denken Sie daran, dass Sie keine Objekte auf Basis eines Interface erstellen können).

Beispiel:

Example.java

Example.java


              
1234

            
// `LinkedList` as implementation of the `List` interface:
List<T> list = new LinkedList<>(); 
// `LinkedList` as implementation of the `Queue` interface:
Queue<T> queue = new LinkedList<>();

Auf diese Weise kann die Anwendung sehr flexibel gestaltet werden, indem verschiedene Implementierungen derselben Schnittstelle verwendet werden.

Kehren wir jedoch zu den Methoden zur Arbeit mit Queue zurück.

Methoden

Einige wichtige Methoden des Queue-Interfaces sind:

  • add(element): Fügt ein Element zur Warteschlange hinzu und wirft eine Ausnahme, wenn die Operation nicht möglich ist;
  • offer(element): Fügt ein Element zur Warteschlange hinzu und gibt true zurück, wenn erfolgreich, oder false andernfalls.

Es fällt auf, dass diese Methoden im Wesentlichen dasselbe tun. Der entscheidende Unterschied liegt jedoch in der Sicherheit der offer-Methode. Im Falle eines nicht korrekt hinzugefügten Elements wirft die offer-Methode keine Ausnahme und stoppt die Programmausführung nicht.

Derzeit ist dieses Merkmal für uns jedoch nicht von großem Interesse, da eine normale Queue nicht begrenzt ist. Es gibt jedoch eine Struktur namens BlockingQueue, die eine Beschränkung der Elementanzahl aufweist; in diesem Fall besteht zwischen diesen Methoden ein deutlicher Unterschied.

Sehen wir uns ein Beispiel an:

Main.java

Main.java


              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.add("One");
        queue.add("Two");
        queue.add("Three");
        System.out.println("Queue: " + queue);
    }
}

Wie Sie sehen, wirft das Programm beim Verwenden der Methode add() und dem Versuch, ein Element hinzuzufügen, das nicht mehr in die Warteschlange passt, einen Fehler und beendet die Ausführung unerwartet.

Versuchen wir denselben Vorgang mit einer sichereren Methode — offer():

Main.java

Main.java


              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
    }
}

Wie Sie sehen, wurde das Element nicht zur Warteschlange hinzugefügt, aber es wurde auch keine Ausnahme ausgelöst. Daher können wir sagen, dass der Fehler ordnungsgemäß behandelt wurde.

Ausnahmen können auch anders behandelt werden, zum Beispiel mit einer Struktur wie try-catch, aber darauf gehen wir später ein.

Entfernungs-Methoden

  • remove(): Entfernt und gibt das Element am Anfang der Warteschlange zurück und löst eine Ausnahme aus, wenn die Warteschlange leer ist;
  • poll(): Entfernt und gibt das Element am Anfang der Warteschlange zurück und gibt null zurück, wenn die Warteschlange leer ist.

Diese Methoden führen genau die Funktion aus, als ob die erste Person in der Warteschlange das Geschäft betritt und die Warteschlange verlässt. Hier greift das FIFO-Prinzip (First In, First Out). Das bedeutet, dass das Element, das zuerst hinzugefügt wurde, auch als erstes entfernt wird.

Hier lässt sich auch der Unterschied zwischen diesen beiden Methoden erkennen. Die Methode poll() wird häufiger verwendet als die Methode remove(), da sie sicherer ist und keine Ausnahmen auslöst.

Schauen wir uns ein Beispiel an:

Main.java

Main.java


              
123456789101112131415

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.remove();
        queue.remove();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Wie Sie sehen, wirft das Programm eine NoSuchElementException, weil versucht wird, ein Element aus einer leeren Warteschlange zu entfernen.

Um eine solche Ausnahme zu vermeiden, ist es besser, die Methode poll() zu verwenden:

Main.java

Main.java


              
123456789101112131415

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.poll();
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Nun wurde ein Element sicher aus der Warteschlange entfernt, und es wurde keine Ausnahme ausgelöst, als versucht wurde, ein Element aus einer leeren Liste zu entfernen.

Die Eigenschaft, dass poll() null zurückgibt, kann beispielsweise in einer while()-Schleife verwendet werden.

Sehen wir uns ein Beispiel an:

Main.java

Main.java


              
1234567891011121314151617181920

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.poll() != null) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Auf diese Weise können alle Elemente aus der Queue mittels einer Schleife entfernt werden.

Beachte, dass das erste Element, das in die Queue eingefügt wurde, auch als erstes entfernt wird! Im obigen Beispiel wurde beispielsweise das Element mit den Daten "One" zuerst entfernt.

Das FIFO-Prinzip wird unten veranschaulicht:

Main.java

Main.java


              
123456789101112131415161718

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);         
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Wir können nun zu den Methoden übergehen, die das erste und das letzte Element zurückgeben:

  • element(): Gibt das Element am Anfang der Warteschlange zurück, entfernt es jedoch nicht, und wirft eine Ausnahme, wenn die Warteschlange leer ist;
  • peek(): Gibt das Element am Anfang der Warteschlange zurück, entfernt es jedoch nicht, und gibt null zurück, wenn die Warteschlange leer ist.

Die Verwendung der Methode peek() ist eine zuverlässigere und sicherere Vorgehensweise, da sie hilft, potenzielle Ausnahmen zu vermeiden.

Sehen wir uns ein Anwendungsbeispiel an:

Main.java

Main.java


              
12345678910111213141516

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
        System.out.println("The first element in the queue: " + queue.peek());
        System.out.println("Queue after the `peek()` method: " + queue);
    }
}

Sie können diese Methode mit anderen Warteschlangenmethoden kombinieren.

Wenn Sie eine Warteschlange mit fünf Elementen haben und alle Elemente bis einschließlich zum vierten entfernen müssen, sehen wir uns die Implementierung einer solchen Operation an:

Main.java

Main.java


              
123456789101112131415161718192021

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (!queue.peek().equals("Four")) {
            queue.poll();
        }
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

Es wurde eine Schleife mit einer Bedingung basierend auf der Methode peek() verwendet.

Diese Schleife kann deutlich optimiert werden, indem die Methode contains() eingesetzt wird. Diese Methode gibt true zurück, wenn das angegebene Element in der Queue vorhanden ist, und false, wenn nicht.

Verbesserung des obigen Codes:

Main.java

Main.java


              
1234567891011121314151617181920

            
package com.example;

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

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.contains("Four")) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

Hier wird eine einzige Bedingung für die while -Schleife festgelegt. Es wurde erfolgreich erreicht, alle Elemente bis einschließlich des Elements "Four" zu entfernen.

1. Was ist eine Queue in Java?

2. Welche Schnittstelle repräsentiert eine Queue im Java Collections Framework?

3. Was ist der Zweck der Methode offer() im Interface Queue?

4. Was macht die Methode poll() im Interface Queue?

5. Welche Klasse im Paket java.util.concurrent von Java stellt eine begrenzte, blockierende Warteschlange dar?

6. Was passiert, wenn Sie versuchen, mit der Methode add() ein Element zu einer vollen Warteschlange hinzuzufügen?

question mark

Was ist eine Queue in Java?

Wählen Sie die richtige Antwort aus

question mark

Welche Schnittstelle repräsentiert eine Queue im Java Collections Framework?

Wählen Sie die richtige Antwort aus

question mark

Was ist der Zweck der Methode offer() im Interface Queue?

Wählen Sie die richtige Antwort aus

question mark

Was macht die Methode poll() im Interface Queue?

Wählen Sie die richtige Antwort aus

question mark

Welche Klasse im Paket java.util.concurrent von Java stellt eine begrenzte, blockierende Warteschlange dar?

Wählen Sie die richtige Antwort aus

question mark

Was passiert, wenn Sie versuchen, mit der Methode add() ein Element zu einer vollen Warteschlange hinzuzufügen?

Wählen Sie die richtige Antwort aus

War alles klar?

Wie können wir es verbessern?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 9

Fragen Sie AI

expand

Fragen Sie AI

ChatGPT

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Abschnitt 1. Kapitel 9
some-alt