Javaでスタックを実装する

基本情報技術者試験に向けて、アルゴリズムを勉強しています。今回はスタックとキューをJavaで実装してみました。

スタックとは

スタックでは最後に格納した要素が最初に取り出されます。このような仕組みをLIFO(Last In First Out、後入れ先出し)と言います。

まずは以下の用語について確認してください。

  • プッシュ(push):スタックにデータを積むこと
  • ポップ(pop):スタックからデータを取り出すこと

スタックにプッシュが行われることにより、データが積まれていきます。その際、「ひとつ前にプッシュしたデータ」は「今プッシュしたデータ」の下に置かれます。

32102

スタックからポップを行うと、スタックの一番上にあるデータが取り出されます。一番上にあるデータ以外は取り出せません。

32103

実装する

今回はjava.utilパッケージのStackクラスを参考にして実装します。
まずは、スタックのデータ構造を作ります。以下の内容を記述したStackクラスを作成しましょう。

public class Stack {
    private Object[] data;
    private int ptr;
}
  • data変数:実際にデータを積んでいく変数です。
  • ptr変数:スタックポインタです。プッシュされたデータを格納する位置、また、ポップ時にどの位置のデータを返すかを管理する変数です。

32201

pushメソッドを実装する

プッシュ操作を実装します。Stackクラスに以下のメソッドを追記してください。

public void push(Object o) {
    if (ptr >= data.length) {
        throw new RuntimeException("stack full");
    }
    data[ptr] = o;
    ptr++;
} 

スタックにこれ以上データが入らないときは例外処理を行います。データを積んだときは、スタックポインタのカウントも上昇します。

popメソッドを実装する

ポップ操作を実装します。Stackクラスに以下のメソッドを追記してください。

public Object pop() {
    if (ptr <= 0) {
        throw new RuntimeException("stack empty");
    }
    ptr--;
    Object o = data[ptr];
    data[ptr] = null;
    return o;
}

スタックが空のときは例外処理を行います。スタックポインタは次にデータを格納する位置を示しています。デクリメントを行い現在の一番上のデータ指すようにし、取り出しを行います(同時に、再度pushされた場合に適切な位置に追加されるようにします)。配列からデータを取り出した後、配列にnullを代入していますが、これはガベージコレクション時に参照されなくなったデータが適切に削除されるようにするためです。そして、取り出したデータをreturnします。

toStringメソッドを実装する

動作確認のためにtoStringメソッドを実装します(System.out.println()の内容を調整します)。

public String toString() {
    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (int i = 0; i < ptr; i++) {
        sb.append(data[i]);
        if (i != ptr - 1) {
            sb.append(", ");
        }
    }
    sb.append(']');
    return sb.toString();
} 

動作確認

新たに動作確認用のクラスを作成し、mainメソッドに以下のように記述します。

public static void main(String[] args) {
    Stack stack = new Stack(10);

    stack.push("abc");
    System.out.println(stack);
    stack.push("def");
    System.out.println(stack);
    stack.push("ghi");
    System.out.println(stack);
    stack.pop();
    System.out.println(stack);
    stack.pop();
    System.out.println(stack);
    stack.pop();
    System.out.println(stack);
}

動作結果:

[abc]
[abc, def]
[abc, def, ghi]
[abc, def]
[abc]
[]

参考資料
スクールの教科書