Javaでキューを実装する

基本情報技術者試験に向けてアルゴリズムを勉強しています。今回はJavaでキューを実装してみます。

キューとは

キューでは最初に格納した要素が最初に取り出されます。このような仕組みをFIFO(First In First Out、先入れ先出し)と言います。

キューにデータを格納することをエンキュー(enqueue)と言います。エンキューしたデータは列の一番後ろに追加されます。

42101

キューからデータを取り出すことをデキュー(dequeue)と言います。データを取り出す際には先頭から取り出されます。

42102

実装する

今回はjava.utilパッケージのArrayDequeクラスを参考にして実装します。
まずは、キューのデータ構造を作ります。以下の内容を記述したQueueクラスを作成しましょう。

public class Queue {
    private Object[] data;
    private int front;
    private int rear;
    
    public Queue(int size) {
        data = new Object[size+1];
        front = 0;
        rear = 0;
    }
}

キューは最初に格納したものを最初に取り出します。これを実現するためには次にデータを格納する位置、次にデータを取り出す位置を別々に管理する必要があります。

  • data:実際にデータを格納する配列です。
  • front:次にデータを取り出す位置を管理する変数です。
  • rear:次にデータを格納する位置を管理する変数です。

リングバッファ

下の図では配列の大きさとして4が設定されています。

42201

ここで、もうひとつデータをエンキュー(追加)するとrearは配列の外に外れてしまいこれ以上データを格納することができなくなってしまいます。

42202

これを解決するためにリングバッファを使用します。リングバッファは以下のような環状のデータ構造です。

42203

実際にリングバッファに沿って、offer(データの追加)とpoll(データの取り出し)を実装していきます。offerでは、rear(データを格納する位置)を操作します。pollでは、front(データを取り出す位置)を操作します。

offerメソッドを実装する(データの追加)

キューへのデータの追加を実装します。Queueクラスに以下のメソッドを追記してください。

public boolean offer(Object o) {
    // 配列をリングバッファとして考えた場合、一周回った(満杯)かをチェック
    if ((rear + 1) % data.length == front) {
        return false;
    }
    data[rear] = o;
    // リングバッファの次の格納位置を計算
    rear = (rear + 1) % data.length;
    return true;
} 

キューが満杯か判定を行い、満杯でなければデータを格納します。データを格納後はリングバッファの次の格納位置を計算します。このコードの肝は(rear + 1) % data.lengthです。これは「データの格納位置」と「データの長さ」で余剰を計算しています。「余剰が0」 = 「リングバッファが一周した」ということです。「リングバッファが一周したときのrearの位置」と「frontの位置」が同じときはデータの格納を行うことができません。

例えば、リングバッファのサイズが8で、以下のようにデータが格納されている場合を考えましょう。

43102

このとき、data[7]にデータを格納するとrearの次の位置が0になり、frontとrearが同じ値になります。frontとrearが同じ場合というのは次の2パターンがあります。

  • リングバッファにデータがないとき
  • リングバッファが満杯のとき

これを区別するためにはfront、rear以外に追加の情報が必要になります。この情報を追加すると処理が複雑になるため、今回は次のrearの位置がfrontと同じになる場合は(実際には1つ余裕があるが)キューが一杯であると判定しています。

そのため、キューに格納できる最大数は配列の大きさより1つ小さくなります。コンストラクタで指定サイズより1大きな配列数を確保しているのはこのためです(1大きく確保しておくことで結果として指定されたサイズ分格納できるようにする)。

pollメソッドを実装する(データの取り出し)

キューへのデータの取り出しを実装します。Queueクラスに以下のメソッドを追記してください。

public Object poll() {
    // キューが空
    if (front == rear) {
        return null;
    }
    Object o = data[front];
    data[front] = null;
    // リングバッファの次の先頭位置を計算
    front = (front + 1) % data.length;
    return o;
}

キューが空か判定を行い、空でなかればデータを取り出します。取り出した後は、配列のもともとデータが入っていた位置にnullを入れます。リングバッファなので、rear同様、配列の大きさで割った余りを次の位置として設定します。

toStringメソッドを実装する

動作確認のためにtoStringメソッドを実装します(System.out.println()の内容を調整します)。

rearがfrontの前にある可能性があるため、単純なfor文では記述できません。

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    int i = front;
    while (i != rear) {
        sb.append(data[i]);
        if ((i + 1) % data.length != rear) {
            sb.append(", ");
        }
        // 配列をリングバッファとして考えた場合の次のデータ位置
        i = (i + 1) % data.length;
    }
    sb.append(']');
    return sb.toString();
} 

終了条件は大小の不等号ではなく、「!=」を利用します。例えば、frontが5、rearが2の場合、data[5], data[6], data[7], data[0], data[1]の値が表示されることになります。

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    Queue queue = new Queue(3);
    queue.offer("abc");
    queue.offer("def");
    queue.offer("ghi");

    Object o;
    o = queue.poll();
    System.out.println(o);
    System.out.println(queue);
    o = queue.poll();
    System.out.println(o);
    System.out.println(queue);
    o = queue.poll();
    System.out.println(o);
    System.out.println(queue);
}

動作結果:

abc
[def, ghi]
def
[ghi]
ghi
[]

参考資料
スクールの教科書