Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.学ぶ Javaにおけるキューのデータ構造 | Javaにおける高度なデータ構造
Javaデータ構造

bookJavaにおけるキューのデータ構造

メニューを表示するにはスワイプしてください

まずはQueueから始めましょう。セール中の店舗の行列を想像してください。10人が並んでおり、最初の人が店舗の入り口に最も近く、10番目の人が最も遠い位置にいます。最初の人が店舗に入ると、その人は行列から抜け、全体の行列が1人分前に進みます。JavaのQueueも非常に似た原理で動作します。

このようにして、キューのロジックがしっかり考えられたさまざまなプログラムを実装できます。例えば、計画やタスクのボードの実装などです。

まずは、Queueを操作するための基本的なメソッドを見ていきましょう。

Queueはインターフェースであり、すでに馴染みのあるLinkedListクラスがこれを継承しているため、この実装を使用します。

このように、オブジェクトの型としてインターフェースを使用しますが、オブジェクトの実装はLinkedListになります。これは、このオブジェクトの具体的な実装だからです。（インターフェースを基にオブジェクトを生成することはできないことを思い出してください）。

例：

Example.java

Example.java

copy

              
1234

            
// `LinkedList` as implementation of the `List` interface:
List<T> list = new LinkedList<>(); 
// `LinkedList` as implementation of the `Queue` interface:
Queue<T> queue = new LinkedList<>();

このようにして、同じインターフェースのさまざまな実装を利用することで、アプリケーションに高い柔軟性を持たせることができます。

それでは、Queueの操作メソッドに戻りましょう。

メソッド

Queueインターフェースの主なメソッドには、次のものがあります。

  • add(element): 要素をキューに追加し、操作が不可能な場合は例外をスローします；
  • offer(element): 要素をキューに追加し、成功した場合はtrue、失敗した場合はfalseを返します。

これらのメソッドは本質的に同じことを行いますが、重要な違いはofferメソッドの安全性です。不適切な要素が追加された場合、offerメソッドは例外をスローせず、プログラムの実行を停止しません。

ただし、現時点ではこの機能はあまり重要ではありません。通常のQueueには制限がないためです。しかし、BlockingQueueという要素数に制限がある構造では、これらのメソッドに明確な違いが現れます。

例を見てみましょう：

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.add("One");
        queue.add("Two");
        queue.add("Three");
        System.out.println("Queue: " + queue);
    }
}

ご覧のとおり、add() メソッドを使用して キューに収まらない要素 を追加しようとすると、プログラムはエラーをスローし、予期せず実行が終了します。

同じ操作を、より安全なメソッドである offer() で試してみましょう。

Main.java

Main.java

copy

              
1234567891011121314

            
package com.example;

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) {
        BlockingQueue<String> queue = new LinkedBlockingQueue<>(2);
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
    }
}

ご覧のとおり、今回は要素がキューに追加されませんでしたが、例外も発生しませんでした。したがって、エラーを適切に処理したと考えることができます。

例外処理は try-catch のような構造を使って異なる方法で行うこともできますが、それについては後ほど説明します。

削除メソッド

  • remove(): キューの先頭から要素を削除して返し、キューが空の場合は例外をスローします；
  • poll(): キューの先頭から要素を削除して返し、キューが空の場合は null を返します。

これらのメソッドは、まるで最初の人が店に入り、キューから抜ける動作と同じ機能を正確に実行します。ここでFIFO（First In, First Out：先入れ先出し）の原則が適用されます。つまり、キューに最初に追加された要素が最初に削除されることになります。

ここでも、これら2つのメソッドの違いが確認できます。poll() メソッドは remove() メソッドよりもよく使われます。なぜなら、より安全であり、例外をスローしないためです。

例を見てみましょう：

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.remove();
        queue.remove();
        System.out.println("Queue after removal operation: " + queue);
    }
}

ご覧のとおり、プログラムは NoSuchElementException をスローしています。これは、空のキューから要素を削除しようとしたためです。

