Nghĩ về tấm bảng phân loại bệnh nhân ở phòng cấp cứu. Y tá luôn gọi người nặng nhất vào trước — cái đó chắc chắn. Nhưng bản thân tấm bảng thì không phải một danh sách xếp răm rắp từ nặng xuống nhẹ; nó chỉ cần giữ được đúng một điều: người nặng nhất luôn ở trên cùng. Nhìn vào giữa bảng mà kết luận "thứ tự lộn xộn, hệ thống hỏng rồi" là hiểu nhầm cách nó hoạt động. PriorityQueue của Java chính là tấm bảng đó, và cái nhầm ấy là một trong hai cú bẫy của bài hôm nay.

Hai lỗi trong bài này đều có chung một đặc điểm: mã chạy đúng, nhưng khi bạn in ra để kiểm tra thì thấy thứ khiến bạn nghi ngờ mọi thứ.

Bắt đầu bằng lớp mà tôi nghĩ nên bị gỡ khỏi mọi dự án.

Stack duyệt từ dưới đáy lên

Stack<String> st = new Stack<>();
st.push("A"); st.push("B"); st.push("C");

  pop() trả về : C (đúng, C vào sau cùng)
  nhưng duyệt ra : [A, B, C]   <- từ ĐÁY lên!
  st.get(0)      : A (phần tử dưới đáy)

Ngăn xếp là "vào sau ra trước". pop() trả C — đúng. Nhưng in ra thì lại thấy [A, B, C], và get(0) cho phần tử dưới đáy.

Nguyên nhân: Stack kế thừa Vector, tức là một danh sách. Nó push bằng cách thêm vào cuối danh sách, nên khi duyệt theo thứ tự danh sách thì bạn đi từ đáy lên đỉnh — ngược hoàn toàn với ý nghĩa của ngăn xếp.

Đây chính là ví dụ vi phạm Liskov ở bài SOLID: Stack là một Vector theo cú pháp, nhưng ngữ nghĩa thì mâu thuẫn.

Cùng việc đó với ArrayDeque:

  peek()   : C
  duyệt ra : [C, B, A]   <- từ ĐỈNH xuống

Đúng chiều. Cộng thêm: ArrayDeque không đồng bộ hoá nên nhanh hơn Stack (vốn đồng bộ trên mọi phương thức mà vẫn không an toàn cho thao tác ghép đôi).

Đừng dùng Stack, Vector, Hashtable. Cả ba là di sản từ Java 1.0, giữ lại chỉ vì tương thích ngược. Thay bằng ArrayDeque, ArrayList, HashMap. Tài liệu chính thức của Stack cũng khuyến nghị dùng Deque.

ArrayDeque làm được cả hai việc

Deque — "double ended queue" — cho thêm và lấy ở cả hai đầu. Nhờ đó nó vừa là ngăn xếp vừa là hàng đợi:

// ngăn xếp
dq.push(x);   // = addFirst
dq.pop();     // = removeFirst

// hàng đợi
q.offer(x);   // = addLast
q.poll();     // = removeFirst

  poll() lần lượt : một, hai, ba

Bên trong nó là một mảng vòng: hai chỉ số đầu và cuối chạy vòng quanh một mảng, không phải dịch chuyển phần tử. Nhờ đó thêm/xoá ở hai đầu đều O(1) trung bình, và dữ liệu nằm liền khối nên tận dụng cache — lý do nó thắng LinkedList trong phép đo ở bài ArrayList.

Nhược điểm duy nhất: không nhận null.

  add(null) -> NullPointerException

Đây là chủ ý, vì poll() dùng null để báo "hàng đợi rỗng". Cho phép null làm phần tử thì không phân biệt được hai trường hợp.

Hai bộ phương thức, khác nhau ở cách báo lỗi

Queue có sáu phương thức chính, chia thành hai bộ làm cùng việc:

Việc Ném ngoại lệ Trả giá trị đặc biệt
Thêm add(x) offer(x) → false
Lấy và xoá remove() poll() → null
Xem không xoá element() peek() → null 
  poll() khi rỗng   : null
  peek() khi rỗng   : null
  remove() khi rỗng : NoSuchElementException
  element() khi rỗng: NoSuchElementException

Chọn theo tình huống: hàng đợi rỗng là chuyện bình thường thì dùng poll/peek; là dấu hiệu lỗi thì dùng remove/element.

Với offer và add thì khác biệt chỉ có ý nghĩa ở hàng đợi có giới hạn sức chứa — ArrayBlockingQueue chẳng hạn. ArrayDeque không giới hạn nên hai cái như nhau.

PriorityQueue in ra không sắp xếp

Đây là chỗ gây bối rối nhất trong bài — và là tấm bảng cấp cứu ở đầu bài.

PriorityQueue<CongViec> pq = new PriorityQueue<>(Comparator.comparingInt(CongViec::uuTien));
pq.add(new CongViec("gửi email", 5));
pq.add(new CongViec("khôi phục CSDL", 1));
pq.add(new CongViec("dọn log", 9));
pq.add(new CongViec("cảnh báo sự cố", 2));

  toString()      : [khôi phục CSDL, cảnh báo sự cố, dọn log, gửi email]
  poll() lần lượt : [khôi phục CSDL, cảnh báo sự cố, gửi email, dọn log]

Hai danh sách khác nhau. In ra thì "dọn log" (ưu tiên 9) đứng thứ ba, nhưng lấy ra thì nó cuối cùng.

Lý do: PriorityQueue là một đống nhị phân lưu trong mảng. Nó chỉ bảo đảm phần tử đầu tiên là nhỏ nhất, phần còn lại chỉ thoả tính chất đống — cha nhỏ hơn con — chứ không sắp xếp toàn bộ.

