ここでは、Java Queue インターフェイスについて説明します。キューのデータ構造とは何か、Java でどのように表現されるか、すべてのキューにとってどのメソッドが最も重要であるかがわかります。また、Java 言語での Queue の実装についても説明します。その後、最も重要な実装を詳しく見て、例を使って学習します。
![Java キュー インターフェイスとその実装 - 1]()
したがって、キューを操作している間、新しい要素は最後に追加され、要素を取得したい場合は最初から取得されます。これは、古典的なキュー データ構造の動作の主原則です。
どういう意味ですか？まず、Java Queue は Collection Framework の一部であり、Collection インターフェースを実装しています。したがって、挿入、削除などの Collection インターフェイスのすべてのメソッドをサポートします。Queue は Iterable インターフェイスを実装しており、オブジェクトを「for-each ループ」ステートメントのターゲットにすることができます。
![Java university]()
![Java キュー インターフェイスとその実装 - 2]()
LinkedList はメモリの使用という点ではあまり効果的ではないと言う人もいるかもしれません。それは事実ですが、このデータ構造は、挿入および削除操作のパフォーマンスの場合に役立ちます。ただし、これは反復子を使用した場合にのみ発生します (この場合、定数時間で発生します)。インデックスによるアクセス操作は、先頭から末尾（どちらか近い方）に向かって目的の要素を検索して実行されます。ただし、要素間の参照を保存するための追加コストを忘れないでください。したがって、LinkedList は Java で最も人気のあるキュー実装です。これは List と Deque の実装でもあり、null を含む任意のオブジェクトで構成される双方向キューを作成できます。LinkedList は要素のコレクションです。
![Java webinar]()
キューのデータ構造
キューは、特定の順序で操作を実行する線形抽象データ構造、つまり先入れ先出し (FIFO) です。つまり、要素の追加 (またはエンキュー、キューへの投入) は構造の末尾でのみ可能であり、要素の取得 (デキューまたはキューからの削除) はその先頭からのみ行うことができます。Queue のデータ構造は容易に想像できると思います。現実の行列や行列のようなものです。先に来た客も先にサービスを受けることになる。マクドナルドなどで4人並んでいる場合、最初に並んだ人が先に店に入ることができます。新しい客が来た場合、その人はハンバーガーを買うために５番目に並ぶことになる。
したがって、キューを操作している間、新しい要素は最後に追加され、要素を取得したい場合は最初から取得されます。これは、古典的なキュー データ構造の動作の主原則です。
Javaのキュー
Java のキューはインターフェイスです。Oracle のドキュメントによると、キュー インターフェイスには 2 つのスーパーインターフェイス、キューから継承する 4 つの異なるインターフェイス、および非常に印象的なクラスのリストがあります。|
スーパーインターフェース: コレクション<E>、反復可能<E> すべての既知のサブインターフェイス: BlockingDeque<E>、BlockingQueue<E>、Deque<E>、TransferQueue<E> すべての既知の実装クラス: AbstractQueue、ArrayBlockingQueue、ArrayDeque、ConcurrentLinkedDeque、ConcurrentLinkedQueue、DelayQueue、LinkedBlockingDeque、LinkedBlockingQueue、LinkedList、LinkedTransferQueue、PriorityBlockingQueue、PriorityQueue、SynchronousQueue |
キューメソッド Java
キューは多数のメソッドを宣言します。これらは、インターフェイスのメソッドとして、Queue を実装するすべてのクラスで表現される必要があります。最も重要なキュー メソッド (Java):- Boolean offer() – 可能であれば新しい要素をキューに挿入します
- Boolean add(E e) – 可能であれば、新しい要素をキューに挿入します。成功した場合は true を返し、スペースがない場合は IllegalStateException をスローします。
- オブジェクトpoll() – の先頭から要素を取得して削除します。キューが空の場合は null を返します。
- Object Remove() – キューの先頭から要素を取得して削除します。
- Object Peak() – キューの先頭から要素を取得しますが、削除しません。キューが空の場合は null を返します。
- Object element() – キューの先頭から要素を取得しますが、削除しません。
Javaキューのサブインターフェース
キューインターフェイスは、BlockingDeque<E>、BlockingQueue<E>、Deque<E>、TransferQueue<E>の 4 つのサブインターフェイスによって継承されます。これらを Deque、Blocking Queue、および Transfer Queue の 3 つのグループに分割できます。BlockingDeque は最初に 2 つに属します。これらのグループを少し見てみましょう。デク
Deque はダブルエンドキューを意味し、キュー(先入れ先出し/FIFO) としてデータの末尾から、またはスタックと呼ばれる別の一般的なデータ構造 (後入れ先出し) として先頭からの追加または削除をサポートします。先出し/LIFO)。 Deque インターフェイスを実装するクラス: ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque、LinkedList。キューのブロック
ブロッキング キューは、次の 2 つの場合にスレッドをブロックするキューです。- スレッドが空のキューから要素を取得しようとしています
- スレッドは要素を満杯のキューに入れようとしています
転送キュー
TransferQueue インターフェイスは BlockingQueue インターフェイスを拡張します。ただし、キューが空 (読み取り) または満杯 (書き込み) の場合にスレッドがブロックされる BlockingQueue インターフェイス キューの実装とは異なり、TransferQueue インターフェイス キューは、別のストリームが要素を取得するまで書き込みストリームをブロックします。これには転送方法を使用します。言い換えれば、BlockingQueue の実装は、Producer によって作成された要素がキュー内に存在する必要があることを保証しますが、TransferQueue の実装は、Producer 要素が Consumer によって「受信」されることを保証します。TransferQueue インターフェイスの公式 Java 実装は、LinkedTransferQueue の 1 つだけです。Java キューの実装
Queue インターフェースを実装するクラスは数多くあります。- AbstractQueue Queue Java 8 ドキュメントによると、この抽象クラスは一部の Queue 操作の基本実装を提供します。null 要素は許可されません。さらに 3 つのメソッド add、remove、および Queue の古典的なoffer、poll、peakに基づく element がそれぞれあります。ただし、false または null を返して失敗を示すのではなく、例外をスローします。
- ArrayBlockingQueue — 配列をサポートする固定サイズの FIFO ブロッキング キュー
- ArrayDeque — Deque インターフェースのサイズ変更可能な配列実装
- ConcurrentLinkedDeque — リンクされたノードに基づく無制限の同時デキュー。
- ConcurrentLinkedQueue — リンクされたノードに基づく無制限のスレッドセーフ キュー。
- DelayQueue — ヒープを利用した時間ベースのスケジューリング キュー
- LinkedBlockingDeque — Deque インターフェイスの同時実装。
- LinkedBlockingQueue — リンクされたノードによってサポートされる、オプションで制限された FIFO ブロッキング キュー
- LinkedList — List インターフェイスと Deque インターフェイスの二重リンク リストの実装。すべてのオプションのリスト操作を実装し、すべての要素 (null を含む) を許可します。
- LinkedTransferQueue — リンクされたノードに基づく無制限の TransferQueue
- PriorityBlockingQueue — ヒープを基盤とする無制限のブロッキング優先キュー
- PriorityQueue — ヒープ データ構造に基づく優先キュー
- SynchronousQueue — 各挿入操作が別のスレッドによる対応する削除操作を待機する必要があるブロッキング キュー、またはその逆。
リンクリスト
Java の LinkedList クラスは、List インターフェイスと Deque インターフェイスを実装します。つまり、List と Deque を組み合わせた双方向キューであり、両側からの要素の追加と削除をサポートします。Java では LinkedList は二重リンクされた List です。List のすべての要素は Node を呼び出し、オブジェクトと 2 つの隣接するオブジェクト (前と次) への参照を含みます。
LinkedList はメモリの使用という点ではあまり効果的ではないと言う人もいるかもしれません。それは事実ですが、このデータ構造は、挿入および削除操作のパフォーマンスの場合に役立ちます。ただし、これは反復子を使用した場合にのみ発生します (この場合、定数時間で発生します)。インデックスによるアクセス操作は、先頭から末尾（どちらか近い方）に向かって目的の要素を検索して実行されます。ただし、要素間の参照を保存するための追加コストを忘れないでください。したがって、LinkedList は Java で最も人気のあるキュー実装です。これは List と Deque の実装でもあり、null を含む任意のオブジェクトで構成される双方向キューを作成できます。LinkedList は要素のコレクションです。
| LinkedList の詳細: LinkedList Java データ構造 |
LinkedList コンストラクター
パラメータなしのLinkedList() は、空のリストを構築するために使用されます。 LinkedList(Collection<? extends E> c) は、指定されたコレクションの要素を、コレクションのイテレータによって返される順序で含むリストを作成するためのものです。主な LinkedList メソッド:
- add(E element) 指定された要素をこのリストの末尾に追加します。
- add(int index, E element) 指定された位置のインデックスに要素を挿入します。
- get(int index) このリスト内の指定された位置にある要素を返します。
- Remove(int Index) 位置 Index にある要素を削除します。
- Remove(Object o) このリストに最初に出現した ?o 要素が存在する場合、それを削除します。
- Remove() リストの最初の要素を取得して削除します。
- addFirst()、addLast() リストの先頭/末尾に要素を追加します。
- clear() はリストからすべての要素を削除します
- contains(Object o) は、リストに o 要素が含まれる場合に true を返します。
- IndexOf(Object o) は、最初に出現した o 要素のインデックスを返します。それがリストにない場合は -1 を返します。
- set(int index, E element) は、インデックス位置の要素を要素に置き換えます。
- size() リスト内の要素の数を返します。
- toArray() は、リストの最初の要素から最後の要素までのすべての要素を含む配列を返します。
- Pop() はスタック (リストで表される) から要素をポップします。
- Push(E e) 要素をスタックにプッシュします (このリストで表されます)。
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 は、FIFO の一般的な意味でのキューとは正確には異なります。優先キューの要素は、使用されるコンストラクターに応じて、自然な順序に従って、またはキューの構築時に提供されるコンパレーターによって順序付けされます。ただし、これはリストのような線形構造のような順序 (最大から最小へ、またはその逆) ではありません。優先度の最小ヒープに基づく優先度のキュー。ヒープはバイナリツリーに基づいたデータ構造です。各親の優先順位は、その子の優先順位よりも高くなります。各親に 2 つ以下の子があり、レベルの塗りつぶしが上から下 (同じレベル、つまり左から右) に行われる場合、ツリーは完全バイナリと呼ばれます。バイナリ ヒープは、新しい要素が追加または削除されるたびに、それ自体を再編成します。min-heap の場合、挿入順序に関係なく、最小の要素がルートに移動します。優先キューはこの最小ヒープに基づいているため、整数の PriorityQueue がある場合、その最初の要素はこれらの数値の最小値になります。ルートを削除すると、次に小さいものがルートになります。主な PriorityQueue メソッド:
- boolean add(object) は、指定された要素を優先キューに挿入します。成功した場合は true を返します。キューがいっぱいの場合、メソッドは例外をスローします。
- boolean offer(object) は、指定された要素をこの優先キューに挿入します。キューがいっぱいの場合、メソッドは false を返します。
- boolean Remove(object) は、指定された要素の単一のインスタンスが存在する場合、このキューからそれを削除します。
- オブジェクトpoll()は、このキューの先頭を取得して削除します。キューが空の場合は null を返します。
- void clear() は、優先キューからすべての要素を削除します。
- Object element() は、このキューの先頭を削除せずに取得します。キューが空の場合は NoSuchElementException をスローします。
- オブジェクト Peak() は、キューの先頭を削除せずに取得します。キューが空の場合は null を返します。
- boolean contains(Object o) は、キューに o 要素が含まれる場合に true を返します。
- int size() は、このキュー内の要素の数を返します。
PriorityQueueの例
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
配列ブロックキュー
ArrayBlockingQueueの内部データ構造要素を格納するための円形配列に基づいています。これは、新しい要素がキューの末尾に挿入され、抽出操作によってキューの先頭から要素が返される場合の典型的なキュー (FIFO) です。一度作成されたキューの容量は変更できません。満杯のキューに要素を挿入 (投入) しようとすると、フローがブロックされます。空のキューから要素を取得しようとすると、スレッドもブロックされます。前に述べたように、この配列は円形です。これは、配列の最初と最後の要素が論理的に隣接して扱われることを意味します。要素をキューに追加したりキューから削除したりするたびに、キューは先頭要素と末尾要素のインデックスを進めます。何らかのインデックスが配列の最後の要素を進める場合、インデックスは 0 から再開されます。(通常の配列のように) ヘッドを削除する場合、キューはすべての要素をシフトする必要はありません。ただし、要素を途中から削除する場合 (Iterator.remove を使用)、要素はシフトされます。 ArrayBlockingQueue は、コンストラクター内のFairパラメーターを使用して追加の公平性ポリシーをサポートし、プロデューサー (要素の挿入) とコンシューマー (要素の抽出) の待機フローの作業を順序付けします。デフォルトでは、順序は保証されません。ただし、キューが「fair == true」で作成された場合、ArrayBlockingQueue クラスの実装により、FIFO 順序でスレッド アクセスが提供されます。通常、資本は帯域幅を削減しますが、ボラティリティも削減し、リソースの不足を防ぎます。ArrayBlockingQueue クラスのコンストラクター
- ArrayBlockingQueue (int Capacity) は、デフォルトのアクセス ポリシーを使用して固定容量のキューを作成します。
- ArrayBlockingQueue (int Capacity, boolean Fair) は、固定容量と指定されたアクセス ポリシーを持つキューを作成します。
- ArrayBlockingQueue (int Capacity、boolean Fair、Collection <? extends E> c) は、アクセス ポリシーで指定された固定容量のキューを作成し、キュー内の要素を含めます。
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();
}
}
結論
- キューは、キューの最後に要素を挿入し、キューの先頭から要素を削除するために使用されます。これは FIFO の概念に従っています。
- Java Queue は Collection Framework の一部であり、Collection インターフェイスを実装します。したがって、挿入、削除などの Collection インターフェイスのすべてのメソッドをサポートします。
- 最も頻繁に使用される Queue の実装は、LinkedList、ArrayBlockingQueue、および PriorityQueue です。
- 優先キューの要素は、使用されるコンストラクターに応じて、自然な順序に従って、またはキューの構築時に提供されるコンパレーターによって順序付けされます。
- BlockingQueues に対して null 操作が実行されると、NullPointerException がスローされます。
GO TO FULL VERSION