Im vorherigen Kapitel haben wir die in ArrayBlockingQueue implementierte blockierende Warteschlange mit Array -Form erklärt.
Die Länge des Arrays muss beim Erstellen bestimmt werden. Wenn die Array -Länge klein ist, wird die ArrayBlocking -Warteschlange leicht blockiert. Wenn die Arraylänge groß ist, verschwendet sie leicht Speicher.
Die Warteschlangendatenstruktur ist natürlich für die Form der verknüpften Listen geeignet, und Linked BlockingQueue ist eine blockierende Warteschlange, die mit verknüpften Listen implementiert wird.
1. Linked List Implementierung
1.1 Knotenin interne Klasse
/ *** Der Knoten der verknüpften Liste wird auch verwendet, um eine einseitige verlinkte Liste zu implementieren. // Zeigen Sie auf den nächsten Knoten des verlinkten Listenknotens <E> als nächstes; Knoten (e x) {item = x; }}Es gibt eine Variable E, die Daten speichert, und es gibt eine Variable im nächsten Referenz, die auf den nächsten Knoten zeigt. Es kann die einfachste Einwegliste implementieren.
1.2 So implementieren Sie die Linkliste
/ *** Sein nächster Punkt zum Warteschlangenkopf, und dieser Knoten speichert keine Daten*/ transienten Knoten <e> Kopf; / *** Warteschlangenschwanzknoten*/ privater transienter Knoten <e> letztes;
Um eine verknüpfte Liste zu implementieren, muss es zwei Variablen geben, einer repräsentiert den Kopf der verknüpften Liste und der andere die letzte der verknüpften Liste. Sowohl Kopf als auch Letzte werden initialisiert, wenn das LinkedBlocking -Objekt erstellt wird.
last = head = neuer Knoten <e> (null);
Beachten Sie, dass hier ein kleiner Trick verwendet wird. Der Kopfknoten der verknüpften Liste speichert keine Daten. Der nächste Knoten zeigt, dass die ersten Daten in der verknüpften Liste wirklich gespeichert werden. Das letzte am Ende der verlinkten Liste speichert tatsächlich die letzten Daten in der verlinkten Liste.
1.3 Knoten einfügen und löschen
/ *** Knoten in den Schwanz der Warteschlange einfügen*/ private void Enqueue (Knoten <e> node) {// putlock.isheldByCurrentThread (); // Der aktuelle Thread muss das Putlock -Sperre erhalten haben // Die nächste Referenz des ursprünglichen Warteschlangen -Schwanzknotens auf den neuen Knotenknoten veröffentlichen und dann den Knotenknoten auf den Tail -Knoten der Warteschlange letzt einstellen // Dies realisiert, dass das Einfügen von Knoten in die Heck der Warteschlange letztendlich.Next = Knoten; }Es ist sehr einfach, einen Knoten am Ende der verlinkten Liste einzufügen. Zeigen Sie den nächsten Knoten der ursprünglichen Warteschlange auf den neuen Knotenknoten und weisen Sie den neuen Knotenknoten dem letzten Knoten am Ende der Warteschlange zu. Dies ermöglicht das Einsetzen eines neuen Knotens.
// den Warteschlangenkopfknoten entfernen und die gelöschten Knotendaten private e dequeue () {// Takelock.isheldByCurrentThread () assert; // Der aktuelle Thread muss das Takelock -Schloss erhalten haben // Head assert.item == null; Knoten <e> H = Kopf; // Die Daten des ersten Elements in der Warteschlange werden im ersten Knotenknoten <e> first = h.Next gespeichert; H.Next = H; // Helfen Sie GC // Das Einstellen des neuen Kopfwerts entsprechen dem Löschen des ersten Knotens. Weil der Kopfknoten selbst Daten nicht zuerst speichert; // die Daten des Warteschlangenheaders e x = zuerst.Item; // Entfernen Sie zuerst die Originaldaten.Item = null; Rückkehr x; }Beachten Sie, dass der Kopf nicht der Header ist, der nächste Punkt zum Header, daher ist es sehr einfach, den Header zu löschen, der den Kopf dem Kopf zuzuweisen und dann die Daten des ursprünglichen Kopfes zurückzugeben.
Achten Sie beim Löschen auf die Situation, in der die verknüpfte Liste leer ist. Der Wert von Head.Next wird unter Verwendung der Enqueue -Methode hinzugefügt. Wenn Head.Next == zuletzt ist, bedeutet dies, dass das letzte Element gelöscht wurde. Wenn Head.Next == NULL ist, kann es nicht gelöscht werden, da die verknüpfte Liste bereits leer ist. Hier gibt es kein Urteil, da das Urteil an der Stelle vorgenommen wurde, an der die Dequeue -Methode aufgerufen wird.
2. Synchrone Lock Reentrantlock und Zustand
Da die blockierende Warteschlange blockiert und gewartet werden muss, wenn die Warteschlange leer ist und die Warteschlange voll ist, sind zwei Bedingungen natürlich erforderlich. Um die Sicherheit der Parallelität mit mehreren Threads zu gewährleisten, ist eine Synchronisationsschloss erforderlich. Dies wurde in ArrayBlockingQueue gesagt.
Hier werden wir über die verschiedenen Dinge über Linked BlockingQueue sprechen.
/ ** Exklusives Schloss, das zur Bewältigung von Parallelitätsproblemen beim Einfügen von Warteschlangenvorgängen verwendet wird, dh Put und Angebot von Operationen*/ Private Final Reentrantlock Putlock = new Reentrantlock (); / ** Bedingung Bedingung, mit der die Warteschlange nicht zufrieden ist, sie wird durch Putlock -Schloss erzeugt*/ private endgültige Bedingung Notfull = putlock.newcondition (); / ** Exklusives Schloss, das zur Bewältigung von Parallelitätsproblemen beim Löschen von Warteschlangenkopfvorgängen verwendet wird, d. H. Take and Poll Operations*/ Private Final Reentrantlock Takelock = new Reentrantlock (); / ** Bedingung Bedingung, dass die Warteschlange nicht leer ist. Sie verwendet die private endgültige Bedingung, die von Takelock Lock erzeugt wird.
2.1 Putlock und Takelock
Wir fanden zwei verwendete Schlösser:
Laut der obigen Erklärung kann es operiert werden, Elemente gleichzeitig einzuführen und zu löschen. Wird es also kein Problem geben?
Lassen Sie es uns im Detail analysieren. Für Warteschlangen sind Operationen in drei Typen unterteilt:
Verwenden Sie daher das Putlock -Schloss, um die letzte variable sicher zu halten, und verwenden Sie die Takelock -Schloss, um den Kopf variabel zu schützen.
Für alle Zählvariablen, die an der Anzahl der Elemente in der Warteschlange beteiligt sind, wird Atomicinger verwendet, um Probleme mit der Parallelität sicherzustellen.
/ ** Verwenden Sie hier die Anzahl der Elemente in der Warteschlange, um die AtomicInteger -Variable zu gewährleisten, um die Sicherheitsprobleme von Parallelität zu gewährleisten.
2.2 Nichtsvoll und notwendig
2.3 Kontrollprozess
Beim Einfügen eines Elements:
Beim Löschen von Elementen:
Beachten Sie auch, dass das Signal und die Warteverfahren auf den Zustand der Bedingungen aufgerufen werden müssen, wenn ein Schloss erfasst wird. Daher gibt es SignalNotEmpty- und SignalNotful -Methoden:
/*** Weck den Thread auf, der unter dem notwendigen Zustand wartet, dh beim Entfernen des Warteschlangenheaders der Faden, der als leer und gezwungen ist zu warten. * Beachten Sie, dass hier die Methode Takelock. * Wenn ein Element in die Warteschlange eingefügt wird (d. H. Put- oder Angebotsbetrieb), ist die Warteschlange definitiv nicht leer und diese Methode wird aufgerufen. */ private void signnotEmpty () {Final Reentrantlock takelock = this.takelock; takelock.lock (); try {Notimpty.Signal (); } endlich {takelock.unlock (); }} /*** Weck den Thread auf, der unter der nicht abfängenden Bedingung wartet, dh wenn das Element am Ende der Warteschlange hinzugefügt wird, ist der Thread, der voll und zum Warten gezwungen ist. * Beachten Sie, dass die entsprechende Sperre erhalten werden muss, da die Methode der Signalmethode der Bedingung aufgerufen werden muss, so dass die Methode Putlock.lock () hier aufgerufen wird */ private void signalNotful () {Final Reentrantlock putlock = this.putlock; putlock.lock (); try {Notfull.Signal (); } endlich {putlock.unlock (); }}3.. Elementmethode einfügen
public void put (e e) löscht InterruptedException {if (e == null) aus neu nullPointerexception (); // Die Anzahl der Elemente vor dem Insertionsoperation int c = -1 aufzeichnen; // Erstellen Sie einen neuen Knotenknoten <E> node = New Knode <E> (e); endgültiger reentantlock putlock = this.putlock; endgültiger atomicinteger count = this.count; putlock.lockinterruptible (); Versuchen Sie {// Geben Sie an, dass die Warteschlange voll ist, und dann müssen Sie die nichtful.await -Methode aufrufen, um den aktuellen Thread zu warten (count.get () == Kapazität) {Notfull.await (); } // Ein neues Element Enqueue (Knoten) einfügen; // 1 zur Anzahl der Elemente in der aktuellen Warteschlange 1 hinzufügen und die Anzahl der Elemente zurückgeben, bevor 1. C = count.getandIncrement () hinzugefügt wird; // C + 1 <Kapazität bedeutet, dass die Warteschlange nicht voll ist und der Thread, der auf den Insertionsvorgang wartet, erweckt wird, wenn (c + 1 <Kapazität) nicht fehlerhaft () (); } endlich {putlock.unlock (); } // c == 0 bedeutet, dass die Warteschlange vor dem Einsetzen leer ist. Wenn die Warteschlange zu einem Element leer ist, das platziert wird, weckt // den Gewinde auf das Löschen und verhindern, dass die häufige Erfassung von Takelock -Sperren die Leistung verhindern, wenn (c == 0) significnotEmpty (); }Wenn Sie die Put -Methode als Beispiel übernehmen, ist der allgemeine Prozess derselbe wie zuvor. Hier ist ein sehr seltsamer Code. Wenn das Element eingefügt wird und feststellen, dass die Warteschlange nicht voll ist, rufen Sie Notfull.Signal () an, um den Thread aufzuwecken, der auf die Einfügung wartet.
Jeder ist sehr verwirrt. Im Allgemeinen sollte diese Methode in das Löschelement (Take Series-Methode) platziert werden, da die Warteschlange, wenn wir ein Element löschen, unterbewegt sein muss, und dann die Methode Notfo.Signal () aufzurufen, um den Thread aufzuwecken, der auf das Einsetzen wartet.
Dies geschieht hauptsächlich hier, da beim Aufrufen der Signalmethode zuerst die entsprechende Schloss erhalten werden muss. Das bei der Methode Take Series verwendete Schloss ist Takelock. Wenn Sie die Methode Notful.Signal () anrufen möchten, müssen Sie zuerst das Putlock -Schloss erhalten. Dies führt dazu, dass die Leistung abnimmt, sodass eine andere Methode angewendet wird.
4. Löschen Sie das Queue -Header -Element
public e take () wirft InterruptedException {e x; int c = -1; endgültiger atomicinteger count = this.count; endgültig neueintretlock takelock = this.takelock; takelock.lockinterruptisle (); Versuchen Sie {// bedeutet, dass die Warteschlange leer ist. Dann müssen Sie die motiOnty.aait -Methode aufrufen, um den aktuellen Thread zu warten, während (count.get () == 0) {notempely.await (); } // Löschen Sie das Element der Warteschlangenheader und geben Sie es zurück x = dequeue (); // Die Anzahl der aktuellen Warteschlangen zurückgibt und dann die Anzahl der Warteschlangen nach einem c = count.getandDdecrement () subtrahieren; // c> 1 bedeutet, dass die Warteschlange nicht leer ist, sodass sie den Faden aufweckt, der auf die Löschvoropie wartet, wenn (c> 1) notieren.Signal (); } endlich {takelock.unlock (); } /*** c == Kapazität bedeutet, dass die Warteschlange vor dem Löschvorgang voll ist. * Weck den Thread auf, der auf das Einsetzen nur dann wartet, wenn ein Element aus der vollständigen Warteschlange gelöscht wird Rückkehr x; }Warum wird die motiOmpty.Signal () -Methode genannt, vergleichen Sie unsere Erläuterung in der Methode des Einfügenelements.
5. Ansicht der Warteschlangenheader -Elemente
// Das Warteschlangenheader -Element public e peek () {// Die Warteschlange ist leer, null if (count.get () == 0) return null; endgültig neueintretlock takelock = this.takelock; takelock.lock (); Versuchen Sie {// den Queue -Header -Knoten erster Knoten <e> first = head.Next; // First == NULL bedeutet, dass die Warteschlange leer ist, null zurück, wenn (zuerst == null) NULL zurückgeben; sonst // Zurück das Warteschlangenheader -Element return zuerst.item; } endlich {takelock.unlock (); }}Zeigen Sie das Element des Warteschlangenheaders an, an dem der Kopfknoten beteiligt ist, sodass Takelock -Schloss verwendet werden muss.
Vi. Andere wichtige Methoden
6.1 Methode (Objekt O) entfernen
// Entfernen Sie das angegebene Element aus der Warteschlange O public boolean entfernen (Objekt o) {if (o == null) return false; // Da es nicht das Listen -Header -Element löschen soll, sind die beiden Variablenkopf und zuletzt involviert, // Putlock und Takelock müssen mit vollständiger () gesperrt werden. Versuchen Sie {// Die gesamte Warteschlange durchqueue, P repräsentiert den aktuellen Knoten, und Trail repräsentiert den vorherigen Knoten des aktuellen Knotens //, da es sich um eine einseitige Liste der verlinkten Liste handelt, müssen zwei Knoten für (Knoten <e> Trail = Head, P = Trail.Next; p! (O.Equals (P.Item)) {Unlink (P, Trail); zurückkehren; }} return false; } endlich {volumunlock (); }}Löschen Sie das angegebene Element aus der Liste. Da sich das gelöschte Element nicht unbedingt im Kopf der Liste befindet, gibt es möglicherweise zwei Variablenkopf und dauern, sodass Sie gleichzeitig sowohl Putlock- als auch Takelock -Schlösser verwenden müssen. Da es sich um eine einseitige gelinkte Liste handelt, ist ein Hilfsvariablen-Trail erforderlich, um den vorherigen Knoten so aufzuzeichnen, dass der aktuelle Knoten P gelöscht werden kann.
6.2 Verknüpfen (Knoten <e> p, Knoten <e> Trail) Methode
// Löschen Sie den aktuellen Knoten P, und der Trail repräsentiert den vorherigen Knoten des P -void -Unglinkes (Knoten <e> p, Knoten <e> Trail) {// Die Daten des aktuellen Knotens auf null p.Item = null setzen; // Dies löscht den Knoten P Trail.Next = P.Next; // Wenn der Knoten P die letzte der Warteschlange ist und gelöscht wird, stellen Sie den Trail auf letztes fest, wenn (last == p) last = Trail; // Die Anzahl der Elemente nach eins subtrahieren. Wenn die ursprüngliche Warteschlange voll ist, rufen Sie die nicht fehlerhafte Methode auf. }Um einen Knoten P in der verknüpften Liste zu löschen, müssen Sie nur den nächsten der vorherigen Knotenspur von P auf den nächsten Knoten als nächstes des Knotens pweisen.
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.