CSE Question (JAVA, Stacks, Copy() Method)

[Janus]

Hey guys, I am completely stuck with writing a method for copying a stack (a deep copy). I have a midterm tomorrow, my GTA told us yesterday that this will be on there (followed by a brief introduction to Stacks, not even close to the complicatedness of this method).

If anyone has any idea on how to write this I would be very appreciative.

[TheMOB]

Do you mean taking a Stack object and just copying the contents? You just have to pop everything in it into a temporary Stack, and then pop the temporary Stack and push everything in it into the copy of the original.

edit:

To be more specific, make a loop that will keep popping your original stack until it's empty. Everytime you pop an object from it, push that object into a temporary stack. Once you've emptied it, do the same thing again only with your temporary stack and a third stack that will hold the copy of the original.

second edit:
if you need to make sure the original Stack isn't altered, when you pop the temp Stack, store each popped object in a temporary variable, then push that variable onto your original Stack and the copied version of it.

[Janus]

thanks TheMOB, I was thinking the same thing, just making sure that my implementation/theory is right.

hmm, I can think of how to do it iteratively, but I am stuck with recursively. I know that when the temporary node hits null that is the base case, I am just trying to think of how to code it.

[TheMOB]

Yikes, why are you trying to do it recursively? That would be really confusing to implement, and not really offer any benefit over an iterative solution. I guess you could have a method that takes two Stacks and pops one and pushes it into the other, and if the Stack you're trying to pop from is empty, return the one you're pushing into, otherwise, call itself again. You could run through that once to fill up the temporary Stack, and then again to fill the copy, but that would leave the original Stack empty. Unless your teacher told you you're going to have to do this recursively on your exam and keep the original Stack intact I wouldn't worry about it.

[Janus]

hmm, I see what you mean by it being over complicated.

does this look right from my implementation of iteration:

-- Edit: updated code


public Stack copy()
{
// deep copy of stack
// create a new stack whose elements are exactly the same as elements in
// original stack

Stack st1 = new Stack();
Stack st2 = new Stack();
Node temp = this.pop();

while(temp!=null)
{
st1.push(this.pop());
}

Node temp2 = st1.pop();
while(temp2!=null)
{
st2.push(st1.pop());
}

return st2;
}


for one of the practice problems he gave us he asked us to do a copy() method that is static, meaning we do not have directly access to the top node of the stack, which is what through me off at first. I thought that the only good way to do it might be recursively or something, but I still think I could do it iteratively, just that I would have to label the top one as top I guess?

[TheMOB]

What is this .top method? I didn't think there was such a thing. Just .empty(), .push(), .pop(), .peek(), and .search() (not even sure about that last one). I'm not exactly sure what temp.getNext() is doing either. Shouldn't you be storing the next item in the stack in there using that top() method (I'm guessing that will return what's on top of the stack without removing it)? Also if you want the original Stack to not be empty you have to refill it in the second part as well. Adding a line that says this.top = temp2; would work, I think.

[Janus]

I was wrong, there isn't a .top method, don't know what I was thinking there.

I'm re-writing it now, I will get back to you.


public Stack copy()
{
// deep copy of stack
// create a new stack whose elements are exactly the same as elements in
// original stack

Stack st1 = new Stack();
Stack st2 = new Stack();
Node temp = this.pop();

while(temp!=null)
{
st1.push(this.pop());
}

Node temp2 = st1.pop();
while(temp2!=null)
{
st2.push(st1.pop());
}

return st2;
}

[TheMOB]

That's pretty close to the method I wrote, but you have a few problems there. Right now your while loops are infinite, because temp1 and temp2 never get changed once the loops begin. You're better off using the .empty() method to test whether or not the Stack you're popping is empty. If you want I can post the method I wrote to do it, it's pretty close to what you have there.

[Janus]

so instead of temp!=null, I just need to use while(!this.empty()) and while(!st1.empty())? - I have also made an isEmpty() method that basically checks to see if the top==null, if so true, if not false. either way it probably does the same thing.

Oh, and I would be very appreciative if I could see your method bud.

