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

戻る  

演習4-2の解答

public class Gstack<E > {
　　private int max;    // スタックの容量
　　private int ptr;    // スタックポインタ
　　E[] stk;             // スタックの本体
　　//...
}

// 演習4-2
// ジェネリックなスタック

public class Gstack<E> {
   private int   max;      // スタックの容量
   private int   ptr;      // スタックポインタ
   private E[] stk;      // スタックの本体

   //--- 実行時例外：スタックが空 ---//
   public static class EmptyGstackException extends RuntimeException {
      public EmptyGstackException() { }
   }

   //--- 実行時例外：スタックが満杯 ---//
   public static class OverflowGstackException extends RuntimeException {
      public OverflowGstackException() { }
   }

   //--- コンストラクタ ---//
   public Gstack(int capacity) {
      ptr = 0;
      max = capacity;
      try {
         stk = (E[])new Object[max];   // スタック本体用の配列を生成
      } catch (OutOfMemoryError e) {   // 生成できなかった
         max = 0;
      }
   }

   //--- スタックにxをプッシュ ---//
   public E push(E x) throws OverflowGstackException {
      if (ptr >= max)                     // スタックは満杯
         throw new OverflowGstackException();
      return stk[ptr++] = x;
   }

   //--- スタックからデータをポップ（頂上のデータを取り出す） ---//
   public E pop() throws EmptyGstackException {
      if (ptr <= 0)                     // スタックは空
         throw new EmptyGstackException();
      return stk[--ptr];
   }

   //--- スタックからデータをピーク（頂上のデータを覗き見） ---//
   public E peek() throws EmptyGstackException {
      if (ptr <= 0)                     // スタックは空
         throw new EmptyGstackException();
      return stk[ptr - 1];
   }

   //--- スタックからxを探してインデックス（見つからなければ-1）を返す ---//
   public int indexOf(E x) {
      for (int i = ptr - 1; i >= 0; i--)      // 頂上側から線形探索
         if (stk[i].equals(x))
            return i;                  // 探索成功
      return -1;                        // 探索失敗
   }

   //--- スタックを空にする ---//
   public void clear() {
      ptr = 0;
   }

   //--- スタックの容量を返す ---//
   public int capacity() {
      return max;
   }

   //--- スタックに積まれているデータ数を返す ---//
   public int size() {
      return ptr;
   }

   //--- スタックは空であるか ---//
   public boolean isEmpty() {
      return ptr <= 0;
   }

   //--- スタックは満杯であるか ---//
   public boolean isFull() {
      return ptr >= max;
   }

   //--- スタック内の全データを底→頂上の順に表示 ---//
   public void dump() {
      if (ptr <= 0)
         System.out.println("スタックは空です。");
      else {
         for (int i = 0; i < ptr; i++)
            System.out.print(stk[i] + " ");
         System.out.println();
      }
   }
}

// 演習4-2
// ジェネリックなスタックの利用例（Gstackクラスの全メソッドを利用）

import java.util.Scanner;

class GstackTesterEx {

   public static void main(String[] args) {
      Scanner stdIn = new Scanner(System.in);
      Gstack<String> s = new Gstack<String>(100);      // 最大100個プッシュできるスタック

      while (true) {
         System.out.println("現在のデータ数：" + s.size() + " / "
                                               + s.capacity());
         System.out.print("(1)プッシュ (2)ポップ (3)ピーク " +
                          "(4)ダンプ (5)探索 (6)空にする " +
                          "(7)情報表示 (0)終了：");

         int menu = stdIn.nextInt();
         if (menu == 0) break;

         String x;

         switch (menu) {
          case 1:                      // プッシュ
            System.out.print("データ：");
            x = stdIn.next();
            try {
               s.push(x);
             } catch (Gstack.OverflowGstackException e) {
               System.out.println("スタックが満杯です。");
            }
            break;

          case 2:                      // ポップ
            try {
                x = s.pop();
               System.out.println("ポップしたデータは" + x + "です。");
             } catch (Gstack.EmptyGstackException e) {
               System.out.println("スタックが空です。");
            }
            break;

          case 3:                      // ピーク
            try {
                x = s.peek();
               System.out.println("ピークしたデータは" + x + "です。");
             } catch (Gstack.EmptyGstackException e) {
               System.out.println("スタックが空です。");
            }
            break;

          case 4:                      // ダンプ
            s.dump();
            break;

          case 5:                      // 探索
            System.out.print("探索するデータ：");
            x = stdIn.next();
            int n = s.indexOf(x);
            if (n >= 0)
               System.out.println("頂上から" + (s.size() - n) +"番目に存在します。");
            else
               System.out.println("そのデータはありません。");
            break;

          case 6:                      // 空にする
            s.clear();
            break;

          case 7:                      // 情報表示
            System.out.println("容量：" + s.capacity());
            System.out.println("データ数：" + s.size());
            System.out.println("空" + (s.isEmpty()  ? "です。"
                                                    : "ではありません。"));
            System.out.println("満杯" + (s.isFull() ? "です。"
                                                    : "ではありません。"));
            break;
         }
      }
   }
}

戻る