新・明解Javaで学ぶアルゴリズムとデータ構造
演習4-3の解答
一つの配列を共有して二つのスタックを実現するint型データ用のクラスを作成せよ。図のように配列の先頭側と末尾側の両側を利用すること。
|
// 演習4-3
// 両頭int型スタック
public class IntStackX2 {
private int max; // スタックの容量（Ａ・Ｂの合計）
private int ptrA; // スタックポインタＡ
private int ptrB; // スタックポインタＢ
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 x) throws 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 sw) throws EmptyIntStackX2Exception {
int x = 0;
switch (sw) {
case StackA:
if (ptrA <= 0) // スタックＡは空
throw new EmptyIntStackX2Exception();
x = stk[--ptrA];
break;
case StackB:
if (ptrB >= max - 1) // スタックＢは空
throw new EmptyIntStackX2Exception();
x = stk[++ptrB];
break;
}
return x;
}
//--- スタックからデータをピーク（頂上のデータを覗き見） ---//
public int peek(AorB sw) throws EmptyIntStackX2Exception {
int x = 0;
switch (sw) {
case StackA:
if (ptrA <= 0) // スタックＡは空
throw new EmptyIntStackX2Exception();
x = stk[ptrA - 1];
break;
case StackB:
if (ptrB >= max - 1) // スタックＢは空
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 = 0; break;
case StackB: ptrB = max - 1; break;
}
}
//--- スタックの容量を返す（ＡとＢの合計） ---//
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("現在のデータ数："+
"Ａ：" + s.size(IntStackX2.AorB.StackA) +
"Ｂ：" + s.size(IntStackX2.AorB.StackB));
System.out.print("(1)Ａにプッシュ (2)Ａからポップ (3)Ａからピーク " +
"(4)Ａをダンプ (5)Ａから探索 (6)Ａを空にする\n" +
"(7)Ｂにプッシュ (8)Ｂからポップ (9)Ｂからピーク " +
"(10)Ｂをダンプ (11)Ｂから探索 (12)Ｂを空にする\n" +
"(13)情報表示 (0)終了：");
int menu = stdIn.nextInt();
if (menu == 0) break;
int n, x = 0;
switch (menu) {
case 1: // Ａにプッシュ
System.out.print("データ：");
x = stdIn.nextInt();
try {
s.push(IntStackX2.AorB.StackA, x);
} catch (IntStackX2.OverflowIntStackX2Exception e) {
System.out.println("スタックが満杯です。");
}
break;
case 2: // Ａからポップ
try {
x = s.pop(IntStackX2.AorB.StackA);
System.out.println("ポップしたデータは" + x + "です。");
} catch (IntStackX2.EmptyIntStackX2Exception e) {
System.out.println("スタックが空です。");
}
break;
case 3: // Ａからピーク
try {
x = s.peek(IntStackX2.AorB.StackA);
System.out.println("ピークしたデータは" + x + "です。");
} catch (IntStackX2.EmptyIntStackX2Exception e) {
System.out.println("スタックが空です。");
}
break;
case 4: // Ａをダンプ
s.dump(IntStackX2.AorB.StackA);
break;
case 5: // Ａから探索
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: // Ｂにプッシュ
System.out.print("データ：");
x = stdIn.nextInt();
try {
s.push(IntStackX2.AorB.StackB, x);
} catch (IntStackX2.OverflowIntStackX2Exception e) {
System.out.println("スタックが満杯です。");
}
break;
case 8: // Ｂからポップ
try {
x = s.pop(IntStackX2.AorB.StackB);
System.out.println("ポップしたデータは" + x + "です。");
} catch (IntStackX2.EmptyIntStackX2Exception e) {
System.out.println("スタックが空です。");
}
break;
case 9: // Ｂからピーク
try {
x = s.peek(IntStackX2.AorB.StackB);
System.out.println("ピークしたデータは" + x + "です。");
} catch (IntStackX2.EmptyIntStackX2Exception e) {
System.out.println("スタックが空です。");
}
break;
case 10: // Ｂをダンプ
s.dump(IntStackX2.AorB.StackB);
break;
case 11: // Ｂから探索
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() - n) + 1) +"番目に存在します。");
else
System.out.println("そのデータはありません。");
break;
case 12: // 空にする
s.clear(IntStackX2.AorB.StackB);
break;
case 13: // 情報表示
System.out.println("容量：" + s.capacity());
System.out.println("Ａのデータ数：" + s.size(IntStackX2.AorB.StackA));
System.out.println("Ｂのデータ数：" + s.size(IntStackX2.AorB.StackB));
System.out.println("Ａは空" + (s.isEmpty(IntStackX2.AorB.StackA) ? "です。"
: "ではありません。"));
System.out.println("Ｂは空" + (s.isEmpty(IntStackX2.AorB.StackB) ? "です。"
: "ではありません。"));
System.out.println("満杯" + (s.isFull() ? "です。"
: "ではありません。"));
break;
}
}
}
}
