スタック

2023年4月29日 最終更新日時 : 2024年6月25日 山崎講師山崎講師

データ構造のスタックは、後入れ先出し【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

投稿者プロフィール

山崎講師
山崎講師代表取締役
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。
対象読者
新入社員
前の記事
キュー
2023年4月29日
次の記事
アルゴリズムを使って数学の問題を解く
2023年4月29日