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

スタックを理解

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

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

問題聲明

目標(biāo)は、スタック內(nèi)の最大要素と最小要素を決定することです。スタックのLIFOの性質(zhì)を考えると、上部以外の要素に直接アクセスすることはできません。これには、最大値と最小値を追跡しながら、スタックを橫斷する必要があります。

2つの追加変數(shù)を使用

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

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

補(bǔ)助スタックを使用して

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

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()};
    }
}

修正されたスタック構(gòu)造を使用します

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

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};
    }
}

結(jié)論

スタック內(nèi)の最大の要素と最小の要素を探すことは、それぞれに利點(diǎn)と短所を備えたさまざまな方法で解決できます。示されている方法には、追加の変數(shù)、補(bǔ)助スタックの使用、最大値と最小値のための個別のスタックの管理、またはスタック自體の構(gòu)造の変更が含まれます。

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

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