Transferring elements from stack to another?

[sobias]

Hi guys, Finally I've registered after being a very long visitor for this awesome community.

I have this problem which consumed 2 days of my time trying to figure out how to solve it. And your help is needed guys.

The problem says: Transfer elemenents from Stack1 to Stack2 , without using additional stack, recursion or arrays. Only using some additional variables. Stack2 should have the same order as in Stack1.

what I understand from the word "Transfer" , this is going to be a desructive copy operation, because stack1 will be empty.

My attempt does not work for any stack size. The snippet below for a 3 elements stack and it works fine. Some guy gave me a hint to use 2 loops and an if statement to make it working for any size. But I failed. I don't know how exactly this could work.

public static void stackSwitch(Stack stack1){

        Stack stack2 = new Stack();
        Object top = stack1.topEl();


        //save the top
        top = stack1.pop();
        stack2.push(stack1.pop());
        stack2.push(stack1.pop());

        //push it back
        stack1.push(top);
        stack1.push(stack2.pop());
        stack1.push(stack2.pop());

        //save the top
        top = stack1.pop();
        stack2.push(stack1.pop()); // The bottom is left in Stack1
        stack2.push(top);
        stack1.push(stack2.pop());
        stack1.push(stack2.pop());


        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }

        System.out.println(stack1.toString());
        System.out.println(stack2.toString());


    }

[Taywin]

I think your requirement is to use recursive call. It is not that difficult with recursion. What you need to do is to pop it every time you are in a recursive call, and keep popping until the stack1 is empty. Then push back to stack2 after the recursive call returned.

public static void stackSwitch(Stack st1, Stack st2) {
  // no base case but check if st1 is empty
  // if not empty, pop from st1 and store in local
  // call stackSwitch again
  // push the element popped from st1 to st2
}

The stack2 will contain stack1 data and stack1 will be empty after it is out.

[sobias]

Taywin, I solved it using recursion already an it's very easy.
I will post my code when I gey back home today.
Anyways, are you saying it's not possible to implement this without recursion?

[Taywin]

It is possible implement it without a recursion, but you would use a dynamic array instead (ArrayList and insert at 0 index). Then push back onto stack2.

Using recursive call to transfer to another stack is easy because it is exactly how a stack works. That's why recursion should be the way to go.

[sobias]

Please check this link out. Click Here

Appreciate your time for me.

[sobias]

Taywin, have you checked the link I posted earlier?

Thanks!

[Taywin]

What do you want to know about that algorithm? Also, it is O(N^2) which is bad. You could do it in O(N) both the same or reverse order. Recursion is for stack. For a code of recursion below (as Java syntax), you should see that it is O(N), not O(N^2) because you go through the source stack once (N) and then push back to the target (N). It is 2N which is the same as O(N).

Stack source;
Stack target;
... // fill in source, and target is an empty stack

private void copyStack(Stack s, Stack t) {
  if (!s.isEmpty()) {
    ObjectItem item = s.pop();
    //t.push(item);    // push here for the reverse order
    copyStack(s, t);
    t.push(item);    // push here for the same order
  }
}

I would suggest either try to learn LISP or Scheme for more in-depth recursion. Both languagues taught me how to deal with recursion because you must think in recursion all the time (it is the way the languages are). :)

PS: When you deal with recursion, try NOT to use it with an algorithm that has O(N^2) or higher because it requires a lot of memory. Recursion could get you in trouble real quick. If an algorithm is that slow, use iteration instead if possible.

PSS: I intended to show a bit different implementaion in Java syntax. You should be able to adapt it to your current implementation.