このような例外を回避するためには、poll() メソッドを使用するのが適切です。

Main.java

Main.java

copy

              
123456789101112131415

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        System.out.println("Queue: " + queue);
        queue.poll();
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

これで、キューから安全に要素を削除でき、空のリストから要素を削除しようとした際にも例外は発生しませんでした。

poll() が null を返す機能は、例えば while() ループ内で利用できます。

例を見てみましょう:

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.poll() != null) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

この方法で、ループを使用してキューからすべての要素を削除可能。

最初にキューに追加された要素が最初に削除されることに注意。 例えば、上記の例では、データが "One" の要素が最初に削除された。

以下にFIFO原則を示す。

Main.java

Main.java

copy

              
123456789101112131415161718

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);         
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

最初と最後の要素を返すメソッドについて説明します。

  • element(): キューの先頭要素を返しますが、削除はしません。キューが空の場合は例外をスローします。
  • peek(): キューの先頭要素を返しますが、削除はしません。キューが空の場合はnullを返します。

peek()メソッドの使用は、信頼性が高く、安全な方法であり、例外発生の回避に役立ちます。

使用例を見てみましょう。

Main.java

Main.java

copy

              
12345678910111213141516

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        System.out.println("Queue: " + queue);
        System.out.println("The first element in the queue: " + queue.peek());
        System.out.println("Queue after the `peek()` method: " + queue);
    }
}

このメソッドは、他のキューメソッドと組み合わせて使用できます。

5つの要素を持つキューがあり、4番目までのすべての要素を削除する必要がある場合、その操作の実装例を見てみましょう。

Main.java

Main.java

copy

              
123456789101112131415161718192021

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (!queue.peek().equals("Four")) {
            queue.poll();
        }
        queue.poll();
        System.out.println("Queue after removal operation: " + queue);
    }
}

peek() メソッドに基づく条件付きループを使用しました。

contains() メソッドを使用すると、このループを大幅に最適化できます。このメソッドは、キューに指定した要素が存在する場合はtrueを返し、存在しない場合はfalseを返します。

上記のコードを改善しましょう:

Main.java

Main.java

copy

              
1234567891011121314151617181920

            
package com.example;

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("One");
        queue.offer("Two");
        queue.offer("Three");
        queue.offer("Four");
        queue.offer("Five");
        System.out.println("Queue: " + queue);
        while (queue.contains("Four")) {
            queue.poll();
        }
        System.out.println("Queue after removal operation: " + queue);
    }
}

ここでは、1つの条件のみを while ループ に設定しています。"Four" 要素まで含めて、すべての要素を正常に削除できました。

1. Javaにおける Queue とは何ですか？

2. JavaコレクションフレームワークでQueueを表すインターフェースはどれですか？

3. offer()インターフェースのQueueメソッドの目的は何ですか？

4. poll()インターフェースのQueueメソッドは何をしますか？

5. Javaのjava.util.concurrentパッケージで有界ブロッキングキューを表すクラスはどれですか？

6. add() メソッドを使用して満杯のキューに要素を追加しようとした場合、どうなりますか？

question mark

Javaにおける Queue とは何ですか？

正しい答えを選んでください

question mark

JavaコレクションフレームワークでQueueを表すインターフェースはどれですか？

正しい答えを選んでください

question mark

offer()インターフェースのQueueメソッドの目的は何ですか？

正しい答えを選んでください

question mark

poll()インターフェースのQueueメソッドは何をしますか？

正しい答えを選んでください

question mark

Javaのjava.util.concurrentパッケージで有界ブロッキングキューを表すクラスはどれですか？

正しい答えを選んでください

question mark

add() メソッドを使用して満杯のキューに要素を追加しようとした場合、どうなりますか？

正しい答えを選んでください

すべて明確でしたか？

どのように改善できますか？

フィードバックありがとうございます！

セクション 2. 章 1

AIに質問する

expand

AIに質問する

ChatGPT

何でも質問するか、提案された質問の1つを試してチャットを始めてください

セクション 2. 章 1
some-alt