スタック
山崎講師データ構造のスタックは、後入れ先出し【LIFO：Last-In, First-Out】の方式で要素を追加・削除することができるデータ構造です。
後入れ先出しとはその名の通り、後に入れたものが先に出されるデータ構造をいいます。
例えば、本棚の一番上に書籍を重ねていく場合を考えてみましょう。最初に置かれた書籍は本棚の底にあり、その上に順番に書籍が重ねられます。最後に重ねられた書籍が一番上にくるため、最後に置いた書籍から順に取り出すことができます。スタックも同様で、新しい要素は常にトップに追加され、トップから取り出されます。
スタックでは、新しい要素は常にスタックのトップに追加されます。スタックのトップにある要素は、最後に追加された要素であり、スタックから削除される要素も同じ要素です。それぞれプッシュ【push】とポップ【pop】操作で実現されます。
スタックは、再帰的なアルゴリズムなど様々なアプリケーションで使用されます。また、関数の呼び出しや式の評価など、プログラミングにおいてもよく使われます。
以下はスタックの利用例です。
- 関数呼び出し：関数を呼び出すと、関数がスタックにプッシュされます。関数が終了すると、スタックからポップされます。この方法により、プログラムがどこに戻る必要があるかを追跡できます。
- ブラウザ履歴：ブラウザの「戻る」ボタンをクリックすると、前のページに戻ります。この機能は、スタックを使用して実装されています。現在のページがスタックにプッシュされ、前のページがポップされます。
- 式の評価：数式の評価中に、演算子をスタックにプッシュします。演算子の優先順位を考慮して、スタックから演算子をポップして式を評価します。
- メモリの割り当て：プログラムがメモリを使用するとき、メモリの割り当てはスタックによって管理されます。新しいメモリが必要な場合、スタックから空いている領域が取り出されます。
スタックは、プログラミングやコンピュータサイエンスにおいて、多くの場面で使用される便利なデータ構造の1つです。
スタックを配列を使って実装する
＜サンプルプログラム＞
import java.util.Scanner;
public class SieveOfEratosthenes {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("いくつまでの素数を知りたいですか？: ");
int n = sc.nextInt();
sc.close();
boolean[] digits = new boolean[n + 1];//配列は0始まり
for (int i = 0; i < digits.length; i++) {
digits[i] = true;//配列はfalseで初期化されているため全てtrue(素数である)にする
}
digits[0] = digits[1] = false;//0と1は素数ではない
for (int i = 2; i * i < digits.length; i++) {
if (digits[i]) {
for (int j = i * i; j < digits.length; j += i) {
digits[j] = false;
}
}
}
for (int i = 2; i < digits.length; i++) {
if (digits[i]) {
System.out.print(i + " ");
}
}
}
}なお、単にスタックを利用するなら以下のjava.util.Stackを使うほうが便利です。
java.util.Stack
Javaの java.util.Stack クラスは、スタックを実装するためのクラスで、LIFO（後入れ先出し）のデータ構造を提供します。以下は、 java.util.Stack クラスで使用できる主なメソッドの一覧です。
push(E element)：スタックに要素をプッシュします。pop()：スタックから要素をポップし、その要素を返します。peek()：スタックのトップ要素を返しますが、削除しません。empty()：スタックが空であるかどうかを返します。
＜サンプルプログラム＞
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
// スタックに要素をプッシュ
stack.push("akafuku");
stack.push("habutai");
stack.push("kiyome");
// スタックから要素をポップ
String popped = stack.pop();
System.out.println("ポップした要素: " + popped);
// スタックのトップ要素を出力
System.out.println("トップ要素: " + stack.peek());
// スタックが空かどうかをチェック
boolean isEmpty = stack.empty();
System.out.println("スタックは空ですか？ " + isEmpty);
}
}＜出力結果＞
| ポップした要素: kiyome トップ要素: habutai スタックは空ですか？ false |
練習問題
基本情報技術者試験 令和元年秋期 午前問8
練習問題
基本情報技術者試験 平成24年春期 午前問6
練習問題
HTMLのタグ（＜＞）の対応をチェックするTagCheckerをjava.util.Stackを使い作成しなさい。
import java.util.Stack;
public class TagChecker {
public static boolean check(String str) {
//ここに処理の中身を書く
}
public static void main(String[] args) {
System.out.println(check("<html>"));
System.out.println(check("<html>aaa</html>"));
System.out.println(check("<a href=\"https://www.yahoo.co.jp/\">ヤフージャパンへ</a>"));
System.out.println(check("<p><img src=\"mtFuji.jpg\"></p>"));
System.out.println(check("<p>/p>"));
System.out.println(check(">p<"));
}
}＜出力結果＞
| true true true true false false |
