Javaによるアルゴリズムとデータ構造

戻る  

演習4-7の解答

class Gqueue<E> {
    int max;        // キューの容量
    int num;        // 現在のデータ数
    int front;      // 先頭要素カーソル
    int rear;       // 末尾要素カーソル
    E[] que;        // キューの本体
    //...
}

// 演習4-7
// 汎用キュー

class Gqueue<E> {

    //--- 実行時例外：キューが空 ---//
    public class EmptyGqueueException extends RuntimeException {
        public EmptyGqueueException() { }
    }

    //--- 実行時例外：キューが満杯 ---//
    public class OverflowGqueueException extends RuntimeException {
        public OverflowGqueueException() { }
    }

    int    max;        // キューの容量
    int    num;        // 現在のデータ数
    int    front;        // 先頭要素カーソル
    int    rear;        // 末尾要素カーソル
    E[] que;        // キューの本体

    //--- コンストラクタ ---//
    Gqueue(int capacity) {
        num = front = rear = 0;
        max = capacity;
        try {
            que = (E [])new Object[max];    // キュー本体用の配列を生成
        } catch (OutOfMemoryError e) {        // 生成できなかった
            max = 0;
        }
    }

    //--- キューにデータをエンキュー ---//
    E enque(E x) throws OverflowGqueueException {
        if (num >= max)
            throw new OverflowGqueueException();            // キューは満杯
        que[rear++] = x;
        num++;
        if (rear == max)
            rear = 0;
        return x;
    }

    //--- キューからデータをデキュー ---//
    E deque() throws EmptyGqueueException {
        if (num <= 0)
            throw new EmptyGqueueException();            // キューは空
        E x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }

    //--- キューからデータをピーク（先頭データを覗く） ---*/
    E peek() throws EmptyGqueueException {
        if (num <= 0)
            throw new EmptyGqueueException();            // キューは空
        return que[front];
    }

    //--- キューからxを探してインデックス（見つからなければ-1）を返す ---//
    int indexOf(E x) {
        for (int i = 0; i < num; i++)
            if (que[(i + front) % max]  == x)            // 探索成功
                return i + front;
        return -1;                                        // 探索失敗
    }

    //--- キューからxを探して先頭から何番目か（見つからなければ-1）を返す ---//
    int search(E x) {
        for (int i = 0; i < num; i++)
            if (que[(i + front) % max]  == x)            // 探索成功
                return i + 1;
        return -1;                                        // 探索失敗
    }

    //--- キューを空にする ---//
    void clear() {
        num = front = rear = 0;
    }

    //--- キューの容量を返す ---//
    int capacity() {
        return max;
    }

    //--- キューに蓄えられているデータ数を返す ---//
    int size() {
        return num;
    }

    //--- キューは空であるか ---//
    boolean isEmpty() {
        return num <= 0;
    }

    //--- キューは満杯であるか ---//
    boolean isFull() {
        return num >= max;
    }

    //--- キュー内の全データを先頭→末尾の順に表示 ---//
    void dump() {
        if (num <= 0)
            System.out.println("キューは空です。");
        else {
            for (int i = 0; i < num; i++)
                System.out.print(que[(i + front) % max].toString() + " ");
            System.out.println();
        }
    }
}

戻る