数据结构Java中的数据队列

Question

我想要一个数据结构，由一系列的数据组成。因此，利用队列中元素的FIFO配置，我实例化了以下内容：

Deque<String> pathQueue = new ArrayDeque<>();

而且

Queue<Deque<String>> myQueueOfDeques = new LinkedList<Deque<String>>();

但是，当我添加每个deque并打印myQueueOfDeques时，它会以正确大小的空字段出现，例如，当它应该存储三个deque时，它会显示[ [], [], [] ]。下面是代码的一部分

for (Element leaf; (leaf = (Element)walker.nextNode()) != null; ) {
            for (Node node = leaf; node.getNodeType() == Node.ELEMENT_NODE; node = node.getParentNode())
            {
                pathQueue.addFirst(((Element)node).getAttribute("id"));
            }
            myQueueOfDeques.add(pathQueue);
            pathQueue.clear();
        }
 System.out.println(myQueueOfDeques);

显然，问题是我一直认为它是数据结构在C++中工作的方式，但是我知道这是java，而且我的日子很难过。我已经阅读了这里不同结构的文档

Answer 1

你需要理解一个重要的事情：在java中，所有的东西都是引用，引用的行为和C++中的指针有点类似。因此，当您向队列中添加一个deque时，您不会添加副本，而是添加刚刚填充的队列。当然，这在性能方面是非常好的，但最终pathQueue不仅与min队列中的相同，而且是非常相同的队列<然后你把它清理干净，当然它现在是空的。如何应对？显然，每次都要创建一个新队列。与C++相比，在java中分配很便宜，所以在大多数情况下，您应该更喜欢重复使用同一个对象。p>

鉴于此，您的代码应该如下所示：

for (Element leaf; (leaf = (Element)walker.nextNode()) != null; ) {
    Deque<String> pathQueue = new ArrayDeque<>();
    for (Node node = leaf; node.getNodeType() == Node.ELEMENT_NODE; node = node.getParentNode())
    {
        pathQueue.addFirst(((Element)node).getAttribute("id"));
    }
    myQueueOfDeques.add(pathQueue);
}
System.out.println(myQueueOfDeques);

正如我所提到的，您可能应该使用ArrayDeque作为队列。它通常在时间和记忆上都比LinkedList更有效。事实上，我认为只有在你真正想要使用^ {< CD3}}的时候，才需要在中间进行快速插入和删除。否则，ArrayDeque通常对队列和堆栈都更好（有一个名为Stack的类，但它被认为是过时的，所以在查找堆栈时，请查找实现Deque接口的任何东西）

因此，您应该将主队列声明更改为：

Queue<Deque<String>> myQueueOfDeques = new ArrayDeque<Deque<String>>();