キュー
山崎講師データ構造のキューは、データの集合を管理するための一種のデータ構造で、先入れ先出し【FIFO：First-In, First-Out】の方式で要素を追加・削除することができます。キューは、配列と同様にデータを保持しますが、新しい要素はキューの末尾に追加され【enqueue】、要素はキューの先頭から削除されます【dequeue】。
例えば、スーパーマーケットのレジにおいて、先に来た顧客が先にレジに通過するのと同じように、最初にキューに追加された要素が最初に削除されることが保証されます。
キューは以下の用途でよく利用されるデータ構造です。
- ジョブキュー：大量のジョブを処理するシステムでは、キューが使用されます。ジョブは、キューに追加され、処理する準備ができているときに順番に実行されます。
- プリンタキュー：プリンタは、一度に1つのジョブしか処理できないため、プリンタキューが使用されます。印刷ジョブは、キューに追加され、プリンタが使用可能になったときに順番に印刷されます。
- ネットワークパケットキュー：ネットワークでは、パケットを送信する前に、送信キューに追加することが必要です。送信されるパケットは、キューに追加された順序で送信されます。
- イベントキュー：ウェブブラウザやJavaScriptランタイムなどのシステムでは、イベントキューが使用されます。イベントは、キューに追加され、順番に処理されます。これにより、イベントが競合することなく、一度に1つのイベントしか処理されないことが保証されます。
キューは、データの処理順序が重要な場合に、効果的に使用されるデータ構造の1つです。
配列を使ってキューを実装する
＜サンプルプログラム＞
public class Queue {
private int front, rear, size;
private int capacity;
private int[] queueArr;
public Queue(int capacity) {
this.front = 0;
this.rear = -1;
this.size = 0;
this.capacity = capacity;
this.queueArr = new int[capacity];
}
public boolean isEmpty() {
return (size == 0);
}
public boolean isFull() {
return (size == capacity);
}
public void enqueue(int data) {
if (isFull()) {
System.out.println("キューが満杯です");
return;
}
queueArr[++rear] = data;
size++;
System.out.println(data + " をキューに追加しました");
}
public int dequeue() {
if (isEmpty()) {
System.out.println("キューが空です");
return -1;
}
int data = queueArr[front++];
size--;
return data;
}
public int peek() {
if (isEmpty()) {
System.out.println("キューが空です");
return -1;
}
int data = queueArr[front];
return data;
}
public static void main(String[] args) {
Queue queue = new Queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println("キューの先頭の要素: " + queue.peek());
System.out.println(queue.dequeue() + " をキューから取り出しました");
System.out.println(queue.dequeue() + " をキューから取り出しました");
System.out.println("キューの先頭の要素: " + queue.peek());
queue.enqueue(4);
System.out.println(queue.dequeue() + " をキューから取り出しました");
System.out.println("キューの先頭の要素: " + queue.peek());
}
}なお、単にキューを利用するなら以下のjava.util.Queueインタフェースを使うほうが便利です。
java.util.Queueインタフェース
Javaの java.util.Queue インタフェースは、先入先出（FIFO）のデータ構造を提供するためのインタフェースです。
Java.util.Queue インタフェースで使用できる主なメソッドの一覧です。
add(E element)：キューに要素を追加します。
offer(E element)：キューに要素を追加します。
remove()：キューから要素を取り出し、その要素を返します。
poll()：キューから要素を取り出し、その要素を返しますが、キューが空の場合は null を返します。
element()：キューの先頭にある要素を返しますが、その要素を削除しません。
peek()：キューの先頭にある要素を返しますが、その要素を削除しません。キューが空の場合は null を返します。
キューに要素を追加する場合、Queue インタフェースでは、add(E element) メソッドまたは offer(E element) メソッドを使用します。
また、キューから要素を取り出す場合、Queue インタフェースでは、remove() メソッドまたは poll() メソッドを使用します。
java.util.Queue インタフェースにはenqueue() メソッドやdequeue() メソッドはありません。
＜サンプルプログラム＞
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
// 要素をキューに追加
queue.add("akafuku");
queue.add("habutai");
queue.add("kiyome");
// 要素をキューから取り出し
String removed = queue.remove();
System.out.println("取り出した要素: " + removed);
// 要素をキューに追加
queue.offer("abekawa");
// キューの先頭にある要素を取得
String head = queue.element();
System.out.println("先頭の要素: " + head);
// キューから要素を取り出し
String polled = queue.poll();
System.out.println("取り出した要素: " + polled);
// キューから要素を取り出し
String peeked = queue.peek();
System.out.println("先頭の要素: " + peeked);
}
}＜出力結果＞
| 取り出した要素: akafuku 先頭の要素: habutai 取り出した要素: habutai 先頭の要素: kiyome |
練習問題1
ユーザーに5つの整数を入力してもらい、それらをいったんキューに追加して、その後キューから取り出してコンソールに出力するプログラムを作成しなさい。
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class QueueExercise {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// キューを作成する処理を書く
// 5つの整数を入力してキューに追加する処理を書く
// キューから整数を取り出して出力する処理を書く
}
}＜出力結果の例＞
| 5つの整数を入力してください。 10 20 30 40 50 キューから整数を取り出して出力します。 10 20 30 40 50 |
