BohYoh.comトップページへ

新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習4-7の解答

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



// 演習4-7 // int型デック public class IntDeque {    //--- 実行時例外:キューが空 ---//    public class EmptyIntDequeException extends RuntimeException {       public EmptyIntDequeException() { }    }    //--- 実行時例外:キューが満杯 ---//    public class OverflowIntDequeException extends RuntimeException {       public OverflowIntDequeException() { }    }    private int max;      // デックの容量    private int num;      // 現在のデータ数    private int front;   // 先頭要素カーソル    private int rear;      // 末尾要素カーソル    private int[] que;   // デックの本体    //--- コンストラクタ ---//    public IntDeque(int capacity) {       num = front = rear = 0;       max = capacity;       try {          que = new int[max];            // デック本体用の配列を生成       catch (OutOfMemoryError e) {   // 生成できなかった          max = 0;       }    }    //--- デックにデータを先頭側からエンキュー ---//    public int enqueFront(int xthrows OverflowIntDequeException {       if (num >= max)          throw new OverflowIntDequeException();      // デックは満杯       num++;       if (--front < 0)          front = max - 1;       que[front= x;       return x;    }    //--- デックにデータを末尾側からエンキュー ---//    public int enqueRear(int xthrows OverflowIntDequeException {       if (num >= max)          throw new OverflowIntDequeException();      // デックは満杯       que[rear++= x;       num++;       if (rear == max)          rear = 0;       return x;    }    //--- デックの先頭からデータをデキュー ---//    public int dequeFront() throws EmptyIntDequeException {       if (num <= 0)          throw new EmptyIntDequeException();         // デックは空       int x = que[front++];       num--;       if (front == max)          front = 0;       return x;    }    //--- デックの末尾からデータをデキュー ---//    public int dequeRear() throws EmptyIntDequeException {       if (num <= 0)          throw new EmptyIntDequeException();         // デックは空       num--;       if (--rear < 0)          rear = max - 1;              return que[rear];    }    //--- デックの先頭からデータをピーク(先頭データを覗く) ---*/    public int peekFront() throws EmptyIntDequeException {       if (num <= 0)          throw new EmptyIntDequeException();         // デックは空       return que[front];    }    //--- デックの末尾からデータをピーク(末尾データを覗く) ---*/    public int peekRear() throws EmptyIntDequeException {       if (num <= 0)          throw new EmptyIntDequeException();         // デックは空       return que[rear == ? max - : rear - 1];    }    //--- デックからxを探してインデックス(見つからなければ-1)を返す ---//    public int indexOf(int x) {       for (int i = 0; i < num; i++)          if (que[(i + front% max]  == x)   // 探索成功             return i + front;       return -1;                              // 探索失敗    }    //--- デックからxを探して先頭から何番目か(見つからなければ0)を返す ---//    public int search(int x) {       for (int i = 0; i < num; i++)          if (que[(i + front% max]  == x)   // 探索成功             return i + 1;       return 0;                              // 探索失敗    }    //--- デックを空にする ---//    public void clear() {       num = front = rear = 0;    }    //--- デックの容量を返す ---//    public int capacity() {       return max;    }    //--- デックに蓄えられているデータ数を返す ---//    public int size() {       return num;    }    //--- デックは空であるか ---//    public boolean isEmpty() {       return num <= 0;    }    //--- デックは満杯であるか ---//    public boolean isFull() {       return num >= max;    }    //--- デック内の全データを先頭→末尾の順に表示 ---//    public 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();       }    } }


// 演習4-7 // int型デックのテストプログラム import java.util.Scanner; class IntDequeTester {    public static void main(String[] args) {       Scanner stdIn = new Scanner(System.in);       IntDeque s = new IntDeque(10);      // 最大10個押し込めるキュー       while (true) {          System.out.println("現在のデータ数:" + s.size() " / "                                                + s.capacity());          System.out.print("(1)先頭にエンキュー (2)先頭からデキュー (3)先頭からピーク\n" +                           "(4)末尾にエンキュー (5)末尾からデキュー (6)末尾からピーク\n" +                           "(7)ダンプ (8)探索 (0)終了:");          int menu = stdIn.nextInt();          if (menu == 0break;          int x = 0, idx;          switch (menu) {           case 1:                      // 先頭にエンキュー             System.out.print("データ:");             x = stdIn.nextInt();             try {                s.enqueFront(x);              catch (IntDeque.OverflowIntDequeException e) {                System.out.println("キューが満杯です。");             }             break;           case 2:                      // 先頭からデキュー             try {                 x = s.dequeFront();                System.out.println("デキューしたデータは" + x + "です。");              catch (IntDeque.EmptyIntDequeException e) {                System.out.println("キューが空です。");             }             break;           case 3:                      // 先頭からピーク             try {                 x = s.peekFront();                System.out.println("ピークしたデータは" + x + "です。");              catch (IntQueue.EmptyIntQueueException e) {                System.out.println("キューが空です。");             }             break;           case 4:                      // 先頭にエンキュー             System.out.print("データ:");             x = stdIn.nextInt();             try {                s.enqueRear(x);              catch (IntDeque.OverflowIntDequeException e) {                System.out.println("キューが満杯です。");             }             break;           case 5:                      // 先頭からデキュー             try {                 x = s.dequeRear();                System.out.println("デキューしたデータは" + x + "です。");              catch (IntDeque.EmptyIntDequeException e) {                System.out.println("キューが空です。");             }             break;           case 6:                      // 先頭からピーク             try {                 x = s.peekRear();                System.out.println("ピークしたデータは" + x + "です。");              catch (IntQueue.EmptyIntQueueException e) {                System.out.println("キューが空です。");             }             break;           case 7:                      // ダンプ             s.dump();             break;           case 8:                      // 探索             System.out.print("探索するデータ:");             x = stdIn.nextInt();             idx = s.search(x);             if (idx != -1)                System.out.println("そのデータは" + idx + "番目に存在します。");             else                System.out.println("そのデータは存在しません。");             break;          }       }    } }


戻る