Java程式：按降序排列棧元素

在本文中，我們將學習如何按降序排列棧元素。棧是一種遵循後進先出 (LIFO) 原則的資料結構，這意味著最後新增的專案首先被移除。棧的一個現例項子是瀏覽器歷史記錄，其中最近訪問的網站會首先顯示。本文將討論如何在Java中按降序排列棧元素。

問題陳述

在給定的問題中，我們有一個包含未排序整數元素的棧，我們需要將其按降序排列，這意味著最大的元素在頂部，最小的元素在底部。

輸入

Original Stack: [4, 2, 9, 7]

輸出

Original Stack: [4, 2, 9, 7]

Sorted Stack in Descending order: [9, 7, 4, 2]

使用遞迴方法對元素進行排序的Java程式

我們將使用遞迴來對棧進行排序。以下是按降序排列棧的步驟：

  • 從java.util匯入Stack類以使用棧資料結構。
  • sortStack方法將遞迴地從棧中移除每個元素，直到棧為空，並將移除的元素臨時儲存。
  • 在sortStack中，使用stack.pop()移除頂部元素，並再次呼叫sortStack，直到所有元素都被移除。這為按降序插入做好了準備。
  • 一旦棧為空，就開始將每個移除的元素插入到正確的位置。
  • sortedInsert輔助方法檢查棧是否為空，或者要插入的元素是否大於當前頂部元素。如果是，則將其壓回棧中。
  • 如果元素較小，則臨時移除頂部元素，遞迴呼叫sortedInsert，然後將臨時移除的元素壓回。
  • 排序後，顯示棧以顯示其現在按降序排列。

用於對棧元素進行排序的Java程式

以下是使用遞迴方法按降序排列棧元素的Java程式：

import java.util.Stack;
public class StackSorter {
    public static void sortStack(Stack<Integer> stack) {
        if (!stack.isEmpty()) {
            int top = stack.pop(); // Remove the top element
            sortStack(stack); // Sort remaining stack recursively
            sortedInsert(stack, top); // Insert the removed item back in sorted order
        }
    }
    // Helper method
    public static void sortedInsert(Stack<Integer> stack, int element) {
        // Insert element when stack is empty or element is greater than top
        if (stack.isEmpty() || element > stack.peek()) {
            stack.push(element);
            return;
        }
        int temp = stack.pop();
        sortedInsert(stack, element);
        stack.push(temp); // Place the held-back element on top
    }
    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);
    }
}

輸出

Original Stack: [4, 2, 9, 7]
Sorted Stack in Descending order: [9, 7, 4, 2]

時間複雜度：O(N2)

空間複雜度：O(N)

程式碼解釋

在上面的程式中，我們將使用遞迴按降序排列棧。首先，它一個接一個地移除每個元素，直到棧為空。然後，使用sortedInsert輔助函式，將每個移除的元素插入到其正確的位置以保持降序。如果元素大於棧頂，則將其壓回；否則，該函式將臨時彈出棧頂元素，插入元素，然後將彈出的元素壓回。最後，列印排序後的棧，顯示從高到低的元素排列。

更新於：2024年10月30日

41 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告