在Stack中声明Dynamic Array中的收缩功能

Question

这是我的代码：

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;
    }

在我的书中，据说如果超过3/4空，此操作会将数组缩小一半。任何人都可以向我解释这个代码是如何发生的？我怀疑这个操作发生在第一个if语句和长度语句中？

Answer 1

Java数组不能改变长度。这样做，是计算新长度，创建一个新长度的数组，并从旧数组中复制内容，然后使旧数组引用新数组。

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

不确定这是否回答了你的问题

编辑：

通过“改变长度的部分”我假设，你想知道，这些做什么：<<和>>。它们是bithift操作符，您可以找到有关它们的更详细描述，例如here。

基本上他们这样做：

• x << n - x将2乘以n的力量
• x >> n - 由x划分2到n的力量

所以10 << 1是20。 10 << 3是80。 10 >> 1是5。 10 >> 2是2（这里精度丢失，因为这些运算符只是移位）。

Answer 2

我追踪逻辑，如果超过3/4为空，它不会将数组缩小到一半。

我认为你正在遵循narasimha karumanchi在java中轻松实现的数据结构和算法。您在此处共享了相同的代码段。

我对代码做了一些修改。请找到以下代码。如果超过3/4空，它会将数组缩小一半。

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;
}

假设堆栈中有16个元素，数组的大小也是16.添加了一个元素，因为数组是全新的数组，大小为32，并且旧的数组内容将被复制到新数组，第17个元素条目将被复制制成新阵列。让我们通过弹出元素来追踪。假设MIN_CAPACITY = 2

堆栈17中没有元素，数组大小为32，顶部= 16

弹出后如果堆栈中只剩下1/4大小的数组元素那么

堆栈8中没有元素，数组大小为32，顶部= 7

top << 2只是top * 2 * 2所以（top << 2> = stackRep.length）将变为（28> 32），这是假的。现在我们应该创建一半大小的数组。

length =（长度<< 1）;将创建一半大小的数组。

其余的东西都是自我解释的。