一つの配列を共有して二つのスタックを実現するクラスを作成せよ。図のように配列の先頭側と末尾側の両側を利用すること。 |
// 演習4-2 // 両頭int型スタック class IntStackX2 { int max; // スタックの容量（Ａ・Ｂの合計） int ptrA; // スタックポインタＡ int ptrB; // スタックポインタＢ int[] stk; // スタックの本体 public enum AorB {StackA, StackB}; //--- 実行時例外：スタックが空 ---// public class EmptyIntStackX2Exception extends RuntimeException { public EmptyIntStackX2Exception() { } } //--- 実行時例外：スタックが満杯 ---// public class OverflowIntStackX2Exception extends RuntimeException { public OverflowIntStackX2Exception() { } } //--- コンストラクタ ---// IntStackX2(int capacity) { ptrA = 0; ptrB = capacity - 1; max = capacity; try { stk = new int[max]; // スタック本体用の配列を生成 } catch (OutOfMemoryError e) { // 生成できなかった max = 0; } } //--- スタックにxをプッシュ ---// 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; } //--- スタックからデータをポップ（頂上のデータを取り出す） ---// 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; } //--- スタックからデータをピーク（頂上のデータを覗き見） ---// 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）を返す ---// 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; // 探索失敗 } //--- スタックを空にする ---// void clear(AorB sw) { switch (sw) { case StackA: ptrA = 0; break; case StackB: ptrB = max - 1; break; } } //--- スタックの容量を返す（ＡとＢの合計） ---// int capacity() { return max; } //--- スタックに積まれているデータ数を返す ---// int size(AorB sw) { switch (sw) { case StackA: return ptrA; case StackB: return max - ptrB - 1; } return 0; } //--- スタックは空であるか ---// boolean isEmpty(AorB sw) { switch (sw) { case StackA: return ptrA <= 0; case StackB: return ptrB >= max - 1; } return true; } //--- スタックは満杯であるか ---// boolean isFull() { return ptrA >= ptrB + 1; } //--- スタック内の全データを底→頂上の順に表示 ---// 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-2 // int型両頭スタックの利用例（IntStackX2クラスの全メソッドを利用） import java.util.Scanner; class IntStackX2TesterEx { public static void main(String[] args) { Scanner stdIn = new Scanner(System.in); IntStackX2 s = new IntStackX2(10); // 最大10個プッシュできる両頭スタック while (true) { int menu, n, x = 0; 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)終了："); if ((menu = stdIn.nextInt()) == 0) break; 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; } } } }
