スタックっぽい何かをJavaで実装する

はじめに

　とある事情により、Javaの学習を始めた人向けに急遽スタックっぽいプログラムをつくり、解説することになりました。しかし、時間の都合上ほとんど解説できずじまいで終わってしまったため、その補完ならびにQiita布教を兼ねて、本記事にてその解説の続きを行う所存です。

　対象者としては、Javaを始めたばかりの方になります。もう少し具体的に申し上げると、Hello Worldを経て、データ型や配列の基礎を知り、if文やfor文・while文の書き方を学んだ直後くらいを想定しています。

　とは言え、いきなりスタック（っぽい何か）を実装と言っても難しいと思いますので、第１章では最低限の枠組みだけをつくり、第２章以降で順次スタックとして必要とされる機能を追加実装していきます。ですので、第１章から順番にコーディングを行っていけば、さほど混乱することなくスタック（っぽい何か）をつくることができるはずです。

　なお、開発環境としては、paiza.ioを利用します。タイトル通り、言語はJavaです。

　それでは、しばらくの間お付き合いくださいませ。

第０章　スタックについて

　スタックとはデータ構造の１つであり、最後に入れたものを初めに出す仕組み（LIFO : Last In First Out）をもっています。エレベータをイメージしてみてください。社会人のマナーなどを考慮しない場合、エレベータに乗ったらまず奥から詰めていきます。そしてエレベータから降りるときは、ドアに近い人、すなわち最後に乗った人から降りていきます。

　本記事では、入力された整数をスタックの役割をもつ配列にpush（格納）していき、最後に入力した整数から順にpop（出力）するスタックっぽいプログラムを作成します。最終的な目標として、以下の要件を満たすことを目指します。

• ５個の整数を入れる配列をスタックとして実装する。
• コマンドプロンプトから文字列および整数を入力し続ける。
• 「push 整数」が入力されたら、整数を配列の先頭に追加する。もし、すでに５個入力されている場合は、「push error」と出力する。
• 「pop」が入力されたら、配列の先頭をプロンプトに出力し、出力された整数は配列から削除する（もしくは、削除したかのように見せかける）。もし、スタックに１つも整数がない場合は、「pop error」と出力する。
• 「end」が入力されたらプログラム終了。

　第１章から順に、少しずつ実装していきましょう。

第１章　入力処理

　この章では、比較的簡単な次の項目から実装していきましょう。

• コマンドプロンプトから文字列および整数を入力し続ける。

　paiza.ioにアクセスし、「コード作成を試してみる（無料）」をクリックしてください。初めはPHPなどの他の言語のサンプルが表示されるかも知れませんが、その場合はJavaを選択しましょう。すると、printlnメソッドを含む簡単なプログラムが次のように表示されるはずです。

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!

        System.out.println("XXXXXXXX");
    }
}

　さて、文字列および整数の入力を受け付けるために、一旦String型で受け取り、整数として扱うときだけint型に変換することにします。それでは、とりあえず入力された文字列をString型に格納し続けるプログラムを書いてみてください。また、実行したときに正しく入力を受け付けているかどうか確認するために、「Your input is [入力された文字列]」と表示する処理も追加してください。書けたら、下の解答例１－１を確認してみましょう。

解答例１－１（クリックすると開きます）

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String input = sc.nextLine();
            System.out.println("Your input is [" + input + "]");
        }
    }
}

　試しに実行してみましょう。paiza.ioでは、コマンドプロンプトから入力するかわりに、入力タブを選んで出てくるウィンドウ内に入力したい内容をすべて書いておく必要があります。そこで、入力タブをクリックしたら次のように書いておきましょう。

push 1
push 2
push 3
end

　ここまでできたら、いよいよ本当に実行してみます。すると、実行時エラーというタブができて、「No line found」というメッセージが表示されます。これはどういうことかと言うと、while文の繰り返し条件がtrueになっているため、永遠に繰り返すという処理になっていることが原因です。入力を最後まで受け付けたにも関わらず、さらに入力を受け取ろうとしたため、「もうねえよ」と言われた訳です。実際、出力タブをクリックすると、ちゃんと「end」までは受け付けていることが分かります。

　そこで、今度は次の項目について考えます。

• 「end」が入力されたらプログラム終了。

　入力された文字列が「end」に等しいかどうかを判定するには、Stringクラスのオブジェクトに用意されているequalsメソッドを使うと良いでしょう。詳しい使い方は各自で調べていただきつつ、「end」が入力されたらwhile文のループを抜け出す処理を書いてみてください。書けたら、下の解答例１－２を確認してみましょう。

解答例１－２（クリックすると開きます）

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String input = sc.nextLine();
            System.out.println("Your input is [" + input + "]");
            if (input.equals("end")) {
                break;
            }
        }
    }
}

　実行もしてみてください。「end」を受け付けた後にwhile文のループを抜け、プログラムが正常に終了できたため、実行時エラーが出ていませんね。これで、入力処理はＯＫです。

第２章　push処理

　この章では、次の項目を実装します。

• 「push 整数」が入力されたら、整数を配列の先頭に追加する。もし、すでに５個入力されている場合は、「push error」と出力する。

　スタックの役割をもつint型配列を用意しましょう。配列の名前はstackにしてください。また、配列の宣言を行う際、要素の個数を指定するのに直接5と書くのはやめましょう。その代わりに、事前にint型変数Nに5を代入しておき、配列の宣言時にはNを用いるようにしてください。これらは、while文の手前に書いておきます。

