スタック内の最大要素と最小要素を見つけるためのJavaプログラム

スタックは、最後の最初の原則（LIFOとも呼ばれる）に従う基本的なデータ構造です。整理機能呼び出しや操作の取り消しなど、スタックには多くのユースケースがあります。多くの場合、スタック内の最大の要素と最小の要素を見つけるという問題に遭遇する可能性があり、この記事では、Javaを使用してこのタスクを達成するための複数の方法を実証します。

スタックを理解

スタックは、上部と呼ばれる一方の端でのみ操作を可能にする線形データ構造です。主な操作には以下が含まれます：

• プッシュ（プッシュ）：スタックの上部に要素を追加します。
• pop（pop）：削除して、スタックの上部要素に戻ります。
• ビュー（ピーク）：スタックを削除せずに、スタックの上部要素を表示します。
• isempty（isempty）：スタックが空であるかどうかを確認します。

問題声明

目標は、スタック内の最大要素と最小要素を決定することです。スタックのLIFOの性質を考えると、上部以外の要素に直接アクセスすることはできません。これには、最大値と最小値を追跡しながら、スタックを横断する必要があります。

2つの追加変数を使用

ここでは、2つの変数を使用して、それぞれ最小値と最大値を追跡します。スタックを反復し、各要素が処理されるときにこれらの変数を更新します。これは最も簡単な方法であり、最も時間のかかるスペースを消費する方法です。

min max

output

import java.util.Stack;

public class MaxMinInStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(5);
        stack.push(15);

        int[] result = findMaxMin(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static int[] findMaxMin(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (Integer element : stack) {
            if (element > max) {
                max = element;
            }
            if (element < min) {
                min = element;
            }
        }
        return new int[]{max, min};
    }
}

最大要素：30 最小要素：5

補助スタックを使用して

ここでは、ポップアップ操作を使用して、必要に応じて最小値と最大値を更新することにより、スタックを通過します。補助スタックは一時的に要素を保存し、これらの要素を元のスタックに復元します。

output

import java.util.Stack;

public class MaxMinInStack {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(5);
        stack.push(15);

        int[] result = findMaxMinWithAuxiliaryStack(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static int[] findMaxMinWithAuxiliaryStack(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        Stack<Integer> tempStack = new Stack<>();
        int max = stack.peek();
        int min = stack.peek();

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (current > max) {
                max = current;
            }
            if (current < min) {
                min = current;
            }
            tempStack.push(current);
        }

        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }

        return new int[]{max, min};
    }
}

最大要素：30 最小要素：5

2つのスタックを使用してください このメソッドは2つの追加スタックを使用します。1つは最大の要素（

）を覚えるために、もう1つは最小の要素（

）を覚えるためです。新しい要素がメインスタックに入るたびに、最大値または最小値を大きくする場合は、

または

にも配置します。 maxStackminStack maxStack minStack

output 最大要素：30 最小要素：5

import java.util.Stack;

public class MaxMinInStack {
    // ... (main method remains the same) ...

    public static int[] findMaxMinWithTwoStacks(Stack<Integer> stack) {
        Stack<Integer> maxStack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();

        while (!stack.isEmpty()) {
            int current = stack.pop();
            if (maxStack.isEmpty() || current >= maxStack.peek()) {
                maxStack.push(current);
            }
            if (minStack.isEmpty() || current <= minStack.peek()) {
                minStack.push(current);
            }
        }
        return new int[]{maxStack.peek(), minStack.peek()};
    }
}

修正されたスタック構造を使用します

スタック構造は、最大値と最小値と通常のスタック要素自体に含まれるように変更されています。各要素は、値、現在の最大値、現在の最小値を含むペアとして保存されます。

output 最大要素：30 最小要素：5

import java.util.Stack;

public class MaxMinInStack {
    static class StackNode {
        int value;
        int currentMax;
        int currentMin;

        StackNode(int value, int currentMax, int currentMin) {
            this.value = value;
            this.currentMax = currentMax;
            this.currentMin = currentMin;
        }
    }

    public static void main(String[] args) {
        Stack<StackNode> stack = new Stack<>();
        push(stack, 10);
        push(stack, 20);
        push(stack, 30);
        push(stack, 5);
        push(stack, 15);

        int[] result = findMaxMinWithModifiedStack(stack);
        System.out.println("最大元素: " + result[0]);
        System.out.println("最小元素: " + result[1]);
    }

    public static void push(Stack<StackNode> stack, int value) {
        int max = stack.isEmpty() ? value : Math.max(value, stack.peek().currentMax);
        int min = stack.isEmpty() ? value : Math.min(value, stack.peek().currentMin);
        stack.push(new StackNode(value, max, min));
    }

    public static int[] findMaxMinWithModifiedStack(Stack<StackNode> stack) {
        if (stack.isEmpty()) {
            throw new IllegalArgumentException("栈为空");
        }

        StackNode topNode = stack.peek();
        return new int[]{topNode.currentMax, topNode.currentMin};
    }
}

結論

スタック内の最大の要素と最小の要素を探すことは、それぞれに利点と短所を備えたさまざまな方法で解決できます。示されている方法には、追加の変数、補助スタックの使用、最大値と最小値のための個別のスタックの管理、またはスタック自体の構造の変更が含まれます。

各テクノロジーは、スタックアイテムにアクセスまたは保存する特定の方法を提供します。これにより、メモリの制限、パフォーマンス要件、データの整合性要件に基づいて特定の状況に適しています。これらの方法を理解して適用することで、開発者がJavaのスタックを効果的に処理し、アプリケーションを特定の状況に最適にすることができます。

以上がスタック内の最大要素と最小要素を見つけるためのJavaプログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。