A Queue of deques in Java

Question

I want to have a data structure conformed by a list of deques. So, taking advantage of the FIFO disposition of elements in a queue, I instantiated the following:

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

and also,

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

However when I add each deque and print myQueueOfDeques, it appears with the correct size of empty fields, e.g. when it is supposed to store three deques it shows [ [], [], [] ]. Here is the portion of the code.

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);

Clearly the problem is that I keep thinking it as the way data structures work in c++, however I know this is java and I'm having a hard time. I already read the documentation for different structures found here

Java objects are references. You're adding a reference to `pathQueue` to `myQueueOfDeques`, then clearing it. Allocate a new `pathQueue` at the beginning of each iteration. — Colonel Thirty Two, Jan 14 '16 at 15:54
But I need to remove all the elements of `pathQueue` each time the deepest bucle finishes. — Nana89, Jan 14 '16 at 15:56
No, you don't. `pathQueue` is a _reference_ to an object. `myQueueOfDeques.add(pathQueue);` adds a reference to the object pointed to by `pathQueue` to the list pointed to by `myQueueOfDeques`. If you clear the object pointed to by `pathQueue`, it also clears the object that you just added to `myQueueOfDeques`, because they're the _same thing_. — Colonel Thirty Two, Jan 14 '16 at 16:00
Think of what would happen in C++ if `pathQueue` was a pointer and you had a list of pointers. Speaking of which, you should probably use another `ArrayDeque` as a queue because it also implements that interface and usually faster than `LinkedList`. — Sergei Tachenov, Jan 14 '16 at 16:01

Sergei Tachenov · Accepted Answer · 2016-01-14T18:17:49.950

You need to understand one important thing: in Java, everything is a reference and references behave somewhat like pointers in C++. So when you add a deque to the queue, you don't add a copy, but rather the very queue you've just filled up. This is, of course, very good performance-wise, but you end up with pathQueue being not just identical to what you have in your min queue, but the very same queue. Then you clear it and of course it's now empty. How to deal with that? Obviously by creating a new queue each time. Allocation is pretty cheap in Java, unlike C++, so you should really prefer it to reusing the same object over and over in most cases.

Given that, your code should probably look like this:

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);

And as I've mentioned, you should probably use ArrayDeque as a queue. It's usually more efficient in both time and memory than a LinkedList. In fact, I believe that about the only time when you really want to use a LinkedList is when you want fast insertions and removals in the middle. Otherwise, ArrayDeque is usually better both for queues and stacks (there is a class called Stack but it's considered obsolete, so when looking for stacks, look for anything that implements the Deque interface).

So you should really change your main queue declaration to this:

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

A Queue of deques in Java

1 Answers1