　次に、「push 整数」の入力をどのように処理するかを考えましょう。入力された文字列はpushと半角スペースと整数のため、まず初めの4文字だけを見てpushコマンドであることを判定できるようにします。それにはStringクラスに用意されているsubstringメソッドを利用してください。

　また、入力された文字列から整数だけを取り出すため、これもStringクラスに用意されているsplitメソッドを用いて、pushと整数に分けましょう。ただし、分けただけでは整数が文字列として扱われていますので、文字列をint型に変換するためにIntegerクラスのparseIntメソッドを利用してください。parseIntメソッドは次のように使いましょう。

int number = Integer.parseInt(string);

　最後に、整数をpushする場合に配列stackの何番目に格納するか判定する処理を考えましょう。配列に手前も奥もあるかと思われるかも知れませんが、ここでは0番目の要素が最も手前、N $-$ 1 ($=$ 4)番目の要素が最も奥であると決めることにします。すなわち、整数は奥のN $-$ 1番目から順に手前の0番目に向かって格納されるということです。ただし、すでに0番目まで整数が格納されている場合はエラーメッセージを出力する必要がありますので、このことにも注意して書いてみてください。書けたら、下の解答例２を確認してみましょう。

解答例２（クリックすると開きます）

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = 5;
        int[] stack = new int[N];
        int indexPointer = N;

        while (true) {
            String input = sc.nextLine();
            System.out.println("Your input is [" + input + "]");
            if (input.equals("end")) {
                break;
            } else if (input.substring(0, 4).equals("push")) {
                if (indexPointer >= 1 && indexPointer <= N) {
                    String[] commands = input.split(" ");
                    int number = Integer.parseInt(commands[1]);
                    indexPointer --;
                    stack[indexPointer] = number;
                    System.out.println(number + " pushed. index:" + indexPointer);
                } else {
                    System.out.println("push error.");
                }
            }
        }
    }
}

　少し補足します。配列の何番目の要素に整数を格納するかを把握するために、新たにint型変数indexPointerを用意しました。pushの処理を行う際、直前に見ていた要素より1つ手前に整数を格納できるかどうか、すなわちindexPointerが今1以上N以下かどうかを判定します。それが真であれば、indexPointerを1減らし、その値の場所に整数を格納します。この処理のため、indexPointerを宣言したときの初期値はNにしておく必要があります。

　さて、ここまでの処理が正しいかどうか、少しテストしてみましょう。入力タブを選び、次のように書いてください。

push 1
push 2
push 3
push 4
push 5
push 6
end

　実行してみます。

Your input is [push 1]
1 pushed. index:4
Your input is [push 2]
2 pushed. index:3
Your input is [push 3]
3 pushed. index:2
Your input is [push 4]
4 pushed. index:1
Your input is [push 5]
5 pushed. index:0
Your input is [push 6]
push error.
Your input is [end]

　ちゃんと配列の奥から順に整数を格納し、5個格納した後はエラーメッセージを表示していますね。

第３章　pop処理

　ここまで進めてこれたなら、もう少しでスタックの完成です。前章において、今配列の何番目の要素に格納したかを変数indexPointerで把握することにしました。この変数はそのままpop処理にも利用できます。書けたら、下の解答例３を確認してみましょう。

解答例３（クリックすると開きます）

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = 5;
        int[] stack = new int[N];
        int indexPointer = N;

        while (true) {
            String input = sc.nextLine();
            System.out.println("Your input is [" + input + "]");
            if (input.equals("end")) {
                break;
            } else if (input.length() >= 4 && input.substring(0, 4).equals("push")) {
                if (indexPointer >= 1 && indexPointer <= N) {
                    String[] commands = input.split(" ");
                    int number = Integer.parseInt(commands[1]);
                    indexPointer --;
                    stack[indexPointer] = number;
                    System.out.println(number + " pushed. index:" + indexPointer);
                } else {
                    System.out.println("push error.");
                }
            } else if (input.equals("pop")) {
                if (indexPointer >= 0 && indexPointer < N) {
                    System.out.println(stack[indexPointer] + " poped. index:" + indexPointer);
                    indexPointer ++;
                } else {
                    System.out.println("pop error.");
                }
            }
        }
    }
}

　いかがでしょうか。push処理よりはやや簡単だったと思います。それでは、入力タブに次のように入力してみてください。

pop
push 1
push 2
push 3
pop
pop
pop
push 4
push 5
push 6
push 7
push 8
push 9
end

　実行してみます。

Your input is [pop]
pop error.
Your input is [push 1]
1 pushed. index:4
Your input is [push 2]
2 pushed. index:3
Your input is [push 3]
3 pushed. index:2
Your input is [pop]
3 popped. index:2
Your input is [pop]
2 popped. index:3
Your input is [pop]
1 popped. index:4
Your input is [push 4]
4 pushed. index:4
Your input is [push 5]
5 pushed. index:3
Your input is [push 6]
6 pushed. index:2
Your input is [push 7]
7 pushed. index:1
Your input is [push 8]
8 pushed. index:0
Your input is [push 9]
push error.
Your input is [end]

　ちゃんと、pushされた１、２、３が逆順にpopされていますね。また、何も整数が格納されていないのにpopしようとした場合や、すでに整数が５個格納されているのにpushしようとした場合はエラーメッセージを出力するようになっています。

おわりに

　今回は、Javaの基本的な文法を用いて簡単なスタックを実装しました。上記プログラムを少し変更するだけで、実はキューも実装することができますので、お時間に余裕があればぜひ挑戦してみてください。

　ここまでお読みいただき、ありがとうございました。