• Post Reply Bookmark Topic Watch Topic
  • New Topic

Dynamic Stack  RSS feed

 
Dhananjay Deshmukh
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So i came across this code to implement dynamic stack:

public void push(int item) {
// if stack is full, allocate a larger stack
if(tos==stck.length-1) {
int temp[] = new int[stck.length * 2]; // double size
for(int i=0; i<stck.length; i++) temp[i] = stck[i];
stck = temp;
stck[++tos] = item;
}
else
stck[++tos] = item;
}

If i am correct the for loop actually assigns the contents of stck to temp who's size has just been doubled. However after the for loop every thing before else is going out of my head, particularly "stck = temp. Can somebody explain me what is happening here?
 
Tim Holloway
Bartender
Posts: 18664
71
Android Eclipse IDE Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the JavaRanch, DhananjayDhananjay!

You can make your Java code examples easier to read by using the "Code" button of our message editor. It inserts special tags that preserve formatting.

What you have there is a class member object named "stck". It's an array, and in Java arrays are always immutable in size (they can have null objects at some locations, but that's not the same thing.)

So when an array that can hold 5 element has all 5 slots used, this method will allocate a new array (temp) that's 20 elements long (5*2). Then the object references are copied from the original "stck" to the new stack (temp).

Once that has been done, then the original value (array reference) of "stk" is replaced by the array reference value of "tmp", effectively discarding the original value of "stck" and making it "temp".

Perhaps a little code formatting will help:


Notes:

Note 1: I changed the test from "==" to ">=" because if something was wrong that causes tos to get set to MORE than stck.length - 1, then the code wouldn't bypass the stack expansion if you just used "==". For even more reliability, expansion should be stck.length*2 or tos, whicherver is larger.

Note 2. This statement originally appeared in both the "if" and "else" parths of the stack-full test. I factored it out. Which left me with an empty "else", so I also removed the "else".
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!