Duyệt hay toString đi theo thứ tự mảng, nên bạn thấy một trật tự nửa vời.

PriorityQueue chỉ bảo đảm thứ tự khi bạn lấy ra bằng poll(). Đừng bao giờ duyệt nó để hiển thị danh sách theo thứ tự ưu tiên — hãy sao chép rồi sắp xếp, hoặc dùng TreeSet nếu cần vừa có thứ tự vừa duyệt được.

Đổi lại, cấu trúc đống cho hiệu năng rất tốt cho đúng việc của nó: thêm và lấy phần tử nhỏ nhất đều O(log n), còn xem phần tử đầu là O(1). Sắp xếp lại toàn bộ mỗi lần thêm sẽ tốn hơn nhiều.

Dùng PriorityQueue ở đâu

Bài toán lập lịch là ví dụ tự nhiên nhất: mỗi việc có mức ưu tiên, luôn lấy việc gấp nhất ra làm trước.

while (!pq.isEmpty()) {
    xuLy(pq.poll());     // luôn là việc ưu tiên cao nhất còn lại
}

Cái hay là thêm việc mới vào giữa chừng vẫn đúng thứ tự — không cần sắp xếp lại.

Ngoài ra nó là nền của thuật toán Dijkstra, của bài toán "k phần tử lớn nhất", và của mọi hệ thống hàng đợi công việc.

Mẹo nhỏ cho bài toán "k phần tử lớn nhất trong n phần tử": giữ một PriorityQueue sức chứa k theo thứ tự tăng dần, thêm từng phần tử và bỏ đầu khi vượt quá k. Cách này chỉ tốn O(n log k) bộ nhớ k, thay vì sắp xếp cả n phần tử.

Vài chi tiết khác

PriorityQueue không nhận null, và nếu không truyền comparator thì phần tử phải Comparable.

Deque cũng là SequencedCollection từ Java 21, nên có getFirst, getLast, reversed.

LinkedList cũng cài Deque, nhưng ArrayDeque nhanh hơn cho mọi việc — trừ khi bạn cần cả API List (chỉ số, subList).

Cần hàng đợi an toàn nhiều luồng thì có cả một họ riêng: ConcurrentLinkedQueue, LinkedBlockingQueue, ArrayBlockingQueue. BlockingQueue là nền của mẫu sản xuất – tiêu thụ, và ta sẽ gặp lại ở chặng đồng thời.

Bảng chọn nhanh

Cần Dùng
Ngăn xếp ArrayDeque (push/pop)
Hàng đợi FIFO ArrayDeque (offer/poll)
Lấy theo mức ưu tiên PriorityQueue
Hàng đợi giữa các luồng LinkedBlockingQueue
Vừa ưu tiên vừa duyệt được theo thứ tự TreeSet

Muốn tự vấp cho nhớ: tạo một PriorityQueue<Integer>, thêm 5, 1, 9, 2 theo đúng thứ tự đó rồi System.out.println(pq). Bạn sẽ thấy [1, 2, 9, 5] — phần tử đầu đúng là nhỏ nhất, nhưng 9 lại đứng trước 5. Chính cái cảnh đó giải thích vì sao bao nhiêu người từng mở một issue báo lỗi "PriorityQueue sắp xếp sai" — trong khi nó đang làm đúng hợp đồng của mình, chỉ là hợp đồng ấy nói về poll() chứ không nói về toString().

Mẫu số chung

Cả hai cú bẫy hôm nay là cùng một bài học đội hai lốt: cấu trúc dữ liệu hứa với bạn một hợp đồng về thao tác, không phải một cách bày biện bên trong — và khi bạn nhìn thẳng vào ruột nó (duyệt, in ra), bạn thấy cái cách bày biện đó chứ không thấy hợp đồng. Đổi ngôn ngữ, cái bẫy đi theo y nguyên. Python có heapq thao tác thẳng trên một list, và in cái list đó ra bạn thấy đúng mảng đống lộn xộn như toString của Java — chỉ heappop mới trả thứ tự; muốn xem có thứ tự phải sorted(h). C++ std::priority_queue thì đi hướng ngược: nó giấu hẳn ruột, không cho bạn duyệt, nên cái bẫy "in ra thấy sai" biến mất vì bạn không nhìn vào được. Go không có ngăn xếp hay hàng đợi riêng — người ta dùng slice làm cả hai, và container/heap cũng chỉ bảo đảm phần tử đỉnh.

Điểm chung nằm dưới đáy: một cấu trúc chỉ bảo đảm cái nó nói là bảo đảm, và mọi thứ ngoài đó là chi tiết cài đặt bạn không được dựa vào. Đống bảo đảm phần tử nhỏ nhất ở đỉnh, không bảo đảm phần còn lại sắp xếp. HashMap bảo đảm tra cứu O(1), không bảo đảm thứ tự duyệt. Ngăn xếp bảo đảm vào-sau-ra-trước, không bảo đảm bạn duyệt được từ đỉnh (Stack cũ thì ngược hẳn). Ngày bạn viết mã dựa vào một hành vi không nằm trong hợp đồng là ngày bạn đặt một quả bom hẹn giờ chờ phiên bản JDK sau gỡ ngòi — hoặc tệ hơn, chờ một người đọc mã tin vào những gì họ thấy khi in ra.

Ngày mai: Iterator và ConcurrentModificationException — cơ chế modCount, cách xoá phần tử an toàn, và vì sao vòng lặp for-each không cứu được bạn.