[TheMOB]

so instead of temp!=null, I just need to use while(!this.empty()) and while(!st1.empty())?Right.
I have also made an isEmpty() method that basically checks to see if the top==null, if so true, if not false. either way it probably does the same thing. Yeah, you could (and did, apparently) basically do the same thing yourself by having a method that does a peek() and checks to see if it returns null.

Oh, and I would be very appreciative if I could see your method bud.Sure thing
public Stack copy()
{
// deep copy of stack
// create a new stack whose elements are exactly the same as elements in
// original stack

Stack st1 = new Stack();
Stack st2 = new Stack();
Object temp;

while (!this.empty())
st1.push(this.pop());

while(!st1.empty()) {
temp = st1.pop();
this.push(temp); //ensures that the stack your copying doesn't get erased
st2.push(temp);
}
return st2;
}
I'm 99% sure this is right. The only thing I'm not sure of is if you can use an Object to take what you pop from the Stack. You might have to make it more specific type (like Node if it's a stack of Nodes or String if it's a stack of Strings, etc.)

[Janus]

oh, so like Node x = this.pop(); st1.push(x); (assuming Nodes)?

[TheMOB]

I actually just looked it up in an old assignment I did. I used it like this
Integer n = (Integer) s.pop();
Which means that Stack.pop() returns something of type Object (it might be called type E, actually) that doesn't really mean anything by itself but can be cast as some defined object (like Node, or Integer). So in your example you'd have to do Node x = (Node) this.pop(), assuming the Stack actually has Nodes in it. I think you'd get a runtime error if the Stack actually had Integers or Strings in it. st1.push(this.pop()); works too, of course.

[Janus]

thanks a lot!

[hawk]

You shouldn't have to cast it unless the types don't match.

[Hampster]

You shouldn't have to cast it unless the types don't match.
You'll get a warning though. Not to mention that it's better style to cast it if you have multiple stacks containing different types of elements. :)

My intro programming class a couple years ago used .top().. it basically was the same thing as .peek().

[Mulchman MM]

STL stack has a top function (but that's not java, heh)

[Janus]

hey, a quick addition to these great replies. I have been stuck with a similar problem, although I am completely lost on how to interact with a stack without being able to use stack functions (if I am reading the question correctly):

"Write a copy method for stacks that does not belong to the Stack class itself. (this means you can't go accessing the top pointer.) Try to implement it without using two loops.

public static Stack copy(Stack orig) // given

here is what I have:


public static Stack copy(Stack orig)
{
Stack copied = new Stack();

if(orig.size()>0)
{
int x = orig.pop();
copied=copy(orig);
copied.push(x);
}
return copied;
}


although I am thinking that because I am using pop/push I will get in trouble? I have absolutely no idea from this teacher.

[Janus]

One last one:



public static Queue shuffle(Queue q1, Queue q2)
{
Queue newQ = new Queue();
int max = q1.length()+q2.length();
int count = 1;
while(count<=max)
{
if(count%2==1&&!q1.isEmpty())
newQ.enqueue(q1.dequeue());
else if(q1.isEmpty())
{
while(q2.dequeue()!=null)
{
newQ.enqueue(q2.dequeue());
return newQ;
}
}
if(count%2==0&&!q2.isEmpty())
newQ.enqueue(q2.dequeue());
else if(q2.isEmpty())
{
while(q1.dequeue()!=null)
{
newQ.enqueue(q1.dequeue());
return newQ;
}
}
count++;
}
return newQ;
}

[TheMOB]

I think this does the same thing but is a lot simpler...I might be overlooking something though, so make sure my logic works.

public static Queue shuffle(Queue q1, Queue q2)
{
Queue newQ = new Queue();
int max = q1.length()+q2.length();
int count = 1;
while(count<=max)
{
if(q1.length() > 0) {
newQ.enqueue(q1.dequeue());
count++;
}
if (q2.length() > 0) {
newQ.enqueue(q2.dequeue());
count++;
}
}
return newQ;
}

[Janus]

thanks MOB, makes a lot better sense than mine. I also forgot to double increment as well.