This Java program demonstrates how to sort elements in one stack using another temporary stack. The algorithm leverages the properties of the stack to reverse the order of elements such that the smallest items are on top.

Program Structure

The program includes:

• Main Class and Method: Execution starts in the main method where we initialize the stack and perform sorting.
• Sorting Method: A separate method sortStack is used to perform the sorting using a temporary stack.

Java Code

import java.util.Stack;

public class StackSorter {
    public static void main(String[] args) {
        Stack<Integer> originalStack = new Stack<>();
        originalStack.push(34);
        originalStack.push(3);
        originalStack.push(31);
        originalStack.push(98);
        originalStack.push(92);
        originalStack.push(23);

        Stack<Integer> sortedStack = sortStack(originalStack);

        System.out.println("Sorted Stack: " + sortedStack);
    }

    public static Stack<Integer> sortStack(Stack<Integer> input) {
        Stack<Integer> tempStack = new Stack<>();
        while (!input.isEmpty()) {
            int tmp = input.pop();
            while (!tempStack.isEmpty() && tempStack.peek() > tmp) {
                input.push(tempStack.pop());
            }
            tempStack.push(tmp);
        }
        return tempStack;
    }
}

How the Program Works

The sortStack function works by:

1. Popping an element from the original stack.
2. Comparing the popped element with the elements of the temporary stack.
3. Transferring elements back to the original stack if they are greater than the popped element.
4. Pushing the popped element into the temporary stack in its correct position.

This ensures that the temporary stack always maintains elements in ascending order.

Explanation

• Main Method: Initializes the stack with unsorted numbers and calls the sortStack method.
• sortStack Method: This method takes the original stack as input and uses a temporary stack to sort the elements. It ensures that the temporary stack holds the elements in descending order, and thus when all elements are transferred from the original to the temporary stack, they are sorted.
• Sorting Logic: The program iteratively compares the top elements of the original and temporary stacks, moving elements between the two stacks to maintain order in the temporary stack.

Conclusion

This method efficiently sorts a stack using only another stack for storage, leveraging the LIFO (last-in-first-out) nature of stacks to reverse the order of the largest elements to the smallest, making it ideal for problems where additional storage needs to be minimized.