Java Language
Warteschlangen und Deques

Die Verwendung der PriorityQueue

PriorityQueue ist eine Datenstruktur. Wie SortedSet sortiert PriorityQueue auch seine Elemente nach ihren Prioritäten. Die Elemente, die eine höhere Priorität haben, stehen an erster Stelle. Der Typ von PriorityQueue sollte eine comparable oder comparator Schnittstelle implementieren, deren Methoden die Prioritäten der Elemente der Datenstruktur bestimmen.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

LinkedList als FIFO-Warteschlange

Die java.util.LinkedList Klasse ist bei der Implementierung von java.util.List eine universelle Implementierung der java.util.Queue Schnittstelle, die ebenfalls nach einem FIFO-Prinzip (First In, First Out) arbeitet.

In dem folgenden Beispiel werden mit der Methode offer() die Elemente in die LinkedList eingefügt. Dieser enqueue wird als enqueue . In der while Schleife werden die Elemente basierend auf dem FIFO aus der Queue entfernt. Diese Operation wird als dequeue .

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

Die Ausgabe dieses Codes ist

first element
second element
third element
fourth element
fifth element

Wie in der Ausgabe zu sehen ist, wird das erste eingefügte Element "erstes Element" zuerst entfernt, "zweites Element" wird an zweiter Stelle usw. entfernt.

Stacks

Was ist ein Stack?

In Java sind Stacks eine LIFO-Datenstruktur (Last In, First Out) für Objekte.

Stack-API

Java enthält eine Stack-API mit den folgenden Methoden

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

Beispiel

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

Dies kehrt zurück:

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

Eine BlockingQueue ist eine Schnittstelle, die eine Warteschlange ist, die blockiert, wenn Sie versuchen, die Warteschlange von der Warteschlange abzunehmen und die Warteschlange leer ist oder wenn Sie versuchen, Elemente in die Warteschlange aufzunehmen, und die Warteschlange bereits voll ist. Ein Thread, der versucht, sich aus einer leeren Warteschlange zu entschlüsseln, wird blockiert, bis ein anderer Thread ein Element in die Warteschlange einfügt. Ein Thread, der versucht, ein Element in eine vollständige Warteschlange einreihen zu lassen, wird blockiert, bis ein anderer Thread Platz in der Warteschlange bereitstellt, indem entweder ein oder mehrere Elemente aus der Warteschlange entfernt oder die Warteschlange vollständig gelöscht wird.

BlockingQueue-Methoden gibt es in vier Formen. Es gibt verschiedene Arten, Operationen zu behandeln, die nicht sofort erfüllt werden können, aber zu einem späteren Zeitpunkt erfüllt werden können: Eine gibt eine Ausnahme aus, die zweite gibt einen speziellen Wert zurück (entweder null oder falsch, abhängig von der Methode) operation), der dritte blockiert den aktuellen Thread auf unbestimmte Zeit, bis die Operation erfolgreich ausgeführt werden kann, und der vierte blockiert nur eine bestimmte Zeitdauer, bevor er aufgibt.

Eine BlockingQueue kann gebunden oder unbegrenzt sein . Eine begrenzte BlockingQueue ist eine, die mit der ursprünglichen Kapazität initialisiert wird.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

Alle Aufrufe einer put () - Methode werden blockiert, wenn die Größe der Warteschlange der ursprünglich festgelegten Kapazität entspricht.

Eine unbegrenzte Warteschlange ist eine Warteschlange, die ohne Kapazität initialisiert wird. Standardmäßig wird sie mit Integer.MAX_VALUE initialisiert.

Einige gängige Implementierungen von BlockingQueue sind:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Betrachten wir nun ein Beispiel für ArrayBlockingQueue :

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

Dies wird drucken:

Entry one done
Entry two done

Und der Thread wird nach der zweiten Ausgabe blockiert.

Warteschlangenschnittstelle

Grundlagen

Eine Queue ist eine Sammlung zum Halten von Elementen vor der Verarbeitung. Warteschlangen ordnen Elemente, jedoch nicht notwendigerweise, in einer FIFO-Art (first-in-first-out).

Kopf der Warteschlange ist das Element, das durch einen Aufruf zum Entfernen oder Abfragen entfernt werden würde. In einer FIFO-Warteschlange werden alle neuen Elemente am Ende der Warteschlange eingefügt.

Die Warteschlangenschnittstelle

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Jede Queue existiert in zwei Formen:

• man gibt eine Ausnahme aus, wenn die Operation fehlschlägt;
• other gibt einen speziellen Wert zurück, wenn der Vorgang fehlschlägt (je nach Vorgang entweder null oder false .

Deque

Ein Deque ist eine "doppelseitige Warteschlange". Deque bedeutet, dass ein Element am Deque oder am Ende der Warteschlange hinzugefügt werden kann. Die Warteschlange kann nur Elemente am Ende einer Warteschlange hinzufügen.

Deque erbt die Queue , was bedeutet, dass die regulären Methoden erhalten bleiben. Die Deque-Schnittstelle bietet jedoch zusätzliche Methoden, um mit einer Warteschlange flexibler zu sein. Die zusätzlichen Methoden sprechen für sich, wenn Sie wissen, wie eine Warteschlange funktioniert, da diese Methoden mehr Flexibilität bieten sollen:

Natürlich stehen die gleichen Optionen für offer , poll und peek zur Verfügung, sie funktionieren jedoch nicht mit Ausnahmen, sondern mit speziellen Werten. Es macht keinen Sinn zu zeigen, was sie hier tun.

Elemente hinzufügen und darauf zugreifen

Um dem Ende eines Deque Elemente hinzuzufügen, rufen Sie die add() Methode auf. Sie können auch die addFirst() und addLast() verwenden, die dem Kopf und dem Schwanz des Deque Elemente hinzufügen.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

Sie können auf das Element am Anfang der Warteschlange zugreifen, ohne das Element aus der Warteschlange zu entfernen. Dies geschieht über die Methode element() . Sie können auch die getFirst() und getLast() verwenden, die das erste und letzte Element im Deque . So sieht das aus:

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

Elemente entfernen

Um Elemente aus einem Deque zu entfernen, rufen Sie die Methoden remove() , removeFirst() und removeLast() . Hier einige Beispiele:

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();