【プログラミングしてみよう68】Javaでデータ構造入門①スタック

前回はアルゴリズム入門としてソートと探索を学びました。

今回から3回に分けてデータ構造を解説します。第1回は「スタック」です。

スタックとは

スタックは**後入れ先出し(LIFO: Last In First Out)**のデータ構造です。 積み重ねた皿のイメージで、最後に積んだものを最初に取り出します。

よく使うメソッドは push(追加)・pop(取り出し)・peek(確認)の3つです。

サンプルコード

ファイル作成

「Java56」フォルダに StackSample.java という名前でファイルを作成します

コード入力

import java.util.ArrayDeque;
import java.util.Deque;

public class StackSample {
    // スタックを使った応用: 括弧の対応チェック
    static boolean isBalanced(String expr) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : expr.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if (c == ')' && open != '(') return false;
                if (c == ']' && open != '[') return false;
                if (c == '}' && open != '{') return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("peek: " + stack.peek());
        System.out.println("pop: "  + stack.pop());
        System.out.println("pop: "  + stack.pop());
        System.out.println("size: " + stack.size());

        // 括弧の対応チェック
        System.out.println("\n--- 括弧チェック ---");
        String[] exprs = {"(1 + 2) * 3", "[(1 + 2])", "{[()]}", "((("};
        for (String expr : exprs) {
            System.out.println("\"" + expr + "\": " + (isBalanced(expr) ? "正しい" : "不正"));
        }
    }
}

コンパイル

javac StackSample.java

実行

java StackSample

実行結果は次のようになります。

peek: 3
pop: 3
pop: 2
size: 1

--- 括弧チェック ---
"(1 + 2) * 3": 正しい
"[(1 + 2])": 不正
"{[()]}": 正しい
"(((": 不正

まとめ

スタックはLIFO(後入れ先出し)のデータ構造で、push・pop・peek の3つの操作が基本です。括弧の対応チェックや「元に戻す(Ctrl+Z)」のような「直前の操作を取り消す」機能に活用されます。Javaでは ArrayDeque を使うのが推奨です。次回はキューを解説します。

2026/08/16(日) ぱんまる