DataslopeQueues and Deques
Queue, Deque, ArrayDeque, and PriorityQueue — the FIFO and double-ended structures behind BFS, schedulers, and priority workflows
Lists are about position. Sets are about presence. Maps are about association. The last collection family is about insertion and removal at the ends:
- A queue is a one-ended pipe: things enter at the back, leave at the front. Think of a line at a coffee shop. (FIFO.)
- A deque (pronounced deck) is a queue with two ends: you can add or remove at either side. Think of a deck of cards you can draw from either end.
The interfaces
Queue has two versions of each operation: a "soft" one that returns
null or false on failure (offer, poll, peek), and a "loud"
one that throws on failure (add, remove, element). Prefer
the soft versions — they make queue-emptiness a value, not an
exception.
ArrayDeque: the modern default
ArrayDeque is the default implementation of Deque, and the
default implementation of Queue in modern code. It is a circular
buffer of Object — contiguous memory, no node allocation per
element, very fast.
Front and back are pointers into the array; they wrap around. Both
ends are O(1).
Use ArrayDeque as a queue (FIFO)
When you need a plain queue (line-at-the-coffee-shop semantics),
ArrayDeque is the right choice:
Use ArrayDeque as a stack (LIFO)
You can also use it as a stack — and you should, instead of the
legacy java.util.Stack:
A Deque is a better stack than java.util.Stack for the same
reason ArrayList is a better growing array than Vector: cleaner
API, no inheritance leaks, no unnecessary synchronization.
A canonical algorithm: BFS with a queue
Breadth-first search on a graph is the queue's textbook job. Every node is visited in the order it was discovered — exactly FIFO.
Swap the Queue for an ArrayDeque-as-stack and you have DFS.
PriorityQueue: the heap
PriorityQueue is a Queue whose poll() always returns the
smallest element according to natural order (or a Comparator
you provide). It is backed by a binary heap, so offer and
poll are both O(log n).
Real uses: Dijkstra's algorithm, scheduling, "top-K" selection, event simulation.
PriorityQueue iteration is *not* sorted
for (E x : pq) walks the underlying heap array, which is in heap
order, not sorted order. To get sorted order, drain via repeated
poll().
Choosing the right queue at a glance
| Need | Pick |
|---|---|
| FIFO queue | ArrayDeque |
| LIFO stack | ArrayDeque (via push / pop) |
| Double-ended | ArrayDeque |
| Priority order | PriorityQueue |
| Concurrent FIFO (multiple threads) | ConcurrentLinkedQueue or ArrayBlockingQueue (out of scope here) |
A multi-file example: a tiny task scheduler
A scheduler is essentially a priority queue of tasks ordered by deadline. The "smallest deadline" task runs next.
Comparator.comparingInt(Task::deadline) extracts the deadline and
orders ascending — the smallest deadline comes out first. We will go
deeper on comparators in the next chapter.
Practice
Write a class SlidingWindow<E> backed by an ArrayDeque<E> that:
- Takes
int capacityin its constructor (assumecapacity >= 1). void add(E item): appendsitemat the back; if size exceedscapacity, removes the oldest from the front.List<E> snapshot(): returns the current contents in oldest-to-newest order.
Expected output:
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
Test your understanding
Which is the modern recommended implementation when you want a plain FIFO Queue<E>?
LinkedList
ArrayDeque
PriorityQueue
Vector
What does pq.poll() return on a non-empty PriorityQueue<Integer> built with default ordering?
The most recently inserted element
The first inserted element
The smallest element according to natural order
A random element
What's wrong with iterating a PriorityQueue to get sorted output?
Iteration throws UnsupportedOperationException
Iteration walks the underlying heap array, which is not in sorted order — drain via poll() if you need sorted order
It is O(n²)
It mutates the queue