BohYoh.comトップページへ

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 xthrows OverflowIntDequeException {         if (num >= max)             throw new OverflowIntDequeException();            // デックは満杯         num++;         if (--front < 0)             front = max - 1;         que[front= x;         return x;     }     //--- デックにデータを末尾側からエンキュー ---//     int enqueRear(int xthrows 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 == ? max - : 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();         }     } }


戻る