Stack is a basic data structure that follows the last-in first-out principle (also known as LIFO). There are many use cases for the stack, such as organizing function calls and undoing operations. Often, one may encounter the problem of finding the largest and smallest elements in the stack, and this article will demonstrate multiple ways to accomplish this task using Java.

Understanding Stack

Stack is a linear data structure that allows operations only at one end, called the top. Main operations include:

• Push (Push): Add elements to the top of the stack.
• Pop (Pop): Removes and returns to the top element of the stack.
• View (Peek): View the top element of the stack without removing it.
• IsEmpty (IsEmpty): Check whether the stack is empty.

Problem Statement

The goal is to determine the maximum and minimum elements in the stack. Given the LIFO nature of the stack, elements other than the top cannot be accessed directly. This requires traversing the stack while keeping track of the maximum and minimum values.

Use two additional variables

Here, we use two variables min and max to track the minimum and maximum values ??respectively. Iterate over the stack and update these variables as each element is processed. This is the easiest method, and the most time-consuming and space-consuming method.

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

Output

Using the auxiliary stack

Here, we traverse the stack by using a pop-up operation and updating the minimum and maximum values ??as needed. The auxiliary stack temporarily saves elements and then restores these elements to the original stack.

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

Output

Use two stacks

This method uses two extra stacks, one for remembering the largest element (maxStack) and the other for remembering the smallest element (minStack). Every time a new element enters the main stack, if it makes the maximum or minimum value larger, we also put it in maxStack or 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()};
    }
}

Output

Use the modified stack structure

The stack structure is modified to include the maximum and minimum values ??and regular stack elements within itself. Each element is saved as a pair containing the value, the current maximum value, and the current minimum value.

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

Output

Conclusion

Looking for the largest and smallest elements in the stack can be solved in different ways, each with its advantages and disadvantages. The methods shown include using additional variables, auxiliary stacks, managing separate stacks for maximum and minimum values, or changing the structure of the stack itself.

Each technology provides a specific way to deal with access or saving stack items, which makes it suitable for certain situations based on memory limitations, performance requirements, and data integrity requirements. Understanding and applying these methods can help developers effectively handle stacks in Java, making their applications best suited for certain situations.

The above is the detailed content of Java program to find the maximum and minimum elements in a stack. For more information, please follow other related articles on the PHP Chinese website!