Java Language
待ち行列と待ち行列

PriorityQueueの使用法

PriorityQueueはデータ構造体です。 SortedSetと同様に、 PriorityQueueは優先順位に基づいて要素をソートします。優先度の高い要素が優先されます。 PriorityQueueの型は、データ構造の要素の優先順位を決定するメソッドをcomparable 、 comparator comparableまたはcomparatorインタフェースを実装comparable必要があります。

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

FIFOキューとしてのLinkedList

java.util.LinkedListクラスでは、実装しながら、 java.util.Listの汎用的な実装であるjava.util.Queueあまりに動作するインターフェイスFIFO（先入れ先出し）の原則。

以下の例では、 offer()メソッドを使用して、要素をLinkedList挿入します。この挿入操作はenqueueと呼ばれます。以下のwhileループでは、要素はFIFOに基づいてQueueから削除されます。この操作はdequeueと呼ばれます。

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

このコードの出力は次のとおりです。

first element
second element
third element
fourth element
fifth element

出力に見られるように、第1の挿入された要素「第1の要素」が最初に除去され、「第2の要素」が第2の場所などで除去される。

スタック

スタックとは何ですか？

Javaでは、StacksはオブジェクトのLIFO（Last In、First Out）データ構造です。

Stack API

Javaには次のメソッドを含むStack APIが含まれています

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

例

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

戻り値：

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

BlockingQueueはインターフェイスで、キューからデキューしようとするとキューを空にしたり、キューに項目をエンキューしようとしたり、キューがすでにいっぱいになったりするとブロックされます。空のキューからデキューしようとするスレッドは、他のスレッドがアイテムをキューに挿入するまでブロックされます。 1つまたは複数のアイテムをデキューするか、キューを完全にクリアすることによって、他のスレッドがキュー内にスペースを作るまで、フル・キュー内のアイテムをエンキューしようとしているスレッドはブロックされます。

BlockingQueueメソッドは、すぐには満足できない操作を処理するさまざまな方法で、4つの形式で提供されますが、将来のある時点では満足できるかもしれません：1つは例外をスローし、2つ目は特別な値を返します操作が成功するまで現在のスレッドを無期限にブロックし、4番目のブロックは、あきらめる前に所定の最大時間制限のみをブロックします。

BlockingQueue 有界または無制限することができます。有界BlockingQueueは、初期容量で初期化されるものです。

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

キューのサイズが定義されている初期容量と等しい場合、put（）メソッドの呼び出しはすべてブロックされます。

無制限のキューは、容量なしで初期化されるキューで、実際にはデフォルトでInteger.MAX_VALUEで初期化されます。

BlockingQueue一般的な実装は次のとおりです。

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

次に、 ArrayBlockingQueue例を見てみましょう。

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

これは印刷されます：

Entry one done
Entry two done

そして、スレッドは2番目の出力の後にブロックされます。

キューインターフェイス

基本

Queueは、処理前に要素を保持するためのコレクションです。キューは通常、要素をFIFO（先入れ先出し）方式で順序付けしますが、必須ではありません。

キューの先頭は、削除またはポーリングの呼び出しによって削除される要素です。 FIFOキューでは、すべての新しい要素がキューの末尾に挿入されます。

キューインタフェース

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

各Queueメソッドは2つの形式で存在します。

• 操作が失敗した場合は例外がスローされます。
• otherは、操作が失敗した場合に特別な値を返します（操作によってはnullまたはfalse 。

デキ

Dequeは、キューの先頭または末尾に要素を追加できる「 Dequeキュー」です。キューは、キューの末尾に要素を追加することしかできません。

DequeはQueueインタフェースを継承します。つまり、通常のメソッドが残っていることを意味しますが、Dequeインタフェースは、キューに柔軟性を持たせるための追加のメソッドを提供します。キューがどのように機能するかを知っていれば、追加の方法は実際には自分のために発言します。これらのメソッドは柔軟性を高めるためです。

もちろん、 offer 、 poll 、 peekオプションも同じですが、例外はなく、特別な値で動作します。彼らがここで何をしているかを示しても意味がありません。

要素の追加とアクセス

Dequeの末尾に要素を追加するには、 add()メソッドを呼び出します。また、使用することができますaddFirst()とaddLast()両端キューの先頭と末尾に要素を追加する方法を、。

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

要素をキューから取り出すことなく、キューの先頭にある要素を覗くことができます。これは、 element()メソッドを介して行われます。また、 Deque最初と最後の要素を返すgetFirst()メソッドとgetLast()メソッドを使用することもできます。それはどのように見えるかです：

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

要素の削除

両端キューから要素を削除するには、 remove() 、 removeFirst()およびremoveLast()メソッドをremoveLast()ます。いくつかの例があります：

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();