Hướng dẫn và ví dụ Java PriorityQueue
1. PriorityQueue
PriorityQueue là một lớp thi hành interface Queue nên nó có đầy đủ các đặc điểm của một hàng đợi và hỗ trợ tất cả các hoạt động tuỳ chọn của Collection. Tuy nhiên khác với một hàng đợi thông thường, các phần tử của PriorityQueue được xắp xếp theo một thứ tự tăng dần dựa trên thứ tự tự nhiên của chúng hoặc theo một Comparator được cung cấp (Tuỳ vào constructor được sử dụng), vì vậy khi một phần tử mới được chèn vào PriorityQueue nó có thể không ở vị trí cuối cùng.
Các đặc điểm thừa kế từ Queue:
- Cho phép phần tử trùng lặp nhưng không cho phép phần tử null.
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
PriorityQueue là một hàng đợi không giới hạn (unbounded), các phần tử được xắp xếp theo thứ tự tăng dần và cho phép các phần tử trùng lặp.
Về cơ bản, PriorityQueue quản lý một mảng đối tượng (Object[]) để lưu trữ các phần tử của nó. Độ dài của mảng này lớn hơn so với số phần tử của hàng đợi, tuy nhiên mảng này sẽ được thay thế bởi một mảng khác có độ dài lớn hơn nếu cần thiết.
PriorityQueue constructors
PriorityQueue()
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
PriorityQueue(Collection<? extends E> c)
PriorityQueue(Comparator<? super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)
- Constructor PriorityQueue(int initialCapacity) tạo ra một đối tượng PriorityQueue với mảng nội bộ có kích thước initialCapacity. Trường hợp này tất cả các phần tử của PriorityQueue phải là kiểu Comparable để có thể tự so sánh với nhau, và phần tử null là không được phép.
- Constructor PriorityQueue(Comparator) tạo ra một đối tượng PriorityQueue với kích thước mảng nội bộ mặc định là 11, đồng thời nó được cung cấp một Comparator để so sánh các phần tử với nhau.
PriorityQueue là một hàng đợi không được đồng bộ, vì vậy bạn không nên sử dụng nó trong môi trường multithreading, thay vào đó, hãy sử dụng lớp an toàn theo luồng (thread-safe) PriorityBlockingQueue.
// Methods inherited from Collection:
Iterator<E> iterator()
default Spliterator<E> spliterator()
- Iterator có được từ PriorityQueue hộ trợ tất cả các phương thức tuỳ chọn.
- Iterator (hoặc Spliterator) có được từ PriorityQueue không đảm bảo rằng nó sẽ giúp duyệt qua (traverse) các phần tử theo thứ tự ưu tiên. Nếu muốn duyệt qua các phần tử theo thứ tự ưu tiên hãy cân nhắc sử dụng Arrays.sort(priorityQueue.toArray()).
- Queue
- Deque
- ConcurrentLinkedQueue
- BlockingDeque
- BlockingQueue
- TransferQueue
- ArrayDeque
- ConcurrentLinkedDeque
- LinkedList
- ArrayBlockingQueue
- DelayQueue
- LinkedBlockingQueue
- LinkedBlockingDeque
- PriorityBlockingQueue
- SynchronousQueue
- LinkedTransferQueue
2. Examples
String là kiểu dữ liệu có thể tự so sánh được với nhau vì nó thi hành interface Comparable. Vì vậy không cần cung cấp một Comparator cho PriorityQueue<String>.
PriorityQueueEx1.java
package org.o7planning.priorityqueue.ex;
import java.util.PriorityQueue;
public class PriorityQueueEx1 {
public static void main(String[] args) {
PriorityQueue<String> queue = new PriorityQueue<>();
queue.add("F");
queue.add("D");
queue.add("B");
queue.add("A");
queue.add("C");
String s = null;
// Retrieves and removes the head of this queue
while((s = queue.poll())!= null) {
System.out.println(s);
}
}
}
Output:
A
B
C
D
F
Ví dụ: Lớp Customer với các property fullName, loyaltyPoints (Họ tên, số điểm tích luỹ khi mua hàng). Khách hàng có loyaltyPoints cao hơn sẽ được ưu tiên phục vụ.
Customer.java
package org.o7planning.beans;
public class Customer implements Comparable<Customer> {
private String fullName;
private int loyaltyPoints;
public Customer(String fullName, int pointOfPurchase) { //
this.fullName = fullName;
this.loyaltyPoints = pointOfPurchase;
}
public String getFullName() {
return fullName;
}
public int getLoyaltyPoints() {
return loyaltyPoints;
}
@Override
public int compareTo(Customer other) {
if (other == null) {
return -1; // this < other
}
int delta = this.loyaltyPoints - other.loyaltyPoints;
if (delta != 0) {
return - delta;
}
return this.fullName.compareTo(other.fullName);
}
}
PriorityQueueEx2.java
package org.o7planning.priorityqueue.ex;
import java.util.PriorityQueue;
import org.o7planning.beans.Customer;
public class PriorityQueueEx2 {
public static void main(String[] args) {
Customer tom = new Customer("Tom", 200);
Customer jerry = new Customer("Jerry", 50);
Customer donald = new Customer("Donald", 300);
Customer mickey = new Customer("Mickey", 30);
Customer daffy = new Customer("Daffy", 500);
PriorityQueue<Customer> queue = new PriorityQueue<>();
queue.add(tom);
queue.add(jerry);
queue.add(donald);
queue.add(mickey);
queue.add(daffy);
Customer currentCustomer = null;
while((currentCustomer = queue.poll())!= null) { // Retrieves and removes
System.out.println("--- Serving customer: " + currentCustomer.getFullName() + " ---");
System.out.println(" >> Loyalty Points: " + currentCustomer.getLoyaltyPoints());
System.out.println();
}
}
}
Output:
--- Serving customer: Daffy ---
>> Loyalty Points: 500
--- Serving customer: Donald ---
>> Loyalty Points: 300
--- Serving customer: Tom ---
>> Loyalty Points: 200
--- Serving customer: Jerry ---
>> Loyalty Points: 50
--- Serving customer: Mickey ---
>> Loyalty Points: 30
Ví dụ: Với các phần tử không thể tự so sánh với nhau, bạn cần cung cấp một Comparator cho PriorityQueue.
PriorityQueueEx3.java
package org.o7planning.priorityqueue.ex;
import java.util.Comparator;
import java.util.PriorityQueue;
public class PriorityQueueEx3 {
public static void main(String[] args) {
Employee tom = new Employee("Tom", 2000);
Employee jerry = new Employee("Jerry", 500);
Employee donald = new Employee("Donald", 3000);
Employee mickey = new Employee("Mickey", 2000);
Employee daffy = new Employee("Daffy", 5000);
PriorityQueue<Employee> queue = new PriorityQueue<>(new EmployeeComparator());
queue.add(tom);
queue.add(jerry);
queue.add(donald);
queue.add(mickey);
queue.add(daffy);
Employee currentEmployee = null;
while ((currentEmployee = queue.poll()) != null) { // Retrieves and removes
System.out.println("--- Serving employee: " + currentEmployee.getFullName() + " ---");
System.out.println(" >> Salary: " + currentEmployee.getSalary());
System.out.println();
}
}
}
class Employee {
private String fullName;
private int salary;
public Employee(String fullName, int salary) {
this.fullName = fullName;
this.salary = salary;
}
public String getFullName() {
return fullName;
}
public int getSalary() {
return salary;
}
}
class EmployeeComparator implements Comparator<Employee> {
@Override
public int compare(Employee o1, Employee o2) {
if (o1 == o2) {
return 0;
}
if (o1 == null) {
return -1; // o1 < o2
}
if (o2 == null) {
return 1; // o1 > o2
}
int s = o1.getSalary() - o2.getSalary();
if (s != 0) {
return s;
}
return o1.getFullName().compareTo(o2.getFullName());
}
}
Output:
--- Serving employee: Jerry ---
>> Salary: 500
--- Serving employee: Mickey ---
>> Salary: 2000
--- Serving employee: Tom ---
>> Salary: 2000
--- Serving employee: Donald ---
>> Salary: 3000
--- Serving employee: Daffy ---
>> Salary: 5000
Nếu muốn duyệt qua tất cả các phần tử của một PriorityQueue mà không phải loại bỏ các phần tử, bạn có thể sử dụng Iterator hoặc Spliterator, tuy nhiên chúng không đảm báo thứ tự ưu tiên của các phần tử. Trong trường hợp này bạn nên sử dụng Arrays.sort(priorityQueue.toArray()) hoặc Arrays.sort(priorityQueue.toArray(),comparator).
PriorityQueueEx4.java
package org.o7planning.priorityqueue.ex;
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
public class PriorityQueueEx4 {
public static void main(String[] args) {
PriorityQueue<String> queue = new PriorityQueue<>();
queue.add("F");
queue.add("D");
queue.add("B");
queue.add("A");
queue.add("C");
System.out.println("--- Using Iterator: ---");
Iterator<String> ite = queue.iterator();
while(ite.hasNext()) {
String e = ite.next();
System.out.println(e);
}
System.out.println("--- Using Arrays.sort(queue.toArray()): ----");
String[] array = new String[queue.size()];
queue.toArray(array);
Arrays.sort(array);
for(String e: array) {
System.out.println(e);
}
}
}
Output:
--- Using Iterator: ---
A
B
D
F
C
--- Using Arrays.sort(queue.toArray()): ----
A
B
C
D
F
Về cơ bản, ngoài các đặc điểm nói trên PriorityQueue có đầy đủ các đặc điểm của một Queue. Các phương thức và các ví dụ liên quan về Queue được đề cập trong bài viết dưới đây:
Các hướng dẫn Java Collections Framework
- Hướng dẫn và ví dụ Java PriorityBlockingQueue
- Hướng dẫn sử dụng nền tảng tập hợp trong Java (Java Collection Framework)
- Hướng dẫn và ví dụ Java SortedSet
- Hướng dẫn và ví dụ Java List
- Hướng dẫn và ví dụ Java Iterator
- Hướng dẫn và ví dụ Java NavigableSet
- Hướng dẫn và ví dụ Java ListIterator
- Hướng dẫn và ví dụ Java ArrayList
- Hướng dẫn và ví dụ Java CopyOnWriteArrayList
- Hướng dẫn và ví dụ Java LinkedList
- Hướng dẫn và ví dụ Java Set
- Hướng dẫn và ví dụ Java TreeSet
- Hướng dẫn và ví dụ Java CopyOnWriteArraySet
- Hướng dẫn và ví dụ Java Queue
- Hướng dẫn và ví dụ Java Deque
- Hướng dẫn và ví dụ Java IdentityHashMap
- Hướng dẫn và ví dụ Java WeakHashMap
- Hướng dẫn và ví dụ Java Map
- Hướng dẫn và ví dụ Java SortedMap
- Hướng dẫn và ví dụ Java NavigableMap
- Hướng dẫn và ví dụ Java HashMap
- Hướng dẫn và ví dụ Java TreeMap
- Hướng dẫn và ví dụ Java PriorityQueue
- Hướng dẫn và ví dụ Java BlockingQueue
- Hướng dẫn và ví dụ Java ArrayBlockingQueue
- Hướng dẫn và ví dụ Java TransferQueue
Show More