BohYoh.comトップページへ

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

戻る  

演習4-3の解答

 一つの配列を共有して二つのスタックを実現するint型データ用のクラスを作成せよ。図のように配列の先頭側と末尾側の両側を利用すること。



// 演習4-3 // 両頭int型スタック public class IntStackX2 {    private int max;      // スタックの容量(A・Bの合計)    private int ptrA;      // スタックポインタA    private int ptrB;      // スタックポインタB    private int[] stk;      // スタックの本体    public enum AorB {StackA, StackB};    //--- 実行時例外:スタックが空 ---//    public class EmptyIntStackX2Exception extends RuntimeException {       public EmptyIntStackX2Exception() { }    }    //--- 実行時例外:スタックが満杯 ---//    public class OverflowIntStackX2Exception extends RuntimeException {       public OverflowIntStackX2Exception() { }    }    //--- コンストラクタ ---//    public IntStackX2(int capacity) {       ptrA = 0;       ptrB = capacity - 1;       max  = capacity;       try {          stk = new int[max];         // スタック本体用の配列を生成       catch (OutOfMemoryError e) {   // 生成できなかった          max = 0;       }    }    //--- スタックにxをプッシュ ---//    public int push(AorB sw, int xthrows OverflowIntStackX2Exception {       if (ptrA >= ptrB + 1)                     // スタックは満杯          throw new OverflowIntStackX2Exception();       switch (sw) {        case StackA: stk[ptrA++= x; break;        case StackB: stk[ptrB--= x; break;       }       return x;    }    //--- スタックからデータをポップ(頂上のデータを取り出す) ---//    public int pop(AorB swthrows EmptyIntStackX2Exception {       int x = 0;       switch (sw) {        case StackA:           if (ptrA <= 0)                     // スタックAは空             throw new EmptyIntStackX2Exception();          x = stk[--ptrA];          break;        case StackB:          if (ptrB >= max - 1)               // スタックBは空             throw new EmptyIntStackX2Exception();          x = stk[++ptrB];          break;       }       return x;    }    //--- スタックからデータをピーク(頂上のデータを覗き見) ---//    public int peek(AorB swthrows EmptyIntStackX2Exception {       int x = 0;       switch (sw) {        case StackA:           if (ptrA <= 0)                     // スタックAは空             throw new EmptyIntStackX2Exception();          x = stk[ptrA - 1];          break;        case StackB:          if (ptrB >= max - 1)               // スタックBは空             throw new EmptyIntStackX2Exception();          x = stk[ptrB + 1];          break;       }       return x;    }    //--- スタックからxを探してインデックス(見つからなければ-1)を返す ---//    public int indexOf(AorB sw, int x) {       switch (sw) {        case StackA:           for (int i = ptrA - 1; i >= 0; i--)      // 頂上側から線形探索             if (stk[i== x)                return i;                  // 探索成功          break;        case StackB:          for (int i = ptrB + 1; i < max; i++)   // 頂上側から線形探索             if (stk[i== x)                return i;                  // 探索成功          break;       }       return -1;                           // 探索失敗    }    //--- スタックを空にする ---//    public void clear(AorB sw) {       switch (sw) {        case StackA: ptrA = 0break;        case StackB: ptrB = max - 1break;       }    }    //--- スタックの容量を返す(AとBの合計) ---//    public int capacity() {       return max;    }    //--- スタックに積まれているデータ数を返す ---//    public int size(AorB sw) {       switch (sw) {        case StackA: return ptrA;        case StackB: return max - ptrB - 1;       }       return 0;    }    //--- スタックは空であるか ---//    public boolean isEmpty(AorB sw) {       switch (sw) {        case StackA: return ptrA <= 0;        case StackB: return ptrB >= max - 1;       }       return true;    }    //--- スタックは満杯であるか ---//    public boolean isFull() {       return ptrA >= ptrB + 1;    }    //--- スタック内の全データを底→頂上の順に表示 ---//    public void dump(AorB sw) {       switch (sw) {        case StackA:          if (ptrA <= 0)             System.out.println("スタックは空です。");          else {             for (int i = 0; i < ptrA; i++)                System.out.print(stk[i" ");             System.out.println();          }        case StackB:          if (ptrB >= max - 1)             System.out.println("スタックは空です。");          else {             for (int i = max - 1; i > ptrB; i--)                System.out.print(stk[i" ");             System.out.println();          }       }    } }


