Struggling with copying stack objects in homework for I6

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
HavocVulture
Posts: 16
Joined: October 30th, 2017, 11:50 pm

Struggling with copying stack objects in homework for I6

Post by HavocVulture » October 31st, 2017, 12:04 am

I'm having trouble with the homework for Intermediate 6, where you create a stack.

I can pass all the tests but have memory leaks, or I get an error after test 5 if I try to delete popped stack items.

I think it has to do with copying stacks. The problem is you can only traverse the stack by popping items off of it and that's no good. I don't want to destroy the stack I'm copying. I was thinking maybe a recursive solution might let you traverse the stack until you hit a nullptr but I can't prevent it from recursing into infinity.

I've attached my stack class files. Any pointers *cough* would be helpful.
Attachments
Stack.cpp
(844 Bytes) Downloaded 128 times
Stack.h
(519 Bytes) Downloaded 119 times

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Struggling with copying stack objects in homework for I6

Post by albinopapa » October 31st, 2017, 2:20 am

What I did is use recursion until you reach a nullptr. Then you've reached it, start pushing the current element to the new stack.

Something like this:

Code: Select all

Stack::ListItem* Stack::Copier( const ListItem*const lstItem )
{
	if( lstItem->prev != nullptr )
	{
		Copier( lstItem->prev );
	}

	Push( lstItem->val );
}
This SHOULD walk the lstItem's prev pointers until one is null, then it skips the recursive check and pushes the new value to the current stack. When that is done, it moves up a level and pushes it on to the stack and so on until you've reached the end of the list.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Struggling with copying stack objects in homework for I6

Post by chili » October 31st, 2017, 3:16 am

Yup, I've done it with recursion in the solution video, because it is simple and I like recursion.

It can also be done with a loop, and a loop is actually the objectively correct approach (though not as sexy imo). :D
Chili

HavocVulture
Posts: 16
Joined: October 30th, 2017, 11:50 pm

Re: Struggling with copying stack objects in homework for I6

Post by HavocVulture » October 31st, 2017, 4:34 am

Thanks for your help albinopapa.

It seems to pass now, no memory leaks. I feel kinda shit about it though, like I fumbled my way into the solution (with your help of course). After getting Copier working, I still had memory leaks. I set my Stack destructor to keep running Pop() until Empty(). Strangely, even though size > 0 my listItem pointer would be null. This caused an exception to be thrown.

So I updated my if statement in Pop() to check if size > 0 and li != nullptr. This made everything work and while I understand why in the naive sense, I don't understand how my size > 0 when I reached the end of the stack.

My dev skills are more Cheetahmen than Castlevania.

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Struggling with copying stack objects in homework for I6

Post by albinopapa » October 31st, 2017, 7:50 am

You'll get there.

The best learning tool often times is the debugging process. Step through line by line if you have to in order to see what logic errors you might have made. Think of a condition where the error occurs and make an if statement that says if this condition occurs, and then set a break point inside the if statement so you can see what the state of your variables are just before the error is thrown. Use the stack window to go back a few function calls if you don't notice anything wrong in the function you're in.

Other than that, start writing little programs that make you think about what you learned from the tutorials. I have a project that I call testbed and anytime I want to test something, I just write it up in there and see what happens. When I get the results I want, I can go implement it in the main project.

You'll get there, just don't try rushing anything, you'll just get frustrated and it will take longer because you won't be as receptive. That's what happened to me.
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

Post Reply