ArrayDeque vs ArrayList 来实现堆栈

stack java arraylist arraydeque

2022-09-01 06:08:38

的文档说：ArrayDeque

当用作堆栈时，此类可能比 Stack 快，在用作队列时，它可能比 LinkedList 快。

没有提到将用作堆栈和使用 .您可以按如下方式将用作堆栈。ArrayDequeArrayListArrayList

list.add(object);                      // push
object = list.remove(list.size() - 1); // pop

我发现，当我只以这种方式使用时，它的性能比.造成这种差异的原因是什么？当然，它不能只是对的调用？在内部，两者都使用在需要时被更大的阵列替换来实现，因此性能肯定应该大致相同吗？ArrayListArrayDequesize()ArrayListArrayDequeObject[]

答案 1

两种实现之间的主要区别在于调整大小策略

ArrayList调整大小为的新大小，从而产生 ~50% 的英寸。默认容量为 10，导致调整大小为 15、22、33、49、73、109、163、244、366...oldCapacity + (oldCapacity >> 1)
ArrayDeque始终调整大小为 2 的幂。调整大小时，容量将加倍。从默认值 16 开始，调整大小后的恢复容量为 32、64、128、256,...

因此，ArrayDeque 以更少的调整大小操作实现了更高的容量，而调整大小操作由于阵列拷贝而成本高昂。即，要将256存储在默认大小的ArrayList中，它需要9次调整大小的调用，而ArrayDeque只需要4次。数组复制可能很快，但除了内存复制成本之外，还可能需要一个 GC 来为新数据集释放一些空间（ArrayDeque 也可能由于它与 2 的幂对齐而性能更好）。

两种数据结构都具有 O（1）的最佳复杂度，用于推送和弹出直接访问任何一个 &（ArrayDequeue）分别添加和删除（Last）（ArrayList）headtailsize

答案 2

为了回答这个问题，让我们比较 ArrayList 和 ArrayDeque 类的 remove 方法。

数组列表删除方法

public E remove(int index) {
    this.rangeCheck(index);
    ++this.modCount;
    E oldValue = this.elementData(index);
    int numMoved = this.size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(this.elementData, index + 1, this.elementData, index, numMoved);
    }

    this.elementData[--this.size] = null;
    return oldValue;
}

ArrayDeque removelast方法

 public E removeLast() {
    E x = this.pollLast();
    if (x == null) {
        throw new NoSuchElementException();
    } else {
        return x;
    }
}

ArrayDeque removeLast 方法调用 pollLast 方法

    public E pollLast() {
    int t = this.tail - 1 & this.elements.length - 1;
    E result = this.elements[t];
    if (result == null) {
        return null;
    } else {
        this.elements[t] = null;
        this.tail = t;
        return result;
    }
}

让我们逐步解释ArrayList删除方法：

检查输入的索引是否在数组的限制范围内
将 ModCount 变量递增 1。
存储要删除的值。
确定要移动的数字数（在我们的示例中，找到numMoved 0，因为最后一个元素将被删除）。
如果要移动的数字大于 0，则复制数组（将不执行复制，因为找到 numMoved 0）。
将 null 分配给数组的最后一个元素。
返回已删除的值。

让我们逐步解释 ArrayDeque removeLast 方法（这足以解释 pollLast 方法）：

查找数组的最后一个索引
返回数组中最后一个元素的值。
如果最后一个元素的值等于 null，则返回 null。
如果最后一个元素的值不为空（如果它不是空，则将执行以下步骤）。
将 null 赋给最后一个元素
更新 tail 变量的值
返回结果

当我们比较这些步骤时，在性能方面没有明显的差异。在我们的示例中，方法将不起作用，因为我们删除了最后一个元素。如果此方法有效，则会出现性能差异。总之，除了@Gerald Mücke的答案之外，没有什么区别可以考虑的。如果要删除的元素是列表的第一个元素，则会出现性能差异。当我们想要删除第一个元素时，我们可以使用类的方法（该方法的工作方式与方法类似）。当我们想要删除ArrayList中的第一个元素时，我们可以使用该方法。当我们删除索引为 0 的 ArrayList 时，这次将完成数组 copy（）。我们曾经说过，由于数组复制过程，它的速度会变慢。ArrayList's System.copyarray removeFirstArrayDequeremoveFirstremoveLastremove(0)System.copyarrayArrayList