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.

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

Thử ba mươi giây

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. Ba mươi giây đó giải thích được vì sao bao nhiêu người từng mở một issue báo lỗi "PriorityQueue sắp xếp sai".

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.