キューデータ構造を実装するJavaプログラム

はじめに

この記事では、Javaでキューデータ構造を実装する方法を詳しく解説します。

キューとは、要素の追加・削除が行われる順序が定められた線形データ構造の一つです。最も基本的な規則は「先入れ先出し（FIFO：First In First Out）」であり、最初に追加された要素が最初に取り出されます。日常的な例でいえば、スーパーマーケットや銀行の待ち行列と同じ仕組みです。

以下に、この記事で扱う処理の具体例を示します。

入力：

入力キュー: [150, 300, 450, 600]

期待される出力：

要素を1つ削除した後のキューの内容: [300, 450, 600]

アルゴリズム

処理の流れは以下のステップのとおりです。

ステップ1 - 開始
ステップ2 - キューを宣言する
ステップ3 - 'offer'メソッドを使って要素を追加する
ステップ4 - キューの内容を表示する
ステップ5 - 'poll'メソッドを使ってキューから要素を削除する
ステップ6 - 'poll'メソッド呼び出し後のキューの要素を表示する
ステップ7 - 結果を表示する
ステップ8 - 終了

例1：標準ライブラリ（LinkedList）を使った実装

まずは、Java標準ライブラリに用意されているQueueインターフェースとLinkedListクラスを利用する方法です。要素の追加にはoffer()メソッド、先頭要素の削除・取得にはpoll()メソッドを使用します。これらのメソッドは、add()やremove()と異なり、失敗時に例外ではなくnullやfalseを返すため、安全にキュー操作を行えます。

import java.util.Queue;
import java.util.LinkedList;
public class Demo {
   public static void main(String[] args) {
      System.out.println("必要なパッケージをインポートしました");
      Queue<Integer> input_queue = new LinkedList<>();
      input_queue.offer(150);
      input_queue.offer(300);
      input_queue.offer(450);
      input_queue.offer(600);
      System.out.println("キューの定義: " + input_queue);
      int removedNumber = input_queue.poll();
      System.out.println("要素を削除した後のキューの内容: " +input_queue);
   }
}

出力

必要なパッケージをインポートしました
キューの定義: [150, 300, 450, 600]
要素を削除した後のキューの内容: [300, 450, 600]

poll()メソッドを呼び出すことで、先頭の要素「150」が取り除かれ、残りの要素[300, 450, 600]だけがキューに残っていることが確認できます。

例2：独自クラスによる実装

次に、標準ライブラリに頼らず、配列をベースにした独自のQueueクラスを実装する例を紹介します。この実装では、以下の基本操作をすべて自前で定義しています。

• enQueue()：キューの末尾に要素を挿入する
• deQueue()：キューの先頭から要素を削除する
• isFull() / isEmpty()：キューが満杯か空かを判定する
• display()：キュー内の全要素を表示する

public class Queue {
   int SIZE = 5;
   int items[] = new int[SIZE];
   int front, rear;
   Queue() {
      front = -1;
      rear = -1;
   }
   boolean isFull() {
      if (front == 0 && rear == SIZE - 1) {
         return true;
      }
      return false;
   }
   boolean isEmpty() {
      if (front == -1)
         return true;
      else
         return false;
   }
   void enQueue(int element) {
      if (isFull()) {
         System.out.println("
キューが満杯です");
      }
      else {
         if (front == -1) {
            front = 0;
         }
         rear++;
         items[rear] = element;
         System.out.println("
要素 " + element + " を挿入しました");
      }
   }
   int deQueue() {
      int element;
      if (isEmpty()) {
         System.out.println("
キューは空です");
         return (-1);
      }
      else {
         element = items[front];
         if (front >= rear) {
            front = -1;
            rear = -1;
         }
         else {
            front++;
         }
         System.out.println("
要素 " +element + " を削除しました");
         return (element);
      }
   }
   void display() {
      int i;
      if (isEmpty()) {
         System.out.println("キューは空です");
      }
      else {
         System.out.println("
キューの要素: ");
         for (i = front; i <= rear; i++)
            System.out.print(items[i] + " ");
      }
   }
   public static void main(String[] args) {
      Queue input_queue = new Queue();
      for(int i = 1; i < 6; i ++) {
         input_queue.enQueue(i * 100);
      }
      System.out.println("キューの定義: " + input_queue);
      input_queue.enQueue(6);
      input_queue.display();
      input_queue.deQueue();
      input_queue.display();
   }
}

出力

要素 100 を挿入しました

要素 200 を挿入しました

要素 300 を挿入しました

要素 400 を挿入しました

要素 500 を挿入しました
キューの定義: Queue@2a139a55

キューが満杯です

キューの要素:
100 200 300 400 500
要素 100 を削除しました

キューの要素:
200 300 400 500

この実装では、容量5の配列に100〜500までの5つの要素を挿入した後、さらに要素を追加しようとして「キューが満杯です」というメッセージが表示されます。また、deQueue()によって先頭の要素「100」が削除され、以降の要素が正しく前に詰められていることがわかります。なお、オブジェクトを直接文字列連結すると「Queue@2a139a55」のようなハッシュ値が表示されるため、実際の開発ではdisplay()メソッドのように内容を明示的に出力するのが一般的です。

まとめ

この記事では、Javaにおけるキューデータ構造の実装方法を2つのアプローチで紹介しました。LinkedListを利用した標準ライブラリ方式は簡潔で実用的であり、日常的な開発ではこちらが推奨されます。一方、配列ベースの独自実装は、キューの内部動作（front/rearポインタの管理、満杯・空の判定など）を深く理解するのに役立ちます。用途に応じて両者を使い分けるとよいでしょう。