4
\$\begingroup\$

Maintain current element as the top element in the input stack. Pop all the elements on the ordered stack which are greater than the current element and push them in to the input stack and maintain a count of these elements. Now push the current element into the ordered stack and pop the count number of elements from the input stack and push them into the ordered stack and return the ordered stack.

public class sortStackInAscending {

    public static void main(String args[]) {
        Stack<Integer> inputStack = new Stack<>();
        int size = 1000;
        Random ran = new Random();
        while (size > 0) {
            inputStack.push(ran.nextInt(size));
            size--;
        }
        Stack<Integer> orderedStack = sortStack(inputStack);
        printStack(orderedStack);
    }

    public static void printStack(Stack<Integer> anyStack) {
        int size = anyStack.size();
        Stack<Integer> tempStack = new Stack<>();
        int temp;
        while (size > 0) {
            temp = anyStack.pop();
            System.out.print(temp + " ");
            tempStack.push(temp);
            size--;
        }
        System.out.println();
        anyStack = tempStack;

    }

    public static Stack<Integer> sortStack(Stack<Integer> inputStack) {
        Stack<Integer> orderedStack = new Stack<>();
        int count = 0;
        int currentElement;
        while (!inputStack.isEmpty()) {
            currentElement = inputStack.pop();
            // pop elements > current element from ordered stack and
            // push them into input stack and maintain the count
            while (!orderedStack.isEmpty()
                    && currentElement < (int) orderedStack.peek()) {
                inputStack.push(orderedStack.pop());
                count++;
            }
            // insert the current element into its correct position in ordered
            // stack
            orderedStack.push(new Integer(currentElement));
            // pop count number of elements from input stack and push them into
            // ordered stack
            while (count > 0) {
                orderedStack.push(inputStack.pop());
                count--;
            }
        }
        return orderedStack;
    }
}
\$\endgroup\$
3
\$\begingroup\$

1 Code

In my opinion, your code would be a little more readable if you had a blank line before and after such constructs as while, for and if. So, instead of

Random ran = new Random();
while (size > 0) {
    inputStack.push(ran.nextInt(size));
    size--;
}
Stack<Integer> orderedStack = sortStack(inputStack);

you could have

Random ran = new Random();

while (size > 0) {
    inputStack.push(ran.nextInt(size));
    size--;
}

Stack<Integer> orderedStack = sortStack(inputStack);

2 printStack

Collections.<Integer>reverse(inputStack);
System.out.println(inputStack);

does the job with funky brackets and commas.

3 Naming

sortStackInAscending is not a very good name. Perhaps StackSorter?

4 Sorting

Usually, sorting routines do not return the sorted result, but rather modify its argument collection. That's the way most production sorts work in practice.

Summa summarum

A sub-point: making your stack sort generic is not hard; see below.

All in all, I had this in mind:

public class StackSorter {

    public static void main(String args[]) {
        Stack<Integer> inputStack = new Stack<>();
        int size = 10;
        Random ran = new Random();

        while (size > 0) {
            inputStack.push(ran.nextInt(size));
            size--;
        }

        sortStack(inputStack);

        System.out.println("Stack is sorted: " + stackIsSorted(inputStack));
        Collections.<Integer>reverse(inputStack);
        System.out.println(inputStack);
    }

    public static <E extends Comparable<? super E>> 
        boolean stackIsSorted(final Stack<E> stack) {
        if (stack.isEmpty()) {
            // Trivially sorted.
            return true;
        }

        final Stack<E> workStack = new Stack<>();
        workStack.addAll(stack);

        E previousElement = workStack.pop();

        while (!workStack.isEmpty()) {
            final E currentElement = workStack.pop();

            if (currentElement.compareTo(previousElement) > 0) {
                return false;
            }

            previousElement = currentElement;
        }

        return true;
    }

    public static <E extends Comparable<? super E>> 
        void sortStack(final Stack<E> inputStack) {
        final Stack<E> orderedStack = new Stack<>();
        E currentElement;
        int count = 0;

        while (!inputStack.isEmpty()) {
            currentElement = inputStack.pop();

            while (!orderedStack.isEmpty() 
                    && currentElement.compareTo(orderedStack.peek()) < 0) {
                inputStack.push(orderedStack.pop());
                count++;
            }

            orderedStack.push(currentElement);

            while (count > 0) {
                orderedStack.push(inputStack.pop());
                count--;
            }
        }

        inputStack.addAll(orderedStack);
    }
}

Hope that helps.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.