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

戻る  

演習4-6の解答

一般にデックと呼ばれる両方向待ち行列（deque ／double ended queue ）は、下図に示すように、先頭と末尾に対して、データの押込み・取出しが行えるデータ構造である。両方向待ち行列を表すクラスIntDeque を作成せよ。

// 演習4-6
// int型デック

class IntDeque {

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

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

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

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

    //--- デックにデータを先頭側からエンキュー ---//
    int enqueFront(int x) throws OverflowIntDequeException {
        if (num >= max)
            throw new OverflowIntDequeException();            // デックは満杯
        num++;
        if (--front < 0)
            front = max - 1;
        que[front] = x;
        return x;
    }

    //--- デックにデータを末尾側からエンキュー ---//
    int enqueRear(int x) throws OverflowIntDequeException {
        if (num >= max)
            throw new OverflowIntDequeException();            // デックは満杯
        que[rear++] = x;
        num++;
        if (rear == max)
            rear = 0;
        return x;
    }

    //--- デックの先頭からデータをデキュー ---//
    int dequeFront() throws EmptyIntDequeException {
        if (num <= 0)
            throw new EmptyIntDequeException();            // デックは空
        int x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }

    //--- デックの末尾からデータをデキュー ---//
    int dequeRear() throws EmptyIntDequeException {
        if (num <= 0)
            throw new EmptyIntDequeException();            // デックは空
        num--;
        if (--rear < 0)
            rear = max - 1;       
        return que[rear];
    }

    //--- デックの先頭からデータをピーク（先頭データを覗く） ---*/
    int peekFront() throws EmptyIntDequeException {
        if (num <= 0)
            throw new EmptyIntDequeException();            // デックは空
        return que[front];
    }

    //--- デックの末尾からデータをピーク（末尾データを覗く） ---*/
    int peekRear() throws EmptyIntDequeException {
        if (num <= 0)
            throw new EmptyIntDequeException();            // デックは空
        return que[rear == 0 ? max - 1 : rear - 1];
    }

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

    //--- デックからxを探して先頭から何番目か（見つからなければ-1）を返す ---//
    int search(int 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] + " ");
            System.out.println();
        }
    }
}

戻る