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

戻る  

演習4-3の解答

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

戻る