Question

数据结构：关于Java实现的一个队列，对其中的扩容步骤有疑问？答题的都是我爹

队列的源码如上，经过一些出队入队和循环队列后操作后，该未扩容过的队列已经变成了如下形式

现在数组已经满了，所以要开始扩容了，但是按照本示例代码的操作方式，扩容后队列就成下面这个奇葩样子了

源码中为什么要在扩容后将front归零呢？这样不是把队列中的顺序打乱了么？

解决我问题的大哥都是我爹，请收下我这个儿子！实在想不明白这问题





Answer 1

这确实有点奇葩，要么修改resize方法，在进行复制的时候，先判断一下front和rear的值，如果front不为0，说明进行过出队列操作，再判断rear与front的值：

if(front < rear ){ //copy from front to rear 这样就可以去除多余的空位置，让front从0开始}
if(front > rear ){ 
//先复制后半段到新的数组，然后复制前半段到新数组的后面，这就保证0位置的就是队列的头  
}

这样的话，就可以理解为什么resize之后将front置为0,。

 

不知道这样的解释对不对，我看完上面的代码觉得就是这样的。

Answer 2

确实是乱了，他的resize()方法实现的有问题，不能简单的使用System.arraycopy()
但front和rear肯定得改，否则计算对了长度会出现问题。

另外按照你的代码是不会出错的，因为没做任何其他操作，front一直是0

追问

给我说懵了 到底是对还是不对呢=。=悲剧啊

追答

若队列在插入若干元素后进行了出队（删除）操作，那么会出现rear在front之前的情形，此时调用resize，队列次序是被打乱了。
但你的主程序中就是一个个插入，在这种情况下，他的resize没有碰到上述情形，不会出错了。
要保证代码无bug，resize方法中拷贝那行需要重写，若出现rear在front之前，需要分段拷贝两次。

追问

爹 你觉得该咋重写

追答

分两种情况来写
public void resize()
{
T[] tmp=(T[])new Object[2*data.length()]

if(front<rear)
{ //直接拷贝data[front..rear]到tmp[0..rear-front]
System.arrayCopy(data,front,tmp,0,rear-front+1);

}
else
{ //先拷贝后半截data[front..data.length()-1]到tmp[0..data.length()-1-front]
System.arrayCopy(data,front,tmp,0,data.length()-front);
//再拷贝前半截data[0..front-1]到tmp[data.length()-front..data.length()-1]

//注意rear=front-1

System.arrayCopy(data,0,tmp,data.length()-front, front);

}
data=tmp;
tmp=null;
}

追问

爹 儿在问一句
一般的队列实现是不是都是“循环队列”+“数组扩容”来实现的呢？
这个也不例外吧？‘
作者也是想按一般思路写，只不过他写错了对吗？=。=

而且这样之后是不是需要对rear重新赋值呀

追答

(1)一般的队列实现都是“循环队列”是防止删除数据时需要每个剩下的数据均要往前移动
(2)数组扩容是针对现有应用数学量不定，有时过大有时小，为了节省空间设定的。但老开辟空间扩容也比较费事。具体应用得在两者之间找一个平衡，
(3)队列不一定需要使用数组来做，可直接使用vector，他是扩容，但内存不需要代码管理。

追问

爹你注意到没有，排列之后front = 0;归零，这个我可以理解，但是rear是不是也得归成data.length-1，您觉得这一步骤有必要吗

追答

他在add函数中已处理
就是这就话rear=（front+size）%data.length

Answer 3

儿子，从小我就教育你认真听课，独立思考。你却跑这认爹，太让我失望了，下面是答案，下不为例。
==========无耻的分割线============
是因为System.arraycopy写错了吧。

应该是这样：System.arraycopy(data, front, tmp, 0, data.length);
data中的front代表队列头，front之前的是已经remove的，所以要从front开始拷贝数组。

另外resize里tmp=null完全没必要，tmp所指向的对象与data相同，tmp=null后data仍然引用，不会触发GC。

追问

不对啊
原数组是1、2、3、4、5
1、2出列变成了null、null、3、4、5
然后6、7入列后变成6、7、3、4、5
你这么复制的话3、4、5是有了，6、7没了啊

有空余空间会先利用循环队列机制，循环队列也用满了的话才会进行扩展数组=。=爹 你说的不对吧

追答

哦，循环队列。小看你了，儿。i'm proud of u.

你觉得这样如何呢？

public void resize() {
T[] TMP = (T[]) new Object[data.length*2];
System.arraycopy(data, front, tmp, 0, data.length - front);
System.arraycopy(data, 0, tmp, data.length - front, front);
data = tmp;
}

追问

嗯
您老人家也有看走眼的时候啊
您这个就是分开求了呗？
之前rear在front前面，现在就是先front遍历到新数组，再把rear以后的遍历到新数组？