Declaring a shrink function in Dynamic Array in Stack

Question

Here is my code:

private void shrink(){ 
int length = top+1; 
    if(length<=MINCAPACITY || top<<2 >= length)  
        return;
        length = length + (top<<1); 
        if(top < MINCAPACITY) length = MINCAPACITY;
        int[] newstack = new int[length];
        System.arraycopy(stackRep, 0 , newstack, 0 , top+1);
        stackRep = newstack;
    }

In my book it is said that this operation shrinks the array to half if more than 3/4th empty. Can anyone please explain to me how is this taking place in this code? I suspect that this operation is taking place in the first if-statement and the length statement?

Well which *exact* part of the code do you not understand? – Jon Skeet Oct 04 '15 at 08:30 — Jon Skeet, Oct 04 '15 at 08:30

score 1 · Answer 1 · edited May 23 '17 at 10:26

Java arrays can't change length. What this does, is calculates the new length, creates a new array of that length, and copies the stuff into it from the old array, then makes the old array reference the new array.

int length = ... // this will be the new arrays length
int[] newstack = new int[length]; // this is the new array
System.arraycopy(stackRep, 0 , newstack, 0 , top + 1); // stuff is copied to the new array
stackRep = newstack; // old array is now the new array

Not sure if this answers your question

Edit:

By the "part that changes the length" I assume, that you want to know, what these do: << and >>. They are bitshift operators, you can find a more detailed description about them for example here.

Basically they do this:

x << n - multiplies x by 2 to the power of n
x >> n - dividesx by 2 to the power of n

So 10 << 1 is 20. 10 << 3 is 80. 10 >> 1 is 5. 10 >> 2 is 2 (precision lost here, since these operators simply shifting bits).

Umm still no. I need to know how this code is reducing the array size to half. — Uddipta_Deuri, Oct 05 '15 at 07:47

score 0 · Answer 2 · answered Sep 17 '18 at 12:26

i traced above logic, it is not shrinking the array to half if more than 3/4th is empty.

I think you are following data structures and algorithms made easy in java by narasimha karumanchi. you have shared same code snippet here.

i made few changes to the code. Please find the following code. It will shrinks the array to half if more than 3/4th empty.

private void shrink(){ 
    int length = top+1; 
        if(length<=MIN_CAPACITY || top<<2 >= stackRep.length){
             return;
        }
        length =  (length<<1); 
        if(top < MIN_CAPACITY) length = MIN_CAPACITY;
        int[] newstack = new int[length];
        System.arraycopy(stackRep, 0 , newstack, 0 , top+1);
        stackRep = newstack;
}

assume there are 16 elements in stack and size of array is also 16. one more element is added, since array is full new array with double the size 32 is created and old array contents will be copied to new array and 17th element entry will be made into new array. let us trace by popping elements. assume MIN_CAPACITY=2

no of elements in stack 17, array size 32, top = 16

after popping if there are only 1/4th size of the array elements left in the stack then

no of elements in stack 8, array size 32, top = 7

top << 2 is nothing but top * 2 * 2 so (top<<2 >= stackRep.length) will become (28 > 32), which is false. now we should create array with half the size.

length = (length<<1); will create array with half the size.

rest of the things are self explanatory.

Declaring a shrink function in Dynamic Array in Stack

2 Answers2