0

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());


    }
2
Contributors
6
Replies
10
Views
4 Years
Discussion Span
Last Post by Taywin
Featured Replies
  • 2

    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 … Read More

  • 1

    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 … Read More

  • 2

    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) … Read More

2

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.

0

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?

1

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.

0

Taywin, have you checked the link I posted earlier?

Thanks!

2

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.

Edited by Taywin

Comments
You didn't have to write the code. Really excellent explanation and you're right! I don't think they want us to use a very inefficient method.
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.