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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告