Sort Integer Stack in Ascending Order

Given an Integer Stack in Java, sort the stack in increasing order (Ascending Order)

Examples:

Input : Stack: [10, 2, 16, 5, 9, 1] Peek: 1
Output : Stack: [1, 2, 5, 9, 10, 16] Peek: 16

Recommended: Design and Implement Special Stack Data Structure

Approach:
The idea is, pop every element from the original stack and compares it with the temporary stack.
If the popped element from the original stack is less than peek element of the temporary stack, then push the temp stack element to the original stack, call this recursively, until temp is not empty and then push the element at the right place.
Else push the element to the temp stack if the original stack element popped is greater than the temp stack.

Implementation in Java:

// Java Program to sort an Integer Stack
import java.util.Stack;

public class SortStack {
    // Method which returns a sorted stack
    static Stack<Integer> sortStack(Stack<Integer> stack) {
        // Create another temporary stack
        Stack<Integer> tempStack = new Stack<Integer>();
        // Iterate until the original stack is empty
        while (!stack.isEmpty()) {
            // Popped element from the original stack
            int s = stack.pop();

            // Check for the specified condition
            while (!tempStack.isEmpty() && (tempStack.peek() > s))
                stack.push(tempStack.pop());

            // Pushed in the temp stack
            tempStack.push(s);
        }

        // Return the stack
        return tempStack;
    }

    // Driver Code
    public static void main(String[] args) {
        // Declare the Stack and Initialize the elements in it
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(10);
        stack.push(2);
        stack.push(16);
        stack.push(5);
        stack.push(9);
        stack.push(1);

        // Print before sorting
        System.out.println(stack + " Peek: " + stack.peek());

        // Sort the stack
        stack = sortStack(stack);

        // Print after sorting
        System.out.println(stack + " Peek: " + stack.peek());
    }
}

Output:

[10, 2, 16, 5, 9, 1] Peek: 1
[1, 2, 5, 9, 10, 16] Peek: 16

Time Complexity: O(n^2) 
Space Complexity: O(n)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.