前の章では、配列フォームを使用して、ArrayBlockingQueueに実装されているブロッキングキューについて説明しました。
アレイの長さは、作成時に決定する必要があります。配列の長さが小さい場合、配列ブロッキングキューキューは簡単にブロックされます。配列の長さが大きい場合、メモリを簡単に無駄にします。
キューデータ構造は、リンクされたリストの形式に自然に適しており、LinkedBlockingQueueはリンクされたリストを使用して実装されたブロッキングキューです。
1。リンクリストの実装
1.1ノード内部クラス
/ ***リンクリストのノードは、一元配置リンクリストを実装するためにも使用されます*/ staticクラスノード<e> {e item; //リンクリストノードの次のノードを指します<e>次へ。ノード（e x）{item = x; }}データを保存する変数Eがあり、次のノードを指す変数次の参照があります。最も単純な一方向リストを実装できます。
1.2リンクリストを実装する方法
/ ***キューヘッドの次のポイントで、このノードはデータを保存しません*/ Transient Node <e> head; / ***キューテールノード*/プライベートトランジェントノード<e> last;
リンクされたリストを実装するには、2つの変数が必要です。1つはリンクリストのヘッドを表し、もう1つはリンクリストの最後を表します。 LinkedBlockingQueueオブジェクトが作成されると、頭と最後の両方が初期化されます。
last = head = new node <e>（null）;
ここでは小さなトリックが使用されていることに注意してください。リンクリストのヘッドノードはデータを保存しません。次のノードは、リンクリストに最初のデータを真に保存することを指します。リンクリストの最後の最後は、実際に最後のデータをリンクリストに保存します。
1.3ノードを挿入して削除します
/ ***キューのテールにノードを挿入*/ private void enqueue（node <e> node）{// assert putlock.isheldbycurrentthread（）; //現在のスレッドは、PutLockロックを取得している必要があります//元のキューテールノードの次の参照を新しいノードノードに向けてから、最後のキューのテールノードにノードノードを設定してください。 }リンクリストの最後にノードを挿入するのは非常に簡単です。元のキューの次のノードを新しいノードノードに最後にポイントし、キューの最後の最後のノードに新しいノードノードを割り当てます。これにより、新しいノードを挿入できます。
//キューヘッドノードを削除し、削除されたノードデータプライベートe dequeue（）{// assert takelock.isheldbycurrentthread（）; //現在のスレッドは、Takelock Lockを取得している必要があります// assert head.item == null; node <e> h = head; //キュー内の最初の要素のデータは、最初のノードノード<e> first = h.nextに保存されます。 h.next = h; // GCをヘルプ//新しいヘッド値を設定することは、最初のノードの削除と同等です。ヘッドノード自体がデータhead = firstを保存しないためです。 //キューヘッダーe x = first.itemのデータ; //最初に元のデータを削除します。Item= null; xを返します。 }ヘッドはヘッダーではなく、ヘッダーの次のポイントであるため、ヘッダーを削除するのは非常に簡単です。ヘッダーはヘッドを割り当てて、元のhead.nextノードのデータを返します。
削除するときは、リンクされたリストが空の状況に注意してください。 head.nextの値は、Enqueueメソッドを使用して追加されます。 head.next ==最後に、最後の要素が削除されたことを意味します。 head.next == nullの場合、リンクされたリストがすでに空であるため削除することはできません。ここでは、Dequeueメソッドが呼び出される場所で判断がなされたため、判断はありません。
2。同期ロックreentrantLockと条件
ブロッキングキューをブロックして待機する必要があるため、キューが空で、キューがいっぱいになったときに待機する必要があるため、2つの条件が自然に必要です。マルチスレッドの並行性の安全性を確保するためには、同期ロックが必要です。これは、arrayblockingqueueで言われています。
ここでは、LinkedBlockingQueueのさまざまなことについて説明します。
/ **キュー操作の挿入の並行性の問題を処理するために使用される排他的ロック、つまり、操作を提供して提供する*/プライベート最終REENTRANTLOCK PUTLOCK = NEW REENTRANTLOCK（）; / **キューが満たされていない状態、それはputlock lockによって生成されます*/プライベート最終条件notfull = putlock.newcondition（）; / **キューヘッド操作の削除の並行性の問題を処理するために使用される排他的ロック、つまりテイクアンドポーリング操作*/プライベート最終REENTRANTLOCK TAKELOCK = new ReentrantLock（）; / **条件キューが空でないという条件は、Takelock Lockによって生成されたプライベート最終条件を使用します*/プライベート最終条件Notempty = takelock.newcondition（）;
2.1 Putlock and Takelock
使用されている2つのロックが見つかりました。
上記の声明によると、要素を同時に挿入して削除する操作がある可能性があるため、問題はありませんか？
詳細に分析しましょう。キューの場合、操作は3つのタイプに分けられます。
したがって、PutLockロックを使用して最後の変数を安全に保ち、Takelockロックを使用してヘッド変数を安全に保ちます。
キュー内の要素の数に関与するすべてのカウント変数について、AtomicIntegerを使用して同時実行セキュリティの問題を確保します。
/ **キュー内の要素の数は、こちらのAtomicInteger変数を使用して、同時環境セキュリティの問題を確保する*/ private final AtomicInteger count = new AtomicInteger（）;
2.2顕著で無名
2.3制御プロセス
要素を挿入するとき：
要素を削除する場合：
また、ロックが取得されたときに、信号と待ち合わせ方法を呼び出す必要があることに注意してください。したがって、signalnotemptyおよびsignalnotfullメソッドがあります。
/*** Notemptyの状態で待っているスレッドを目覚めさせます。つまり、キューヘッダーを削除するときに、空で待機を余儀なくされていることがわかったスレッドです。 *条件の信号方法を呼び出すには、対応するロックを取得する必要があるため、takelock.lock（）メソッドがここで呼び出されることに注意してください。 *要素がキューに挿入された場合（つまり、プットまたはオファー操作）、キューは間違いなく空ではなく、この方法は呼び出されます。 */ private void signalnotempty（）{final reentrantlock takelock = this.takelock; takelock.lock（）; try {notempty.signal（）; }最後に{takelock.unlock（）; }} /***顕著な状態の下で待っているスレッドを起動します。つまり、キューの最後に要素が追加されたときに、満腹で待機を余儀なくされます。 *条件の信号方法を呼び出すには、対応するロックを取得する必要があるため、ここでputlock.lock（）メソッドが呼び出されることに注意してください*要素（つまり、テイクまたはポーリング操作）がキューで削除された場合、キューは間違いなく不満になり、このメソッドを呼び出します。 */ private void signalnotfull（）{final reentrantlock putlock = this.putlock; putlock.lock（）; try {notfull.signal（）; }最後に{putlock.unlock（）; }}3.要素メソッドを挿入します
public void put（e e）throws arturtedexception {if（e == null）throw new nullpointerexception（）; //挿入操作の前に要素の数を記録int c = -1; //新しいノードnode <e> node = new node <e>（e）を作成します。 final reentrantlock putlock = this.putlock; final atomicinteger count = this.count; putlock.LockIntructibly（）; try {//キューがいっぱいであることを示します。その後、notfull.awaitメソッドを呼び出して、現在のスレッドを待機させる必要があります（count.get（）== capuation）{notfull.await（）; } //新しい要素Enqueue（ノード）を挿入します。 //現在のキュー内の要素の数に1を追加し、1。c= count.getandincrement（）を追加する前に要素の数を返します。 // c + 1 <容量とは、キューがいっぱいではないことを意味し、（c + 1 <容量）notfull.signal（）; }最後に{putlock.unlock（）; } // c == 0は、挿入前にキューが空であることを意味します。配置されている要素にキューが空になったら、//削除を待っているスレッドを起動します}PUTメソッドを例にとると、一般的なプロセスは以前に紹介したのと同じです。これが非常に奇妙なコードです。要素が挿入されたら、キューがいっぱいでないことがわかった場合は、notfull.signal（）を呼び出して、挿入を待っているスレッドを起動します。
誰もがとても混乱しています。一般的に言えば、このメソッドは削除要素（シリーズメソッドを取得）に配置する必要があります。要素を削除するときは、キューが完全に完全に行われ、notfull.signal（）メソッドを呼び出して、挿入を待っているスレッドを起動する必要があるためです。
これは主にここで行われます。信号メソッドを呼び出すとき、対応するロックを最初に取得する必要があるためです。テイクシリーズメソッドで使用されるロックはTakelockです。 notfull.signal（）メソッドを呼び出す場合は、最初にputlockロックを取得する必要があります。これにより、パフォーマンスが低下するため、別の方法が使用されます。
4.キューヘッダー要素を削除します
public e take（）throws arturnedexception {e x; int c = -1; final atomicinteger count = this.count; final reentrantlock takelock = this.takelock; takelock.LockIntructibly（）; try {//キューが空であることを意味します。その後、notempty.awaitメソッドを呼び出して、現在のスレッドを待機させる必要があります（count.get（）== 0）{notempty.await（）; } //キューヘッダー要素を削除し、x = dequeue（）を返します。 //現在のキューの数を返し、次にキューの数を1つのc = count.getanddecrement（）で差し引きます。 // c> 1は、キューが空でないことを意味するため、（c> 1）notempty.signal（）; }最後に{takelock.unlock（）; } /*** c ==容量とは、削除操作の前にキューがいっぱいであることを意味します。 *完全なキューから要素が削除された場合にのみ挿入を待っているスレッドを起動します* Putlockロックの頻繁な取得を防ぎ、パフォーマンスを消費します*/ if（c ==容量）signalnotfull（）; xを返します。 }なぜnotempty.signal（）メソッドが呼び出されるのか、挿入要素メソッドの説明を比較してください。
5.キューヘッダー要素を表示します
//キューヘッダー要素を表示public epeek（）{//キューは空です。 final reentrantlock takelock = this.takelock; takelock.lock（）; try {//キューヘッダーノードfirst node <e> first = head.next; // first == nullとは、キューが空であることを意味します。 else // queueヘッダー要素を返すfirst.item; }最後に{takelock.unlock（）; }}ヘッドノードを含むキューヘッダー要素を表示するため、Takelockロックを使用する必要があります。
vi。その他の重要な方法
6.1削除（オブジェクトO）メソッド
//キューから指定された要素を削除o public boolean remove（object o）{if（o == null）return false; //リストヘッダー要素を削除しないため、2つの変数ヘッドと最後が関与するため、// putlockとtakelockを完全にロックする必要があります（）。 try {//キュー全体をトラバースし、pは現在のノードを表し、トレイルは一方向のリンクリストであるため、現在のノードの前のノードを表します。 （o.equals（p.item））{loonink（p、trail）; trueを返します。 }} falseを返します。 }最後に{fullyunlock（）; }}リストから指定された要素を削除します。削除された要素は必ずしもリストのヘッドにあるわけではないため、2つの変数が頭と最後にある可能性があるため、PutlockロックとTakelockロックの両方を同時に使用する必要があります。これは一方向のリンクリストであるため、現在のノードPを削除できるように、前のノードを記録するために補助変数トレイルが必要です。
6.2 Unlink（node <e> p、node <e> trail）メソッド
//現在のノードPを削除すると、トレイルはpoid lonink（node <e> p、node <e> trail）の前のノードを表します{//現在のノードのデータをnull p.item = nullに設定します。 //これにより、ノードP Trail.next = p.next;が削除されます。 //ノードPがキューの最後の最後であり、削除されている場合、トレイルをlast if（last == p）last = trailに設定します。 //元のキューがいっぱいの場合、要素の数を1つずつ減算し、notfull.signal（）メソッドを呼び出します//実際には、これは判断なしに直接呼ばれます。 }リンクリストのノードPを削除するには、Pの以前のノードトレイルの次のノードトレイルを次のノードPの次のノードPに向けるだけでいい。
上記はこの記事のすべての内容です。みんなの学習に役立つことを願っています。誰もがwulin.comをもっとサポートすることを願っています。