Kolejka priorytetowa wyjmuje element o najwyższym (lub najniższym) priorytecie, a nie najstarszy. Zwykle jest zaimplementowana kopcem, więc wstawienie/usunięcie to O(log n).
import java.util.PriorityQueue;
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
System.out.println(pq.poll()); // 1