Lines 64 to 71 are giving me the heartburn. If I remove those lines everything seems to work fine but when I try to implement the pushLast() method, I start getting null pointer errors.
Your initial concept for pushLast looks good to me.
i.e. - cycle through your stack until you get to the "bottom"
Your next step is where things start to go wrong.
I would suggest drawing some pictures of what should happen to get an idea of the concept of the links here.
But to give you some pointers:
Lets say you have a stack: 5-4-3-2-1
Where 5 is at the top of the stack, and 1 is at the bottom.
If you pushLast(0) what would you expect to get?
Currently your algorithm looks like it would
Move "top" from element '5' all the way down to '1'
Make '1' the next node to '0'
Make '0' the top.
So you would end up with: 0-1
And you have lost the 5-4-3-2 somewhere.
What should be the "next" node for the new element?
Where should top end up pointing?
Hint: You might need another variable in your pushLast() method.
Thank you for the hints. I managed to get it to pass the test cases. I am still really frustrated at myself because I feel like I accomplished the solution more through trial and error and less through understanding. There is no way I could reproduce what I have just done on a whiteboard...smh. I have attached my corrected code for closure.
The code is, actually, in my opinion, a bit awkward. You are using the tmp1 variable to keep a reference to the top node. And then, you are using your top node reference variable as the looping variable to find the last node, and to add to the last node. Wouldn't it have been better to use the tmp1 variable as the looping variable? This way, you can leave your top node variable as the top node variable, instead of temporarily using it as a looping variable?
@ Henry Wong I am sure I implemented it incorrectly( that's my specialty) but when I left "top" alone and user tmp1 to cycle I empty out my list. Again I am sure it is something I have done incorrectly though. If ever just feel too good about myself and need some humbling, I just open NetBeans. It works every time.
Tim Cooke wrote:I might be missing the point here, but by the definition of a stack you can push things on the top of a stack, and pop things from the top of a stack. If you add the ability to add things to the bottom of a stack, you no longer have a stack. You have a regular list.
Actually, I would have said a queue (or Deque).
@R L MIller: A classic stack is generally implemented as a "pointer to <T>" in languages that allow pointer manipulation; however, since Java doesn't, you have to come up with an alternative - and the simplest one is based on a forward-pointing Node that contains data and a reference to the "next" Node (or null).
If you think about it, such an object gives you all you need to implement a stack, since you're only ever worried about which one is "on top" - "popped" Nodes are no longer relevant, since they're no longer part of the Stack, and Nodes further down the Stack aren't "visible" until they become the top one.
For this reason, a stack requires only TWO methods: pop() and push().
Anything else - including peek() - is gravy, and generally unnecessary; although implementing peek() can save a bit of time.
So, my advice: Concentrate on those three methods, and make sure they work before you even think about about implementing any others (even if you've been told to).
Good classes have simple APIs.
Stefan Evans wrote:hint: you need another instance of stack to use as temporary storage
Nice challenge, but that statement isn't strictly true - although it's the one that is usually taught.
@R L MIller: And the reason it isn't is that a stack can be implemented as a "ring" - ie, where the last Node points to the "top" one.
After you've tried Stefan's challenge, you might want to think about how such an implementation might work.
Winston, even with the 'ring' implementation you can't achieve a pushLast() operation using only the standard push(), pop(), and peek() operations. You'd need some internal pointer jiggery.
Edit: You guys must be classmates or something because this is the exact same homework as posted here.
Tim Cooke wrote:Winston, even with the 'ring' implementation you can't achieve a pushLast() operation using only the standard push(), pop(), and peek() operations. You'd need some internal pointer jiggery.
No. Assuming your Node is a single "forward"-linked ring-style one, you simply need to change your "last" Node (which is the only one you need to keep track of for the stack), whenever you execute a pushLast().
If you have an "anchor" Node (my preference), then you have two choices:
1. Copy and change (easiest, but means making the data non-final).
2. Give your anchor Node a rearward pointer. Data-wise, it's a bit "cleaner", but it makes pushLast() a logical exception, and doesn't help with a removeLast() (if needed).
My general preference is #1.
Tim Cooke wrote:Stefan's challenge was: Using that interface, how would you implement a pushLast(E element) method?
OK, well however you do it, your Node needs a constructor that presumably takes a Node to point to, or null if you're creating the first one.
In the case of a ring without an "anchor Node", this makes adding the first Node (at the start or end) an exception, so my implementation would be something like this:Only marginally more involved than storing the "top" Node, and if you have an anchor, you don't even need those 'last == null' and 'last == top()' checks. However, pushLast() then becomes a "logical add".