Wachtrij

Bij de meeste mensen roept het woord "wachtrij" weinig prettige associaties op. Maar vandaag hebben we het over verschillende wachtrijen: Java-wachtrijen. In Java is een wachtrij alles dat de wachtrij- interface overerft , die op zijn beurt de collectie- interface uitbreidt. Dat betekent dat wachtrijen kunnen worden behandeld als verzamelingen.

Wachtrijen in Java ondersteunen twee werkingsprincipes: FIFO en LIFO .

Het FIFO- principe (First In, First Out) regelt een reguliere wachtrij: het eerste element dat aan de wachtrij wordt toegevoegd, verlaat deze als eerste.

Het LIFO- principe (Last In, First Out) beschrijft het gedrag van een stapel: het laatste element dat aan de wachtrij wordt toegevoegd, verlaat deze als eerste. Zo werk je bijvoorbeeld met een pak kaarten: je pakt de kaarten een voor een van de bovenste kaart totdat je de onderkant van het kaartspel bereikt.

De wachtrijhiërarchie in Java ziet er als volgt uit:

Hier kunt u zien dat Queue 3 implementatieklassen heeft: LinkedList , ArrayDeque en PriorityQueue . LinkedList en ArrayDeque erven rechtstreeks niet Queue , maar Deque .

Deque is een interface die is toegevoegd in Java 6. Het bevat verschillende methoden die handig zijn voor wachtrijen en stelt een wachtrij in staat om te functioneren als een dubbele (of bidirectionele) wachtrij. Dat betekent dat het FIFOenLIFOkan zijn.

Een van de twee afstammelingen van de Deque- interface is ArrayDeque . Het ondersteunt een wachtrij met dubbele uiteinden waarmee u elementen van beide uiteinden kunt invoegen en verwijderen. Het is ook een dynamische array die automatisch groter wordt.

Er is ook een klasse PriorityQueue , die een directe afstammeling is van Queue : deze gedraagt ​​zich anders dan de klassen die Deque implementeren .

PriorityQueue is een prioriteitswachtrij die elementen standaard organiseert volgens hun natuurlijke volgorde. Hier gebruikt het sorteren de Comparable- en Comparator- interfaces. Het principe is hetzelfde als bij TreeSet of TreeMap — klassen die de Comparable- interface gebruiken en hun eigen sorteervolgorde hebben.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(String::length));

priorityQueue.add("Andrew");
priorityQueue.add("John");
priorityQueue.add("Rob");

while (!priorityQueue.isEmpty()) {
   System.out.println(priorityQueue.remove());
}

Als u dit voorbeeld uitvoert, ziet u het volgende in de console:

Aangezien we werken met wachtrijen en niet met reguliere collecties, moeten we de elementen uit de lijst verwijderen. Hiervoor gebruiken we deze constructie:

while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.remove());
}

De Deque- interface erft de Queue- methoden en voegt verschillende van zijn eigen interessante methoden toe:

Laten we nu een paar van deze methoden in de praktijk bekijken.

Laten we eerst een element aan een wachtrij toevoegen:

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); // Adds "Apple" to the end of the queue
        deque.addFirst("Orange"); // Adds "Orange" to the front of the queue
        deque.addLast("Pineapple"); // Adds "Pineapple" to the end of the queue
  
        System.out.println(deque);
    

Laten we nu waarden uit een wachtrij halen:

	Deque<String> deque = new ArrayDeque<>();

	deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 

         
        System.out.println("The first element is: "+ deque.getFirst());
                          
        System.out.println("The last element is: " + deque.getLast());
                          
    }
    

Deze code geeft het eerste en laatste element van de wachtrij weer.

         Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pop()); // Get and remove the first element of the queue
System.out.println(deque.poll()); // Get and remove the first element of the queue

System.out.println(deque);
    

Als we deze code uitvoeren, krijgen we:

Het verschil tussen pop() en poll() is dat pop() een NoSuchElementException genereert als de lijst een lege lijst is, maar poll() retourneert null .

Nu gaan we de methoden pollFirst() en pollLast() bekijken .

Deque<String> deque = new ArrayDeque<>();

        deque.add("Apple"); 
        deque.addFirst("Orange"); 
        deque.addLast("Pineapple"); 
        deque.add("Lemon");

System.out.println(deque.pollFirst()); // Get and remove the first element of the queue
System.out.println(deque.pollLast()); // Get and remove the last element of the queue.
System.out.println(deque);
    

Beide methoden retourneren en verwijderen een waarde uit de wachtrij.

Hier is een voorbeeld van het gebruik van de peekFirst() en peekLast() methoden:

Deque<String> friends = new ArrayDeque<>();

friends.add("John");
friends.add("Rob");
friends.add("Greg");
friends.add("Max");
friends.add("Oliver");

System.out.println("The first element is: " + friends.peekFirst());
System.out.println("The last element is: " + friends.peekLast());

System.out.println(friends);
    

Beide methoden retourneren het eerste/laatste element uit de wachtrij en verwijderen ze niet. Als de wachtrij leeg is, wordt null geretourneerd.

Goed gedaan! Vandaag hebben we geleerd hoe we met wachtrijen in Java kunnen werken. Nu weet je hoe je ze in de praktijk kunt gebruiken.