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?
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. (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 ]
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 but we don't touch arr. 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