Itt a Java Queue felületről fogunk beszélni. Megtudhatja, mi az a Queue adatstruktúra, hogyan jelenik meg a Java-ban, mely metódusok a legfontosabbak az összes sor esetében. Továbbá, hogy a Queue mely implementációi vannak Java nyelven. Ezt követően közelebbről is szemügyre vesszük a legfontosabb megvalósításokat, és példákkal ismerkedünk meg velük.
Sor adatszerkezet
A Queue egy lineáris absztrakt adatstruktúra a műveletek meghatározott sorrendjével – First In First Out (FIFO). Ez azt jelenti, hogy egy elemet (vagy sorba helyezést, sorba helyezést) csak a struktúra végére vehet fel, és egy elemet csak az elejétől vehet fel (sorból vagy eltávolíthat a sorból). Nagyon könnyen elképzelheti a Queue adatstruktúrát. A való életben sorban állásnak vagy ügyfelek sorának tűnik. Azt a vevőt is először szolgálják ki, aki előbb volt. Ha négy ember áll sorban a McDonaldsban vagy máshol, akkor az elsőként beáll a sorba, aki elsőként kapja meg a boltot. Ha jön az új vásárló, ő lesz az 5. a hamburger sorban. Tehát a sorral való munka során új elemek kerülnek a végére, és ha egy elemet akarunk kapni, akkor az elejétől fogva lesz. Ez a klasszikus soradat-szerkezeti munka fő elve.
Sor Java nyelven
A Queue a Java-ban egy interfész. Az Oracle dokumentációja szerint a Queue interfésznek 2 szuperinterfésze, 4 különböző interfésze van, amelyek a sorból öröklődnek, és rendkívül lenyűgöző osztálylistája.
Mit jelent? Először is, a Java Queue a Collection Framework része, és megvalósítja a Collection felületet. Tehát támogatja a Gyűjtemény interfész összes módszerét, például beillesztést, törlést és így tovább. A Queue Iterable felületet valósít meg, amely lehetővé teszi, hogy egy objektum a "for-each loop" utasítás célpontja legyen.
Sormódszerek Java
A Queue számos metódust deklarál. Az interfész metódusaiként a Queue-t megvalósító összes osztályban szerepelniük kell. A legfontosabb várólista módszerek, Java:
Boolean offer() – új elemet szúr be a sorba, ha lehetséges
Logikai add(E e) – új elemet szúr be a sorba, ha lehetséges. Siker esetén igaz értéket ad vissza, és IllegalStateException-t dob, ha nincs szóköz.
Object poll() – lekér és eltávolít egy elemet a fejéből. Null értékkel tér vissza, ha a sor üres.
Object remove() – lekér és eltávolít egy elemet a sor fejéből.
Object peek() – visszakeres, de nem távolít el egy elemet a sor fejéből. Null értékkel tér vissza, ha a sor üres.
Object element() – visszakeres, de nem távolít el egy elemet a sor fejéből.
A Java Queue alinterfészei
A sor interfészt 4 alinterfész örökli – BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E> . Ezeket 3 csoportra oszthatja: Deques, Blocking Queues és Transfer Queues, ahol a BlockingDeque tartozik először. Vessünk egy pillantást ezekre a csoportokra.
Deques
A deque jelentése Kettős sor , és támogatja az adatok hozzáadását vagy eltávolítását az adatok végéből sorként (first-in-first-out/FIFO), vagy a fejből, mint egy másik népszerű adatstruktúra, a verem ( last - in- first-out/LIFO). Deque Interface-t megvalósító osztályok: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.
Várólisták blokkolása
A blokkoló sor olyan sor, amely két esetben blokkol egy szálat:
a szál egy üres sorból próbál elemeket beszerezni
a szál megpróbál elemeket a teljes sorba helyezni
Amikor egy szál egy üres sorból próbál elemeket beszerezni, megvárja, amíg egy másik szál behelyezi az elemeket a sorba. Hasonlóképpen, amikor egy szál megpróbál elemeket egy teljes sorba helyezni, megvárja, amíg egy másik szál kiveszi az elemeket a sorból, hogy szabad helyet kapjon az elemek számára. Természetesen a "teljes várólista" fogalma azt jelenti, hogy a várólista korlátozott méretű, amelyet általában a konstruktor határoz meg. A szabványos blokkolósorok közé tartozik a LinkedBlockingQueue, a SynchronousQueue és az ArrayBlockingQueue. A BlockingQueue interfész implementációs osztályai : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeegy alinterfész a BlockingQueue számára. A BlockingDeque, például a BlockingQueue, egy blokkoló sor, de kétirányú. Tehát örökli a Deque interfész tulajdonságait. Többszálú végrehajtásra van orientálva, nem engedélyez nulla elemet, és a kapacitás korlátozható. A BlockingDeque interfész megvalósításai blokkolják az elemek lekérését, ha a sor üres, és egy elem hozzáadását a sorhoz, ha az tele van.
Átviteli sorok
A TransferQueue interfész kiterjeszti a BlockingQueue felületet. Ellentétben a BlockingQueue interfész várólisták megvalósításával, ahol a szálak blokkolhatók, ha a sor üres (olvasás), vagy ha a sor megtelt (írás), a TransferQueue interfész várólisták blokkolják az írási adatfolyamot, amíg egy másik adatfolyam le nem kéri az elemet. Ehhez használjon átviteli módot. Vagyis a BlockingQueue implementációja garantálja, hogy a Gyártó által létrehozott elemnek a sorban kell lennie, míg a TransferQueue megvalósítása azt, hogy a Termelő elemet a Fogyasztó „fogadja”. A TransferQueue felületnek csak egyetlen hivatalos Java implementációja létezik – a LinkedTransferQueue.
Java sormegvalósítások
Számos osztály valósítja meg a Queue interfészt:
Az AbstractQueue a Queue Java 8 dokumentumok szerint ez az absztrakt osztály néhány Queue művelet alapvető megvalósítását biztosítja. Nem engedélyezi a null elemeket. További 3 hozzáadási, eltávolítási és elemi módszer áll rendelkezésre a Queue classical offer , poll és peek alapján . Azonban kivételeket dobnak ahelyett, hogy hamis vagy nulla visszaadáson keresztül jeleznék a sikertelenséget.
ArrayBlockingQueue – fix méretű FIFO blokkoló sor, amelyet egy tömb támogat
ArrayDeque – a Deque interfész átméretezhető tömb megvalósítása
ConcurrentLinkedDeque – egy korlátlan párhuzamos deque, amely összekapcsolt csomópontokon alapul.
ConcurrentLinkedQueue – korlátlan, szálbiztos sor, amely csatolt csomópontokon alapul.
DelayQueue — egy halom által támogatott időalapú ütemezési sor
LinkedBlockingDeque — a Deque felület egyidejű megvalósítása.
LinkedBlockingQueue – opcionálisan határolt FIFO blokkoló sor, amelyet összekapcsolt csomópontok támogatnak
LinkedList – a List és Deque interfészek duplán linkelt listás megvalósítása. Megvalósítja az összes opcionális listaműveletet, és engedélyezi az összes elemet (beleértve a nullát is)
LinkedTransferQueue – egy korlátlan TransferQueue, amely összekapcsolt csomópontokon alapul
PriorityBlockingQueue – egy halom által támogatott, korlátlan blokkoló prioritású sor
PriorityQueue — a kupac adatszerkezetén alapuló prioritási sor
SynchronousQueue – egy blokkoló sor, ahol minden beszúrási műveletnek meg kell várnia egy másik szál megfelelő eltávolítási műveletét, és fordítva.
A legnépszerűbb megvalósítások a LinkedList, az ArrayBlockingQueue és a PriorityQueue. Nézzük meg őket, és mutassunk néhány példát a jobb megértés érdekében.
LinkedList
A Java LinkedList osztálya List és Deque felületeket valósít meg. Tehát ez a List és a Deque kombinációja, egy kétirányú várólista, amely támogatja az elemek hozzáadását és eltávolítását mindkét oldalról. A Java-ban a LinkedList duplán linked List: a List minden eleme Node-ot hív, és tartalmaz egy objektumot és hivatkozásokat két szomszédos objektumra – az előzőre és a következőre. Azt mondhatja, hogy a LinkedList nem túl hatékony a memóriahasználat szempontjából. Ez igaz, de ez az adatstruktúra hasznos lehet a beszúrási és törlési műveletek teljesítménye esetén. Ez azonban csak akkor történik meg, ha iterátorokat használsz hozzájuk (jelen esetben állandó időben). Az index szerinti hozzáférési műveletek végrehajtása a végétől (amelyik közelebb van) a kívánt elemhez keresve. Ne feledkezzünk meg azonban az elemek közötti hivatkozások tárolásának többletköltségeiről sem. Tehát a LinkedList a Java legnépszerűbb sormegvalósítása. Ez a List és a Deque megvalósítása is, és lehetővé teszi számunkra, hogy kétirányú sort hozzunk létre, amely bármilyen objektumból áll, beleértve a nullát is. A LinkedList elemek gyűjteménye.
A paraméterek nélküli LinkedList() egy üres lista létrehozására szolgál. LinkedList(Collection<? extends E> c) a megadott gyűjtemény elemeit tartalmazó lista létrehozására szolgál, sorrendben, azokat a gyűjtemény iterátora adja vissza.
A LinkedList főbb módszerei:
add(E elem) A megadott elemet hozzáfűzi a lista végéhez;
add(int index, E elem) Beszúrja az elemet a megadott pozícióindexbe;
get(int index) A listában a megadott helyen lévő elemet adja vissza;
remove(int index) Eltávolítja a pozícióindexen lévő elemet;
remove(Object o) Eltávolítja az ?o elem első előfordulását a listából, ha ott van.
remove() Lekéri és eltávolítja a lista első elemét.
addFirst(), addLast() elemet ad a lista elejére/végére
clear() eltávolítja az összes elemet a listából
A include(Object o) igaz értéket ad vissza, ha a lista tartalmazza az o elemet.
Az indexOf(Object o) az o elem első előfordulásának indexét adja vissza, vagy -1-et, ha az nem szerepel a listában.
set(int index, E elem) lecseréli az index pozícióban lévő elemet az elemre
size()A lista elemeinek mennyiségét adja vissza.
A toArray() egy tömböt ad vissza, amely a lista összes elemét tartalmazza az elsőtől az utolsó elemig.
pop(), amely kidob egy elemet a veremből (amelyet a lista képvisel)
push(E e), amely egy elemet a verembe tol (ez a lista képviseli)
Java Queue példa – LinkedList (elemek elhelyezése és eltávolítása különböző módokon)
import java.util.*;
public class LinkedListTest {
public static void main(String args[]){
LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
myLinkedList.add(1);
myLinkedList.add(2);
myLinkedList.add(4);
System.out.println("three added elements: " + myLinkedList);
//put one element into the head, not to the tail:
myLinkedList.push(5);
System.out.println("The new element last in will be the first: " + myLinkedList);
//add new element at the specified position:
myLinkedList.add(4,3);
//put one element into the head, not to the tail (same as push):
myLinkedList.addFirst(6);
System.out.println(myLinkedList);
//now remove element no 2 (it is 1):
myLinkedList.remove(2);
System.out.println(myLinkedList);
//now remove the head of the list
myLinkedList.pop();
System.out.println(myLinkedList);
//remove with the other method
myLinkedList.remove();
System.out.println(myLinkedList);
//and with one more
myLinkedList.poll();
System.out.println(myLinkedList);
}
}
PriorityQueue
A PriorityQueue nem pontosan az a sor a FIFO általános jelentésében. A prioritási sor elemei a természetes sorrendjük szerint, vagy a sorépítéskor biztosított Összehasonlító segítségével kerülnek rendezésre, attól függően, hogy melyik konstruktort használják. Ez azonban nem olyan sorrend, mint amilyen lineáris szerkezetben, például listában lenne (a legnagyobbtól a legkisebbig vagy fordítva). Prioritási sor egy prioritási min halom alapján. A kupac egy bináris fán alapuló adatstruktúra. Minden szülő prioritása nagyobb, mint a gyermekeié. Egy fát teljes binárisnak nevezünk, ha minden szülőnek legfeljebb két gyermeke van, és a szintek kitöltése fentről lefelé halad (ugyanarról a szintről - balról jobbra). A bináris kupac minden alkalommal újraszervezi magát, amikor új elemet adnak hozzá vagy eltávolítanak belőle. Min-heap esetén a legkisebb elem kerül a gyökérbe, függetlenül a beillesztési sorrendtől. A prioritási sor ezen a min-halmon alapul, tehát ha egész számokból álló PriorityQueue-unk van, akkor annak első eleme a legkisebb lesz ezek közül a számok közül. Ha törli a gyökeret, a következő legkisebb gyökér lesz.
A Priority Queue fő módszerei:
A logikai add(object) beszúrja a megadott elemet a prioritási sorba. Siker esetén igazat ad vissza. Ha a sor megtelt, a metódus kivételt dob.
A logikai ajánlat(object) beszúrja a megadott elemet ebbe a prioritási sorba. Ha a sor megtelt, a metódus false értéket ad vissza.
A boolean remove(object) eltávolítja a megadott elem egyetlen példányát a sorból, ha az jelen van.
Az Object poll() lekéri és eltávolítja ennek a sornak a fejét. Null értékkel tér vissza, ha a sor üres.
A void clear() eltávolítja az összes elemet a prioritási sorból.
Az Object element() lekéri ennek a sornak a fejét anélkül, hogy eltávolítaná. A NoSuchElementException parancsot dobja, ha a sor üres.
Az Object peek() lekéri a sor fejét anélkül, hogy eltávolítaná azt. Null értékkel tér vissza, ha a sor üres.
A boolean include(Object o) értéke igaz, ha a sor tartalmazza az o elemet.
Az int size() a sorban lévő elemek számát adja vissza.
Példa a PriorityQueue-ra
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
Queue<Integer> queueL = new LinkedList<>();
for (int i = 5; i > 0; i--) {
queueL.add(i);
}
System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
Queue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 5; i > 0; i--) {
priorityQueue.offer(i);
}
System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
System.out.println("Print PriorityQueue using poll() (by retrieval): " );
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our PriorityQueue using poll() (by retrieval):
1
2
3
4
5
Fontos megérteni, hogy a prioritási sorok bináris kupacokon alapulnak, így nem lineárisan rendezik az elemeket. A gyökértől a levélig minden út rendezett, de a gyökértől eltérő utak nem. Ez azt jelenti, hogy nagyon gyorsan megkaphatja a sor minimális elemét. Ha minden alkalommal törli a fejet, akkor egy rendezett szerkezetet nyomtat.
ArrayBlockingQueue
Az ArrayBlockingQueue belső adatstruktúrájaaz elemek tárolására szolgáló kör alakú tömbön alapul. Ez egy tipikus sor (FIFO) arra az esetre, ha új elemeket szúrnak be a sor végébe, és a kibontási műveletek egy elemet adnak vissza a sor fejéből. A létrehozott sor kapacitása nem módosítható. Egy elem teljes sorba való beillesztésére (behelyezésére) irányuló kísérletek az áramlás blokkolásához vezetnek; az üres sorból való elem felvétele is blokkolja a szálat. Mint korábban említettük, ez a tömb kör alakú. Ez azt jelenti, hogy a tömb első és utolsó eleme logikailag szomszédos. A sor minden alkalommal előreviszi a head és a tail elemek indexeit, amikor az elemet a sorba helyezi vagy eltávolítja a sorból. Ha valamelyik index előrelép a tömb utolsó eleménél, akkor 0-ról indul újra. a sornak nem kell az összes elemet eltolnia a fej eltávolítása esetén (mint a szokásos tömbben). Abban az esetben azonban, ha egy elemet középről távolítunk el (az Iterator.remove segítségével), az elemek eltolódnak. Az ArrayBlockingQueue egy további méltányossági házirendet támogat fair paraméterrel a konstruktorban, hogy elrendelje a termelők (elemek beillesztése) és a fogyasztók (elemek kibontása) várakozási folyamatainak munkáját. Alapértelmezés szerint a megrendelés nem garantált. Ha azonban a sor a "fair == true" beállítással jön létre, az ArrayBlockingQueue osztály megvalósítása FIFO sorrendben biztosítja a szálak elérését. A részvények általában csökkentik a sávszélességet, de csökkentik a volatilitást és megakadályozzák az erőforrások kimerülését.
ArrayBlockingQueue osztályú konstruktorok
Az ArrayBlockingQueue (int kapacitás) fix kapacitású és alapértelmezett hozzáférési házirenddel rendelkező sort hoz létre.
Az ArrayBlockingQueue (int kapacitás, logikai fair) fix kapacitású és meghatározott hozzáférési házirenddel rendelkező sort hoz létre.
Az ArrayBlockingQueue (int kapacitás, logikai tisztességes, Collection <? extends E> c) a hozzáférési házirendben meghatározott fix kapacitású sort hoz létre, és elemeket is tartalmaz a sorba.
Itt van a BlockingQueueExample példa. Létrehozunk egy sort az ArrayBlockingQueue-ből egy elem kapacitással és egy korrekt zászlóval. Két szál indul. Közülük az első, a Producer szál, sorba állítja az üzeneteket az üzenettömbből a put metódus használatával. A második, a fogyasztói szál a take metódussal beolvassa az elemeket a sorból, és megjeleníti a konzolon. Az elemek sorrendje a sor természetes sorrendje.
import java.util.concurrent.*;
public class ArrayBlockingQueueExample {
private BlockingQueue<Integer> blockingQueue;
private final Integer[] myArray = {1,2,3,4,5};
public ArrayBlockingQueueExample ()
{ blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
(new Thread(new Producer())).start();
(new Thread(new Consumer())).start();
}
class Producer implements Runnable
{
public void run() {
try {
int counter = 0;
for (int i=0; i < myArray.length; i++) {
blockingQueue.put(myArray[i]);
if (counter++ < 2)
Thread.sleep(3000);
} blockingQueue.put(-1);
}
catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
class Consumer implements Runnable
{
public void run() {
try {
Integer message = 0;
while (!((message = blockingQueue.take()).equals(-1)))
System.out.println(message);
} catch (InterruptedException e) {
System.err.println(e.getMessage());
}
}
}
public static void main(String[] args) {
new ArrayBlockingQueueExample();
}
}
A kimenet a várólista természetes sorrendben; az első két elem késéssel jelenik meg. A tanultak megerősítése érdekében javasoljuk, hogy nézzen meg egy videóleckét a Java-tanfolyamról
Következtetések
A várólista elemeket szúr be a sor végére, és eltávolítja a sor elejéről. A FIFO koncepciót követi.
A Java Queue a Collection Framework része, és megvalósítja a Gyűjtemény felületet. Tehát támogatja a Gyűjtemény interfész összes módszerét, például beillesztést, törlést és így tovább.
A Queue leggyakrabban használt implementációi a LinkedList, az ArrayBlockingQueue és a PriorityQueue.
Az elsőbbségi sor elemei a természetes sorrendjük szerint, vagy a sorépítéskor biztosított Összehasonlító segítségével kerülnek rendezésre, attól függően, hogy melyik konstruktort használják.
Ha bármilyen null műveletet hajtanak végre a BlockingQueues-on, a NullPointerException kivetődik.
Tehát a sorral való munka során új elemek kerülnek a végére, és ha egy elemet akarunk kapni, akkor az elejétől fogva lesz. Ez a klasszikus soradat-szerkezeti munka fő elve.
Azt mondhatja, hogy a LinkedList nem túl hatékony a memóriahasználat szempontjából. Ez igaz, de ez az adatstruktúra hasznos lehet a beszúrási és törlési műveletek teljesítménye esetén. Ez azonban csak akkor történik meg, ha iterátorokat használsz hozzájuk (jelen esetben állandó időben). Az index szerinti hozzáférési műveletek végrehajtása a végétől (amelyik közelebb van) a kívánt elemhez keresve. Ne feledkezzünk meg azonban az elemek közötti hivatkozások tárolásának többletköltségeiről sem. Tehát a LinkedList a Java legnépszerűbb sormegvalósítása. Ez a List és a Deque megvalósítása is, és lehetővé teszi számunkra, hogy kétirányú sort hozzunk létre, amely bármilyen objektumból áll, beleértve a nullát is. A LinkedList elemek gyűjteménye.
GO TO FULL VERSION