Program Java untuk mencari elemen maksimum dan minimum dalam timbunan

Stack adalah struktur data asas yang mengikuti prinsip pertama yang terakhir (juga dikenali sebagai LIFO). Terdapat banyak kes penggunaan untuk timbunan, seperti penganjuran fungsi panggilan dan operasi undoing. Sering kali, seseorang mungkin menghadapi masalah mencari unsur -unsur terbesar dan terkecil dalam timbunan, dan artikel ini akan menunjukkan pelbagai cara untuk mencapai tugas ini menggunakan Java.

Memahami Stack

Stack adalah struktur data linear yang membolehkan operasi hanya pada satu hujung, yang dipanggil bahagian atas. Operasi utama termasuk:

tolak (push)
• : Tambah elemen ke bahagian atas timbunan.
pop (pop)
• : Menghapuskan dan kembali ke elemen atas timbunan.
Lihat (mengintip)
• : Lihat elemen atas timbunan tanpa mengeluarkannya.
isEmpty (isEmpty)
• : periksa sama ada timbunan kosong.
Pernyataan Masalah

Matlamatnya adalah untuk menentukan unsur maksimum dan minimum dalam timbunan. Memandangkan sifat lifo timbunan, unsur -unsur selain daripada bahagian atas tidak dapat diakses secara langsung. Ini memerlukan melintasi timbunan sambil menjejaki nilai maksimum dan minimum.

Gunakan dua pembolehubah tambahan

di sini, kami menggunakan dua pembolehubah

dan

untuk menjejaki nilai minimum dan maksimum masing -masing. Keluarkan di atas timbunan dan kemas kini pembolehubah ini kerana setiap elemen diproses. Ini adalah kaedah yang paling mudah, dan kaedah yang paling memakan masa dan memakan ruang.

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

Unsur maksimum: 30 Elemen minimum: 5

Menggunakan timbunan tambahan

di sini, kami melintasi timbunan dengan menggunakan operasi pop timbul dan mengemas kini nilai minimum dan maksimum seperti yang diperlukan. Tumpukan tambahan sementara menjimatkan unsur -unsur dan kemudian mengembalikan unsur -unsur ini ke timbunan asal.

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

Unsur maksimum: 30 Elemen minimum: 5

Gunakan dua timbunan

Kaedah ini menggunakan dua susunan tambahan, satu untuk mengingati elemen terbesar (

) dan yang lain untuk mengingati elemen terkecil (). Setiap kali elemen baru memasuki timbunan utama, jika ia menjadikan nilai maksimum atau minimum lebih besar, kami juga memasukkannya ke dalam

atau

. maxStack minStack maxStack minStack

output

Unsur maksimum: 30 Elemen minimum: 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()};
    }
}

Gunakan struktur timbunan yang diubah suai

Struktur timbunan diubahsuai untuk memasukkan nilai maksimum dan minimum dan elemen timbunan biasa dalam dirinya sendiri. Setiap elemen disimpan sebagai pasangan yang mengandungi nilai, nilai maksimum semasa, dan nilai minimum semasa.

output

Unsur maksimum: 30 Elemen minimum: 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};
    }
}

Kesimpulan

Mencari unsur -unsur terbesar dan terkecil dalam timbunan dapat diselesaikan dengan cara yang berbeza, masing -masing dengan kelebihan dan kekurangannya. Kaedah yang ditunjukkan termasuk menggunakan pembolehubah tambahan, susunan tambahan, menguruskan susunan berasingan untuk nilai maksimum dan minimum, atau mengubah struktur timbunan itu sendiri.

Setiap teknologi menyediakan cara khusus untuk menangani akses atau menyimpan item timbunan, yang menjadikannya sesuai untuk situasi tertentu berdasarkan batasan memori, keperluan prestasi, dan keperluan integriti data. Memahami dan memohon kaedah ini boleh membantu pemaju mengendalikan susunan dengan berkesan di Java, menjadikan aplikasi mereka paling sesuai untuk situasi tertentu.

Atas ialah kandungan terperinci Program Java untuk mencari elemen maksimum dan minimum dalam timbunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!