// 演習4-3 // int型両頭スタックの利用例(IntStackX2クラスの全メソッドを利用) import java.util.Scanner; class IntStackX2Tester {    public static void main(String[] args) {       Scanner stdIn = new Scanner(System.in);       IntStackX2 s = new IntStackX2(10);   // 最大10個プッシュできる両頭スタック       while (true) {          System.out.println("現在のデータ数:"+                               "A:" + s.size(IntStackX2.AorB.StackA                               "B:" + s.size(IntStackX2.AorB.StackB));          System.out.print("(1)Aにプッシュ (2)Aからポップ (3)Aからピーク " +                           "(4)Aをダンプ (5)Aから探索 (6)Aを空にする\n" +                           "(7)Bにプッシュ (8)Bからポップ (9)Bからピーク " +                           "(10)Bをダンプ (11)Bから探索 (12)Bを空にする\n" +                           "(13)情報表示 (0)終了:");          int menu = stdIn.nextInt();          if (menu == 0break;          int n, x = 0;          switch (menu) {           case 1:                        // Aにプッシュ             System.out.print("データ:");             x = stdIn.nextInt();             try {                s.push(IntStackX2.AorB.StackA, x);              catch (IntStackX2.OverflowIntStackX2Exception e) {                System.out.println("スタックが満杯です。");             }             break;           case 2:                         // Aからポップ             try {                 x = s.pop(IntStackX2.AorB.StackA);                System.out.println("ポップしたデータは" + x + "です。");              catch (IntStackX2.EmptyIntStackX2Exception e) {                System.out.println("スタックが空です。");             }             break;           case 3:                         // Aからピーク             try {                 x = s.peek(IntStackX2.AorB.StackA);                System.out.println("ピークしたデータは" + x + "です。");              catch (IntStackX2.EmptyIntStackX2Exception e) {                System.out.println("スタックが空です。");             }             break;           case 4:                         // Aをダンプ             s.dump(IntStackX2.AorB.StackA);             break;           case 5:                         // Aから探索             System.out.print("探索するデータ:");             x = stdIn.nextInt();             n = s.indexOf(IntStackX2.AorB.StackA, x);             if (n >= 0)                System.out.println("頂上から" (s.size(IntStackX2.AorB.StackA- n+"番目に存在します。");             else                System.out.println("そのデータはありません。");             break;           case 6:                      // 空にする             s.clear(IntStackX2.AorB.StackA);             break;           case 7:                        // Bにプッシュ             System.out.print("データ:");             x = stdIn.nextInt();             try {                s.push(IntStackX2.AorB.StackB, x);              catch (IntStackX2.OverflowIntStackX2Exception e) {                System.out.println("スタックが満杯です。");             }             break;           case 8:                         // Bからポップ             try {                 x = s.pop(IntStackX2.AorB.StackB);                System.out.println("ポップしたデータは" + x + "です。");              catch (IntStackX2.EmptyIntStackX2Exception e) {                System.out.println("スタックが空です。");             }             break;           case 9:                         // Bからピーク             try {                 x = s.peek(IntStackX2.AorB.StackB);                System.out.println("ピークしたデータは" + x + "です。");              catch (IntStackX2.EmptyIntStackX2Exception e) {                System.out.println("スタックが空です。");             }             break;           case 10:                         // Bをダンプ             s.dump(IntStackX2.AorB.StackB);             break;           case 11:                         // Bから探索             System.out.print("探索するデータ:");             x = stdIn.nextInt();             n = s.indexOf(IntStackX2.AorB.StackB, x);             if (n >= 0)                System.out.println("頂上から" (s.size(IntStackX2.AorB.StackB(s.capacity() - n1+"番目に存在します。");             else                System.out.println("そのデータはありません。");             break;           case 12:                      // 空にする             s.clear(IntStackX2.AorB.StackB);             break;           case 13:                      // 情報表示             System.out.println("容量:" + s.capacity());             System.out.println("Aのデータ数:" + s.size(IntStackX2.AorB.StackA));             System.out.println("Bのデータ数:" + s.size(IntStackX2.AorB.StackB));             System.out.println("Aは空" (s.isEmpty(IntStackX2.AorB.StackA)  "です。"                                                                               "ではありません。"));             System.out.println("Bは空" (s.isEmpty(IntStackX2.AorB.StackB)  "です。"                   "ではありません。"));             System.out.println("満杯" (s.isFull() "です。"                                                     "ではありません。"));             break;          }       }    } }


戻る