棧是遵循后進(jìn)先出原則（也稱為L(zhǎng)IFO）的基本數(shù)據(jù)結(jié)構(gòu)。棧有很多用例，例如組織函數(shù)調(diào)用和撤消操作。通常，人們可能會(huì)遇到查找棧中最大和最小元素的問(wèn)題，本文將演示使用Java完成此任務(wù)的多種方法。

理解棧

棧是一種線性數(shù)據(jù)結(jié)構(gòu)，只允許在一端進(jìn)行操作，稱為頂部。主要操作包括：

• 壓棧 (Push)：將元素添加到棧頂。
• 彈出 (Pop)：移除并返回棧頂元素。
• 查看 (Peek)：查看棧頂元素而不將其移除。
• 是否為空 (IsEmpty)：檢查棧是否為空。

問(wèn)題陳述

目標(biāo)是確定棧中的最大和最小元素。鑒于棧的LIFO特性，無(wú)法直接訪問(wèn)除頂部以外的元素。這需要遍歷棧，同時(shí)跟蹤最大值和最小值。

使用兩個(gè)附加變量

在這里，我們使用兩個(gè)變量 min 和 max 分別跟蹤最小值和最大值。遍歷棧，并在處理每個(gè)元素時(shí)更新這些變量。這是最簡(jiǎn)單的方法，也是最耗時(shí)和最耗空間的方法。

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

輸出

使用輔助棧

在這里，我們通過(guò)使用彈出操作并根據(jù)需要更新最小值和最大值來(lái)遍歷棧。輔助棧臨時(shí)保存元素，然后將這些元素恢復(fù)到原始棧中。

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

輸出

使用兩個(gè)棧

這種方法使用兩個(gè)額外的棧，一個(gè)用于記住最大元素（maxStack），另一個(gè)用于記住最小元素（minStack）。每次一個(gè)新元素進(jìn)入主棧時(shí)，如果它使最大值或最小值變大，我們也將其放入 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()};
    }
}

輸出

使用修改后的棧結(jié)構(gòu)

棧結(jié)構(gòu)被修改為在其自身內(nèi)包含最大值和最小值以及常規(guī)棧元素。每個(gè)元素都保存為一個(gè)對(duì)，包含值、當(dāng)前最大值和當(dāng)前最小值。

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é)論

查找棧中最大和最小元素可以通過(guò)不同的方式來(lái)解決，每種方式都有其優(yōu)點(diǎn)和缺點(diǎn)。所示方法包括使用額外變量、輔助棧、為最大值和最小值管理單獨(dú)的棧或更改棧本身的結(jié)構(gòu)。

每種技術(shù)都提供了一種特定方法來(lái)處理訪問(wèn)或保存棧項(xiàng)的問(wèn)題，這使得它根據(jù)內(nèi)存限制、性能需求和數(shù)據(jù)完整性需求而適合某些情況。了解和應(yīng)用這些方法可以幫助開(kāi)發(fā)人員有效地處理Java中的棧，使他們的應(yīng)用程序最適合某些情況。

以上是Java程序在堆棧中找到最大和最小元素的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！