1

我的任务是创建一个在不使用 Deque 库的情况下添加到 ArrayDeque 的前面（左）的方法。我想出了一个方法，虽然它没有添加到队列中，但它出现了一个空队列。这是我的 addLeft 方法：

public T[] addLeft(T item){
    T[] copyarr = (T[]) new Object[arr.length+1];

    if(isEmpty()){
        copyarr[frontPos] = item;

    }else{
        copyarr[frontPos] = item;
        frontPos--;
        for(int i = 1; i<copyarr.length; i++){
            copyarr[i] = arr[i];
        }
    }
    arr = copyarr;
    return arr;
}

这是iv一直在使用的测试代码：

public class DequeueTest {

public static void main(String[] args) {
    Dequeue test = new Dequeue();
    test.addLeft(3);
    test.addLeft(4);
    System.out.println(test.toString());
}
}

知道我哪里出错了吗？

4

1 回答 1

1

您能否澄清“不使用 Deque 库的 ArrayDeque”？这是否意味着您不想使用 JDK 中的ArrayDeque？

您在数组复制语句中出错了，应该是

copyarr[i] = arr[i-1]

（注意索引是如何移动的）

您的实现在前面添加元素会产生严重的运行时成本，因为您每次都在复制数组。（来自计算机科学课程：ArrayList 在需要时通过将数组大小加倍来获得它们的运行时行为，从而平衡所有附加操作的重新调整大小成本。）

此外，正如评论中已经提到的，请查看 ArrayDeque 实现以获得灵感。也许offerFirst真的正是你所需要的。

根据 Ferrybig 的评论添加：

您可能希望在一个额外的变量中跟踪数组大小，以便存储数组可以大于实际的双端队列。这样，当存储阵列太小时，您可以将其翻倍，从而避免每次都创建副本。不过，您必须移动元素（从较高的索引到较低的索引），最后首先放入新元素。

第二个优化步骤：保存第一个位置，如果您希望前面有多个插入，请保留一些空间，这样您就不必在每次插入时移动元素。（同样，您正在用空间换取运行时的复杂性。）

于 2016-01-26T14:35:30.793 回答