Using a stack as a Queue in Java

Question

I need to process a tree in different orders, let's say BFS and DFS. Both is easy by using a queue or a stack, however, I'm missing a proper interface in Java allowing to do something like

QueueOrStack<N> pending = ... while (!pending.isEmpty()) { N node = pending.poll(); // <----- this is the problem pending.addAll(node.children()); process(node); }

There's no real problem, I can encapsulate an ArrayList into something implementing Queue¹, however I'd bet I'm overlooking something in the Java Collection Framework. Or is it really missing?

__

¹ or use a newest-first comparator with a PriorityQueue, which is probably a dumb idea

Alexander Pogrebnyak · Accepted Answer · 2012-11-01 20:35:33Z

5

There is such a structure.

It is called ArrayDeque -> http://docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html

answered Nov 1, 2012 at 20:35

Alexander Pogrebnyak

45.8k10 gold badges111 silver badges123 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Jesse Webb Over a year ago

+1 - I've never used the class, but I glanced at the doc and it looks exactly like what is needed for this case. It is also worth pointing out that the doc states "This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue." which is nice!

Luiggi Mendoza Over a year ago

Indeed, the structure is Deque and the ArrayDeque is an implementation.

maaartinus Over a year ago

@Alexander Pogrebnyak: I see it has all the needed operations, but I still need to do something like N node = asStack ? pending.pollLast() : pending.pollFirst(). But this is not bad.

durron597 Over a year ago

@maaartinus: Make your own class with an ArrayDeque as a field, and a boolean asStack. Then expose the methods you want (i.e. public E poll() { asStack ? pending.pollLast() : pending.pollFirst() }). You can make it implement the Stack<E> and Queue<E> interfaces if you like.

Stefan Over a year ago

@maaartinus LinkedList also implements Deque and atleast in this case it performs better than an array based one.

Collectives™ on Stack Overflow

Using a stack as a Queue in Java

1 Answer 1

5 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Linked

Related