Mục lục

PriorityQueue
Examples

Hướng dẫn và ví dụ Java PriorityQueue

Xem thêm các chuyên mục:

Các hướng dẫn Java Collections Framework

PriorityQueue
Examples

Nhóm phát triển của chúng tôi vừa ra mắt website langlearning.net học tiếng Anh, Nga, Đức, Pháp, Việt, Trung, Hàn, Nhật, ... miễn phí cho tất cả mọi người.
Là một website được viết trên công nghệ web Flutter vì vậy hỗ trợ rất tốt cho người học, kể cả những người học khó tính nhất.
Hiện tại website đang tiếp tục được cập nhập nội dung cho phong phú và đầy đủ hơn. Mong các bạn nghé thăm và ủng hộ website mới của chúng tôi.

Hãy theo dõi chúng tôi trên Fanpage để nhận được thông báo mỗi khi có bài viết mới.

Facebook

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.

Java Queue

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.

Java 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()).

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.

So sánh và sắp xếp trong Java

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:

Java Queue

Xem thêm các chuyên mục:

Các hướng dẫn Java Collections Framework