标签: arraydeque

我试图理解为什么Java的ArrayDeque优于Java的LinkedList,因为它们都实现了Deque接口.

我几乎没有看到有人在他们的代码中使用ArrayDeque.如果有人对ArrayDeque的实现方式有了更多了解,那将会很有帮助.

如果我明白了,我会更有信心使用它.我无法清楚地了解JDK实现它管理头尾引用的方式.

文档ArrayDeque说:

当用作堆栈时,此类可能比Stack快,并且当用作队列时比LinkedList更快.

没有提到使用ArrayDeque堆栈和使用堆栈之间的区别ArrayList.您可以使用ArrayList如下堆栈作为堆栈.

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

我发现当我只用ArrayList这种方式时,它的性能比它差ArrayDeque.这种差异的原因是什么？当然,它不仅仅是电话size()？在内部,都ArrayList和ArrayDeque使用的是实现Object[]由更大的阵列需要时更换,所以可靠地性能应该是大约相同的？

已经尝试过一个示例程序来理解Java 6 之间的区别addFirst和offerFirst方法ArrayDeque.但是它们看起来是一样的,有什么建议吗？

public void interfaceDequetest()
{
        try{
        ArrayDeque<String> ad = new ArrayDeque<String>();
        ad.addFirst("a1");
        ad.offerFirst("o1");
        ad.addFirst("a2");
        ad.offerFirst("02");
        ad.addFirst("a3");

        System.out.println("in finally block");

        for (String number : ad){
            System.out.println("Number = " + number);
        }
}

根据javadoc,

当用作堆栈时,ArrayDeque类可能比Stack快

我不明白ArrayDeque怎么能比堆栈更快.假设使用链表实现堆栈,如下所示:

Push: Insert new element at the head, teamp->next = head; head = temp 
(where temp is the element to be inserted)
Pop: Remove the element from head, and make head = head->next

对于大量元素,ArrayDeque将有一个调整大小的开销,这在使用LinkedList实现的Stack中不是这种情况.那么ArrayDeque究竟比堆栈更快呢？

在Java中（但在PHP中类似），ArrayDeque实现的能力始终为2的幂：

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/ArrayDeque.java#l126

对于HashMap这种选择很明显-基于修剪的32位哈希具有均匀的元素分布。但是Deque顺序插入/删除元素。

同样，ArrayList不将其容量限制为2的幂，只是确保其至少为元素数量。

那么，为什么Deque实现要求其容量为2的幂？

为什么通常不ArrayList实施双端,这将支持前面和后面的快速摊销？

使用后者而不是前者有不利之处吗？

(我不只是谈论Java - 我没有看到双端数组列表是任何其他语言的默认值,但Java只是一个很好的例子.)

*编辑:我最初称它们为"阵列deques",但这对我来说是一种误解; 我不是在谈论队列,而是双端阵列表.

想知道为什么我的内存访问速度比我预期的慢一些,我终于想通了Visual C++实现deque确实有一个内置的额外间接层,破坏了我的内存局部性.

即它似乎持有一个数组T*,而不是一个数组T.

是否有另一个我可以使用VC++但没有这个"功能"的实现,或者是否有某种方式(虽然我认为不太可能)在这个实现中能够避免它？

我基本上都在寻找一个vector在前面也有O(1)推/弹的东西.
我想我可以自己实现它,但处理allocators等是一种痛苦,需要一段时间才能正确,所以我宁愿使用以前编写/测试的东西,如果可能的话.

我arraydeque用来创建项目列表并传递参数(项目是类)

ArrayDeque<Item> Items= new ArrayDeque<Item>();

但我有java ArrayDeque的问题.也许有办法一次添加多个元素.例如.我想补充的同时TableType,并colourOfTable为ArrayDeque.

在c ++中我可以用它完成它

vector<Item>Items

Items.push_back(Item("CoffeeTable", "brown"));

我想用Java做同样的事情.而不是为每个项目创建一个新的obj,如:

ArrayDeque<Item> Items = new ArrayDeque<Item>();

Item obj = new Item("CoffeTable", "brown"); 
Items.add(obj);

Item obj1 = new Item("DinnerTable", "Black"); 
Items.add(obj1);

但obj我并没有想要同时添加 "CoffeTable", "brown"一个代码行(如c ++示例中)到Items数组中.

我尝试过类似的东西

ArrayDeque<Item> Items= new ArrayDeque<Item>();

Items.add(Items("CoffeTable", "brown")); 

但是在创建create方法'Items(String,String)'时出现错误

java.util.ArrayDeque类中的addFirst方法的代码是

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

在这里,我无法理解其含义

head = (head - 1) & (elements.length - 1)

另外,假设数组大小为10. head为0且tail为9(数组已满).在这种情况下,什么索引系统会插入？(我的理解是:如果数组已满,则首先增加其大小,然后在arraySize() - 1索引中插入.)

我通过java源代码看看尝试学习集合的实现.在ArrayDeque类中发现了一件有趣的事情.

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    elements[t] = null;
    tail = t; …