Sorting numbers in Stack using one int variable

Question

I have a Stack variable (java collection) which holds five integers and I was also given one int variable. Is it possible to sort the numbers in the given stack. I am not able to solve that. Please post here if you have ideas.

Stack<Integer> s = new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);
int a;

We should not create any new variable except the one given in the above code snippet and also should not use Collections.sort(s).

Answer 1

Here i found the perfect answer from geeksforgeeks which uses recursion. http://www.geeksforgeeks.org/sort-a-stack-using-recursion/ Just posting the same algorithm here.

Algorithm:

We can use below algorithm to sort stack elements:

sortStack(stack S)
if stack is not empty:
    temp = pop(S);  
    sortStack(S); 
    sortedInsert(S, temp);

Below algorithm is to insert element is sorted order:

sortedInsert(Stack S, element)

if stack is empty OR element > top element
    push(S, elem)
else
    temp = pop(S)
    sortedInsert(S, element)
    push(S, temp)

Answer 2

You can use bubble sort to do it, as the following:

Stack<Integer> s = new Stack();
        s.push(5);
        s.push(3);
        s.push(4);
        s.push(1);
        s.push(1);

        int a = 0;
        while (a != s.size() - 1) {
            if (a != s.size() - 1) {
                if (s.elementAt(a) >= s.elementAt(a + 1)) {
                    a++;
                } else {
                    s.push(s.remove(a));
                    a = 0;
                }
            }
        }
        System.out.println(s.toString());

Answer 3

Terribly inefficient, but respects the rules :)

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a == -1) { // Here 'a' is used as a kind of boolean that tells us whether we need to keep checking for items to reorder or not.
    for (a = 0; a < s.size() - 1; a++) { // Now 'a' becomes stack element's index.
        if (s.get(a) > s.get(a + 1)) {
            a = s.remove(a); // Here 'a' again changes meaning and holds the value that needs to be reordered.
            s.push(a);
            a = -1; // And here, 'a' is back to being used as a kind of boolean flag to control the outer loop.
            break;
        }
    }
}

EDIT: Basically, I take advantage of the fact that I know that Stack extends Vector. So I don't actually have to use only the standard Pop and Push methods to access/remove elements. I can use normal List methods.

And then, I just squeeze the most use I can from a by using it for different purposes at different times (exit flag, loop index, temp storage for value to reorder). Normally a very bad programming practice.

So the algorithm is basically that I loop through the Stack elements. Any time I find an element that is greater than the next, then I remove it, and then place it at the end of the Stack. At that moment, I stop the loop, and reset a to -1 to make sure I start the loop again. I keep doing this until I am able to loop through all the stack items without needing to reorder anything.

EDIT 2: Here is another alternative that is a bit more complicated to read, but still respects the rules, and performs better following the bubble sort pattern. The principles used are pretty much the same as my first attempt (abusing the Stack as a List + using variable a for multiple uses).

Stack<Integer> s=new Stack<Integer>();
s.push(5);s.push(3);s.push(4);s.push(1);s.push(1);

int a = -1;
while (a < 0) { // keep looping if the previous loop performed at least one swap.
    a = 0;

    // if 'a' is >= 0, then it simply holds the index.
    // if 'a' < 0, then the index can be obtained by applying the bitwise complement operator.
    while ((a < 0 ? ~a : a) < (s.size() - 1)) { // loop all items except the last one.
        if (s.get(a < 0 ? ~a : a) > s.get((a < 0 ? ~a : a) + 1)) { // if this item is greater than the next, a swap is needed.
            s.insertElementAt(s.remove(a < 0 ? ~a : a), (a < 0 ? ~a : a) + 1); // swap this value with the next.

            // If this was not done already, flag the fact that a swap was performed by
            // applying the bitwise complement operator to 'a'.
            // This serves as a flag to let the outer loop know
            // that we'll need to perform the stack loop again.
            if (a >= 0) {
                a = ~a;
            }
        }

        // increment index. Or if the bitwise complement operator was applied,
        // then go the opposite way since the value is now negative.
        if (a >= 0) {
            a++;
        } else {
            a--;
        }
    }
}

EDIT 3: Revised my last algorithm to use the bitwise complement operator rather than Math.abs().

Also, I would like to point out that, unlike some other clever attempts, this algorithm doesn't really have any limitations. It won't potentially suffer from a StackOverflowException because of too many recursive calls, because no recursion is used. Memory used is stable. And you can have any int value in the Stack, even negative ones, and it will work fine.

Answer 4

It's possible to do, but you're going to be cheating a little bit - you're going to use a second stack to do it.

I don't mean that you're explicitly declaring another stack; you're going to be recursing through this method.

Bear in mind that this approach has some limitations; it can handle sequential data just fine (that is, it can reverse a stack just fine), but dealing with more jumbled data is a lot trickier as we can only see up to two elements in the future (peek and holder).

This also inverts the approach and doesn't order them in a way you'd prescribe (1 to 5), but figuring out the correct condition from the code should be a trivial matter.

The approach is:

• Handle null and empty stacks by returning what was given to us
• Handle a stack of size 1 by returning what was given to us
• In the process, we pop the stack and store that in the holder variable.

• If what's in the stack next is less than the holder variable, we act:

  • Pop the stack again, multiply it by 10, and add this to the holder. We do the multiplication here so that we can (roughly) store two ints at once.
  • Push the remainder value (holder % 10) into the stack.
  • Recurse, repeating the instructions.
  • Once recursion has exhausted, we push the value we multiplied by 10 back onto the array by dividing the holder by 10.

• Otherwise, we put back what we had found and return the stack.

public Stack<Integer> sortStack(Stack<Integer> stack) {
    // no-op on empty stacks
    if(null == stack || stack.empty()) {
        return stack;
    }

    // pop stack and place in holder
    while(true) {
        int holder = stack.pop();
        // no-op on stacks of size 1
        try {
            stack.peek();
        } catch(EmptyStackException e) {
            // Stack only had one element; put it back and return the stack
            stack.push(holder);
            return stack;
        }
        if(stack.peek() < holder) {
            holder += stack.pop() * 10;
            stack.push(holder % 10);
            stack = sortStack(stack);
            stack.push(holder / 10);
        } else {
            //put it back
            stack.push(holder);
            break;
        }
    }
    return stack;
}

Answer 5

Since Stack implements List and Integer implements Comparable just:

Collections.sort(s);