Java program to sort the elements of the stack in descending order

This article demonstrates how to sort a stack's elements in descending order using Java. A stack, adhering to the Last-In-First-Out (LIFO) principle, is a fundamental data structure. Think of a browser's history; the most recently visited site is accessed first. We'll explore a recursive Java solution for this sorting task.

Problem:

Given an unsorted stack of integers, arrange its elements in descending order (largest element at the top).

Input Example:

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

Output Example:

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

Recursive Java Solution:

Our approach employs recursion to efficiently sort the stack. The process involves these steps:

1. sortStack(Stack<integer> stack)</integer> Method: This recursive method iteratively removes elements from the input stack until it's empty. Each removed element is temporarily stored, and the sortStack method recursively calls itself on the remaining stack.

2. sortedInsert(Stack<integer> stack, int element)</integer> Helper Method: This method handles the insertion of the temporarily removed elements back into the stack, maintaining descending order. It checks if the stack is empty or if the element to be inserted is greater than the current top element. If either condition is true, the element is pushed onto the stack. Otherwise, the top element is temporarily removed, sortedInsert is recursively called, and then the temporarily removed element is pushed back.

3. Main Method: The main method creates a sample stack, calls sortStack to sort it, and then prints the sorted stack.

Here's the complete Java code:

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>

Time and Space Complexity:

• Time Complexity: O(N²), where N is the number of elements in the stack. This is due to the nested nature of the recursive calls.
• Space Complexity: O(N) due to the recursive call stack.

This recursive approach provides a clear and concise solution for sorting a stack in descending order in Java. The use of a helper function improves code readability and organization.

The above is the detailed content of Java program to sort the elements of the stack in descending order. For more information, please follow other related articles on the PHP Chinese website!