Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Adding to bottom of linked Stack  RSS feed

 
R L Miller
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
     I have to add a method to be able to push and object to the bottom of a linked stack. I have made a few attempts but have not been successful. Quite frankly, I don't think I understand linked lists in this application from a conceptual level. I am able to push to the top of the stack but can't seem to push to the bottom. I attempt to cycle through the objects until I reach a null and then attempt to add my element there. It adds the element but either it is still pushing it to the top of the stack or I am inadvertently making the bottom of the stack the top of the stack. I apologize for my rambling, this is effectively my 5th week of knowing Java as more than a cup of coffee and I don't know enough to even ask intelligent questions. I have attached my code for review. 

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.




           
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey RL Miller, I'm doing something similar with my LinkedList assignment. Have you tried creating sentinel nodes in your stack, and then had the last node point to the tail node of the stack? That possibly could work.
 
Stefan Evans
Bartender
Posts: 1836
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there.
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.
 
R L Miller
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Stefan Evans  
     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.


 
Tim Cooke
Marshal
Posts: 3872
233
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Henry Wong
author
Sheriff
Posts: 23283
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
R L Miller
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@ Tim Cooke  This was an assignment for a College course. You are probably correct.

@ 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.
 
Campbell Ritchie
Marshal
Posts: 55751
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
R L Miller wrote:. . . This was an assignment for a College course. You are probably correct. . . .
where else would somebody think that it is normal to add something to the bottom of a stack?
 
Stefan Evans
Bartender
Posts: 1836
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A challenge for you: 

Implement the pushLast() method using ONLY the standard methods of a stack. 
i.e. using push() pop() and peek() only. 
No fiddling around with the internal pointers.

hint: you need another instance of stack to use as temporary storage


 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Have fun.

Winston
 
Jonothon Turner
Greenhorn
Posts: 20
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am doing a linked stack assignment and I am having issues with the toString() method may I ask how you completed yours
 
Tim Cooke
Marshal
Posts: 3872
233
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Jonathan, what issues are you having with your toString()?

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.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Winston
 
Tim Cooke
Marshal
Posts: 3872
233
Clojure IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That sounds like internal jiggery to me. You are manipulating the internal data structure by means that cannot be achieved through the interface

Stefan's challenge was: Using that interface, how would you implement a pushLast(E element) method?
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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".

Winston
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!