Java Language
Wachtrijen en Deques

Het gebruik van de PriorityQueue

PriorityQueue is een gegevensstructuur. Net als SortedSet sorteert PriorityQueue ook zijn elementen op basis van hun prioriteiten. De elementen, die een hogere prioriteit hebben, komen eerst. Het type PriorityQueue moet een comparable of comparator interface implementeren, waarvan de methoden de prioriteiten van de elementen van de gegevensstructuur bepalen.

//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 een FIFO-wachtrij

De java.util.LinkedList klasse, tijdens de implementatie van java.util.List is een general-purpose uitvoering van java.util.Queue -interface te werken op een FIFO (First In, First Out) principe.

In het onderstaande voorbeeld, met de methode offer() , worden de elementen ingevoegd in de LinkedList . Deze invoegbewerking wordt enqueue . In de while lus hieronder worden de elementen uit de Queue verwijderd op basis van FIFO. Deze bewerking wordt 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() );
}

De uitvoer van deze code is

first element
second element
third element
fourth element
fifth element

Zoals te zien in de uitvoer, wordt het eerste ingevoegde element "eerste element" eerst verwijderd, wordt "tweede element" in de tweede plaats verwijderd enz.

stapels

Wat is een stapel?

In Java zijn Stacks een LIFO-gegevensstructuur (Last In, First Out) voor objecten.

Stack API

Java bevat een Stack API met de volgende 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

Voorbeeld

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");
      }
   }
}

Dit retourneert:

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

Een BlockingQueue is een interface, die een wachtrij is die blokkeert wanneer u probeert de wachtrij te verwijderen en de wachtrij leeg is, of als u items probeert op te halen en de wachtrij al vol is. Een thread die probeert te verwijderen uit een lege wachtrij wordt geblokkeerd totdat een andere thread een item in de wachtrij plaatst. Een thread die probeert een item in een volledige wachtrij te plaatsen, wordt geblokkeerd totdat een andere thread ruimte in de wachtrij maakt, door een of meer items te verwijderen of de wachtrij volledig te wissen.

BlockingQueue-methoden zijn er in vier vormen, met verschillende manieren om bewerkingen af te handelen waaraan niet onmiddellijk kan worden voldaan, maar op een bepaald moment in de toekomst wel kan worden voldaan: de ene genereert een uitzondering, de tweede retourneert een speciale waarde (null of false, afhankelijk van de operatie), de derde blokkeert de huidige thread voor onbepaalde tijd totdat de bewerking kan slagen, en de vierde blokkeert voor slechts een gegeven maximale tijdslimiet voordat het wordt opgegeven.

Een BlockingQueue kan begrensd of ongebonden zijn . Een begrensde BlockingQueue is er een die wordt geïnitialiseerd met initiële capaciteit.

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

Alle aanroepen van de methode put () worden geblokkeerd als de grootte van de wachtrij gelijk is aan de gedefinieerde initiële capaciteit.

Een onbegrensde wachtrij is een wachtrij die zonder capaciteit wordt geïnitialiseerd, eigenlijk standaard geïnitialiseerd met Integer.MAX_VALUE.

Enkele veel voorkomende implementaties van BlockingQueue zijn:

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

Laten we nu eens kijken naar een voorbeeld van 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");

Dit zal afdrukken:

Entry one done
Entry two done

En de thread wordt geblokkeerd na de tweede uitvoer.

Wachtrij-interface

Basics

Een Queue is een verzameling voor het vasthouden van elementen voorafgaand aan de verwerking. Wachtrijen, meestal, maar niet noodzakelijk, bestellen elementen op een FIFO-manier (first-in-first-out).

Hoofd van de wachtrij is het element dat zou worden verwijderd door een oproep om te verwijderen of te pollen. In een FIFO-wachtrij worden alle nieuwe elementen achter in de wachtrij ingevoegd.

De wachtrijinterface

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

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

Elke Queue bestaat in twee vormen:

• men werpt een uitzondering als de operatie mislukt;
• other retourneert een speciale waarde als de bewerking mislukt ( null of false afhankelijk van de bewerking.

Deque

Een Deque is een "dubbele wachtrij", wat betekent dat elementen aan de voor- of achterkant van de wachtrij kunnen worden toegevoegd. De wachtrij kan alleen elementen toevoegen aan de staart van een wachtrij.

De Deque neemt de Queue interface over, wat betekent dat de reguliere methoden behouden blijven, maar de Deque-interface biedt extra methoden om flexibeler te zijn met een wachtrij. De extra methoden spreken echt voor zichzelf als je weet hoe een wachtrij werkt, omdat deze methoden zijn bedoeld om meer flexibiliteit toe te voegen:

Natuurlijk zijn dezelfde opties voor offer , poll en peek beschikbaar, maar ze werken niet met uitzonderingen, maar met speciale waarden. Het heeft geen zin om te laten zien wat ze hier doen.

Elementen toevoegen en openen

Om elementen aan de staart van een Deque toe te voegen, noem je de methode add() . U kunt ook de addFirst() en addLast() gebruiken, die elementen aan de kop en staart van de deque toevoegen.

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

U kunt het element aan het hoofd van de wachtrij bekijken zonder het element uit de wachtrij te halen. Dit gebeurt via de methode element() . U kunt ook de methoden getLast() getFirst() en getLast() gebruiken, die het eerste en laatste element in de Deque . Hier is hoe dat eruit ziet:

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

Elementen verwijderen

Als u elementen uit een deque wilt verwijderen, roept u de methoden remove() , removeFirst() en removeLast() aan. Hier zijn een paar voorbeelden:

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