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:
John
Andreas
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:
void addFirst(E obj) | Voegt het obj- element toe aan de voorkant van de wachtrij |
void addLast(E obj) | Voegt het obj- element toe aan het einde van de wachtrij |
E getFirst() | Retourneert het eerste element uit de wachtrij |
E haalLaatste() | Retourneert het laatste element uit de wachtrij |
boolean offerFirst(E obj) | Voegt het obj- element toe aan de voorkant van de wachtrij en retourneert true als het element wordt toegevoegd. Anders retourneert false . |
boolean offerLast(E obj) | Voegt het obj- element toe aan het einde van de wachtrij en retourneert true als het element wordt toegevoegd. Anders retourneert false . |
E pop() | Haalt het eerste element uit de wachtrij en verwijdert het |
ongeldig push(E obj) | Voegt het obj- element toe aan de voorkant van de wachtrij |
E peekFirst() | Retourneert (maar verwijdert niet) het eerste element uit de wachtrij |
E peekLaatste() | Retourneert (maar verwijdert niet) het laatste element uit de wachtrij |
E-peilingEerste() | Retourneert en verwijdert het eerste element uit de wachtrij. Retourneert null als er geen elementen zijn. |
E-peilingLaatste() | Retourneert en verwijdert het laatste element uit de wachtrij. Retourneert null als er geen elementen zijn. |
E verwijderLaatste() | Retourneert en verwijdert het eerste element van de wachtrij. Werpt een uitzondering op als er geen elementen zijn. |
E verwijderEerste() | Retourneert en verwijdert het laatste element van de wachtrij. Werpt een uitzondering op als er geen elementen zijn. |
boolean removeFirstOccurrence(Object obj) | Verwijdert het eerste exemplaar van obj uit de wachtrij |
boolean removeLastOccurrence(Object obj) | Verwijdert het laatste exemplaar van obj uit de wachtrij |
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.
Het laatste element is: Ananas
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:
Appel
[Ananas, Citroen]
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);
Citroen
[Appel, Ananas]
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);
Het laatste element is: Oliver
[John, Rob, Greg, Max, Oliver]
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.
GO TO FULL VERSION