*
The moose likes Beginning Java and the fly likes Not understanding pop and pushing stacks Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Not understanding pop and pushing stacks" Watch "Not understanding pop and pushing stacks" New topic
Author

Not understanding pop and pushing stacks

Jay Dilla
Ranch Hand

Joined: Aug 12, 2004
Posts: 201
this is a segment of example code i found on the sun java site
I'm not understanding the code for the pop and push



next is the variable given to the array index and is initially equal to 0.
won't next always be less then the length of the array?
and if you call the pop method and the array is not empty you will return the index minus 1?
won't the value on the last index still be there, and you will just return the next to last index value?
Chad Clites
Ranch Hand

Joined: Aug 16, 2005
Posts: 134
stack[next] serves as an index into the array. If next=1, then stack[next] is whatever the value is at index one. When pushing a value onto the stack, the value is added to the array, and the counter is incremented by one, so that it 'points' to the next empty slot. (Drawing pictures helps). When a value is popped from the stack, the counter has to be decremented by one before it can do that, since the push function incremented it past the last value that was inserted.

In reality, yes, the value is still there. An array is a convenient way to demonstrate how a stack works.

So, lets do a push and a pop. Here is a crude stack:
|__|
|__|
|__|<- next=0

The code is saying that if there is room on the stack, add the value to the array at stack[next], or stack[0]. (I'll just use x for the value).
|__|
|__|
|_x|<- next=0

Now next is incremented by one (next++), so the stack looks like this:
|__|
|__|<- next=1
|_X|

Notice that stack[next] is pointing to an empty slot. Now to pop the top value off the stack, we have to first decrement next (--next).
|__|
|__|
|_X|<- next=0

Now we get the value stored at stack[next], which equals x. Does that help?
[ June 19, 2007: Message edited by: Chad Clites ]
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
won't next always be less then the length of the array?

Almost. Say we have array length of 3 ...


and if you call the pop method and the array is not empty you will return the index minus 1?

Yup. Let's just do one this time:


won't the value on the last index still be there, and you will just return the next to last index value?

Yes, again. If we pop again after that last one:

We return the value at arr[1] but we don't touch arr[2]. If that's an object reference the reference may prevent garbage collection that you really wanted to happen, which is A Bad Thing. If it's just primitives then there's no harm done, you can't make the array slot take up less memory so leaving it is fine.

All that fit with what you expected?


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Jay Dilla
Ranch Hand

Joined: Aug 12, 2004
Posts: 201
Wow that's this was really helpful!!!
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Not understanding pop and pushing stacks
 
Similar Threads
Help-Drop out stack
Java Stack program
Picking characters from a string
Stacks
nullpointerexception