Program Java untuk menyusun unsur -unsur timbunan dalam urutan menurun

Artikel ini menunjukkan cara menyusun unsur -unsur stack dalam urutan menurun menggunakan Java. Tumpukan, mematuhi prinsip terakhir (LIFO), adalah struktur data asas. Fikirkan sejarah penyemak imbas; Tapak yang paling baru -baru ini dikunjungi diakses terlebih dahulu. Kami akan meneroka penyelesaian Java rekursif untuk tugas penyortiran ini.

Masalah:

diberi tumpukan bilangan bulat yang tidak disusun, mengatur unsur -unsurnya dalam urutan menurun (elemen terbesar di bahagian atas).

Contoh input:

<code>Original Stack: [4, 2, 9, 7]</code>

Output Contoh:

<code>Sorted Stack in Descending Order: [9, 7, 4, 2]</code>

Penyelesaian Java Rekursif:

Pendekatan kami menggunakan rekursi untuk menyusun susunan dengan cekap. Proses ini melibatkan langkah -langkah ini:

1. Kaedah: sortStack(Stack<integer> stack)</integer> Kaedah rekursif ini secara beransur -ansur menghilangkan elemen dari timbunan input sehingga ia kosong. Setiap elemen yang dikeluarkan disimpan sementara, dan kaedah secara rekursif memanggil dirinya pada timbunan yang tinggal. sortStack

2. Kaedah penolong: sortedInsert(Stack<integer> stack, int element)</integer> Kaedah ini mengendalikan penyisipan unsur -unsur yang dikeluarkan sementara kembali ke dalam timbunan, mengekalkan urutan menurun. Ia memeriksa jika timbunan kosong atau jika elemen dimasukkan lebih besar daripada elemen atas semasa. Jika salah satu keadaan adalah benar, elemen itu ditolak ke timbunan. Jika tidak, elemen teratas dikeluarkan sementara, dipanggil secara rekursif, dan kemudian unsur yang dikeluarkan sementara ditolak. sortedInsert

Kaedah Utama

3. Kaedah: Kaedah membuat timbunan sampel, panggilan main untuk menyusunnya, dan kemudian mencetak timbunan yang disusun. sortStack

inilah kod Java yang lengkap:

import java.util.Stack;

public class StackSorter {

    public static void sortStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            int top = stack.pop();
            sortStack(stack);
            sortedInsert(stack, top);
        }
    }

    public static void sortedInsert(Stack<Integer> stack, int element) {
        if (stack.isEmpty() || element > stack.peek()) {
            stack.push(element);
            return;
        }
        int temp = stack.pop();
        sortedInsert(stack, element);
        stack.push(temp);
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(4);
        stack.push(2);
        stack.push(9);
        stack.push(7);

        System.out.println("Original Stack: " + stack);
        sortStack(stack);
        System.out.println("Sorted Stack in Descending Order: " + stack);
    }
}

output:

<code>Original Stack: [4, 2, 9, 7]
Sorted Stack in Descending Order: [9, 7, 4, 2]</code>

kerumitan masa dan ruang:

• kerumitan masa: o (n 2 ^{), di mana n adalah bilangan elemen dalam timbunan. Ini disebabkan sifat bersarang panggilan rekursif.}
• kerumitan ruang: o (n) kerana timbunan panggilan rekursif.

Pendekatan rekursif ini memberikan penyelesaian yang jelas dan ringkas untuk menyusun timbunan dalam urutan menurun di Jawa. Penggunaan fungsi pembantu meningkatkan pembacaan dan organisasi kod.

Atas ialah kandungan terperinci Program Java untuk menyusun unsur -unsur timbunan dalam urutan menurun. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!