We just started discussing stacks and queues in my class, and our teacher left us with some questions to answer. I got all of it done except for the last question, which I honestly just can't understand, and am wondering if there is something about stacks that I'm missing. Here is the question:

"Suppose you have aStack and Bstack. Assuming each stack starts empty, write the code that would write out the number of elements on aStack ultimately leaving aStack unchanged (without using a method involving a size variable)"

I don't really understand it because first and foremost, if I'm assuming the stack is empty, how can I write out the number of elements (unless I'm supposed to just write out the code regardless of what's actually inside the stack, at which point I'm not sure why it says the stacks are empty). Also, why would "bStack" be brought in? It doesn't seem like I'd need to utilize two stacks for this question.

Any help would be GREATLY appreciated!

I am not entirely I understand the question either, but my guess is that your task is to write a function that can determine the length of stack a without actually using it. I think that you could make a copy of stack a as elements are added to it in stack b, then just write something to determine the size of stack b.

A pure (or minimal) stack implementation would just provide a few functions: usually just one to push a new element to the top of the stack, one to read the top element of the stack, one to pop the top element off the stack, and a function to tell if the stack is empty.

I also think that the question is a bit weirdly formulated but my guess is that what is asked is for an algorithm that can print all the elements of a stack (Astack) while leaving it unchanged. Now, the problem is that since you can only read the top value on the stack, you can't really "traverse" it without popping elements off the stack until it's empty. So, the problem is this: how can you manage to repopulate the stack with all the same elements it had before? That's where the Bstack comes into play.

Just imagine that you had a pile (or little tower or stack) of blocks (like those blocks with letters on them like you used to play with as an infant) and you could only see the block that is on top. If you wanted to know all the blocks that are in the pile but you wanted to restore the pile to how it was before. If you just carelessly take all the blocks off, you would have no idea in which order to put them back, so that's not an option. If you carefully take notes to mark down which block appeared in what order on the pile as you remove them one by one, then you could reconstruct the original stack by putting them back in reverse order that you took them off the pile, but that solution is pretty tedious and requires a lot of book-keeping. Another solution, that is much simpler, is to make another pile with all the blocks as you are taking them off the original pile, making that new pile store all the blocks in reverse order, and then, transfer them all back to the original pile, and that's it. That's basically what you need to do with your Astack as the original stack and the Bstack as the temporary stack that you transfer the elements to and from.

If you want to know the size, you just count the number of blocks you took off the original stack on the first transfer, or you count number of blocks you put back on the original stack on the second transfer. If you want to print the elements in order from top element to bottom element, then you print the values out as you are taking them off the original stack. And if you want to print the elements from bottom to top, then you print the values during the second transfer (from Bstack back to Astack). That's it. I'm pretty sure that's the algorithm your prof was alluding in his question.

This article has been dead for over six months. Start a new discussion instead.