Java程序在堆栈中找到最大和最小元素

栈是遵循后进先出原则（也称为LIFO）的基本数据结构。栈有很多用例，例如组织函数调用和撤消操作。通常，人们可能会遇到查找栈中最大和最小元素的问题，本文将演示使用Java完成此任务的多种方法。

理解栈

栈是一种线性数据结构，只允许在一端进行操作，称为顶部。主要操作包括：

• 压栈 (Push)：将元素添加到栈顶。
• 弹出 (Pop)：移除并返回栈顶元素。
• 查看 (Peek)：查看栈顶元素而不将其移除。
• 是否为空 (IsEmpty)：检查栈是否为空。

问题陈述

目标是确定栈中的最大和最小元素。鉴于栈的LIFO特性，无法直接访问除顶部以外的元素。这需要遍历栈，同时跟踪最大值和最小值。

使用两个附加变量

在这里，我们使用两个变量 min 和 max 分别跟踪最小值和最大值。遍历栈，并在处理每个元素时更新这些变量。这是最简单的方法，也是最耗时和最耗空间的方法。

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

使用辅助栈

在这里，我们通过使用弹出操作并根据需要更新最小值和最大值来遍历栈。辅助栈临时保存元素，然后将这些元素恢复到原始栈中。

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

使用两个栈

这种方法使用两个额外的栈，一个用于记住最大元素（maxStack），另一个用于记住最小元素（minStack）。每次一个新元素进入主栈时，如果它使最大值或最小值变大，我们也将其放入 maxStack 或 minStack 中。

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

输出

最大元素: 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};
    }
}

输出

最大元素: 30 最小元素: 5

结论

查找栈中最大和最小元素可以通过不同的方式来解决，每种方式都有其优点和缺点。所示方法包括使用额外变量、辅助栈、为最大值和最小值管理单独的栈或更改栈本身的结构。

每种技术都提供了一种特定方法来处理访问或保存栈项的问题，这使得它根据内存限制、性能需求和数据完整性需求而适合某些情况。了解和应用这些方法可以帮助开发人员有效地处理Java中的栈，使他们的应用程序最适合某些情况。

以上是Java程序在堆栈中找到最大和最小元素的详细内容。更多信息请关注PHP中文网其他相关文章！