File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Not understanding pop and pushing stacks

 
Jay Dilla
Ranch Hand
Posts: 201
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 134
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 8791
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Jay Dilla
Ranch Hand
Posts: 201
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wow that's this was really helpful!!!
 
I agree. Here's the link: http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic