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中文網其他相關文章！