Trong hướng dẫn này, chúng ta sẽ tìm hiểu về lớp PriorityQueue của khung công tác bộ sưu tập Java với sự trợ giúp của các ví dụ.
Các PriorityQueuelớp học cung cấp các chức năng của cấu trúc dữ liệu đống .
Nó thực hiện giao diện Hàng đợi .
Không giống như hàng đợi bình thường, các phần tử của hàng đợi ưu tiên được truy xuất theo thứ tự đã được sắp xếp.
Giả sử, chúng ta muốn truy xuất các phần tử theo thứ tự tăng dần. Trong trường hợp này, phần đầu của hàng đợi ưu tiên sẽ là phần tử nhỏ nhất. Khi phần tử này được truy xuất, phần tử nhỏ nhất tiếp theo sẽ là phần đầu của hàng đợi.
Điều quan trọng cần lưu ý là các phần tử của hàng đợi ưu tiên có thể không được sắp xếp. Tuy nhiên, các phần tử luôn được truy xuất theo thứ tự được sắp xếp.
Tạo PriorityQueue
Để tạo hàng đợi ưu tiên, chúng ta phải nhập java.util.PriorityQueuegói. Sau khi chúng tôi nhập gói, đây là cách chúng tôi có thể tạo một hàng đợi ưu tiên trong Java.
PriorityQueue<Integer> numbers = new PriorityQueue<>();
Ở đây, chúng tôi đã tạo một hàng đợi ưu tiên mà không có bất kỳ đối số nào. Trong trường hợp này, phần đầu của hàng đợi ưu tiên là phần tử nhỏ nhất của hàng đợi. Và các phần tử được loại bỏ theo thứ tự tăng dần khỏi hàng đợi.
Tuy nhiên, chúng tôi có thể tùy chỉnh thứ tự của các phần tử với sự trợ giúp của Comparatorgiao diện. Chúng ta sẽ tìm hiểu về điều đó sau trong hướng dẫn này.
Các phương pháp của PriorityQueue
Các PriorityQueuelớp học cung cấp cho việc thực hiện tất cả các phương pháp hiện diện trong Queuegiao diện.
Chèn các phần tử vào PriorityQueue
add()– Inserts the specified element to the queue. If the queue is full, it throws an exception.offer()– Inserts the specified element to the queue. If the queue is full, it returnsfalse.
Ví dụ,
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
// Using the add() method
numbers.add(4);
numbers.add(2);
System.out.println("PriorityQueue: " + numbers);
// Using the offer() method
numbers.offer(1);
System.out.println("Updated PriorityQueue: " + numbers);
}
}
Đầu ra
PriorityQueue: [2, 4] Updated PriorityQueue: [1, 4, 2]
Ở đây, chúng tôi đã tạo một hàng đợi ưu tiên có tên là số . Chúng tôi đã chèn 4 và 2 vào hàng đợi.
Mặc dù 4 được chèn trước 2, phần đầu của hàng đợi là 2. Đó là vì phần đầu của hàng đợi ưu tiên là phần tử nhỏ nhất của hàng đợi.
Sau đó, chúng tôi đã chèn 1 vào hàng đợi. Hàng đợi bây giờ được sắp xếp lại để lưu phần tử nhỏ nhất 1 vào phần đầu của hàng đợi.
Truy cập phần tử giá trị ưu tiên
Để truy cập các phần tử từ hàng đợi ưu tiên, chúng ta có thể sử dụng peek()phương pháp. Phương thức này trả về phần đầu của hàng đợi. Ví dụ,
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(4);
numbers.add(2);
numbers.add(1);
System.out.println("PriorityQueue: " + numbers);
// Using the peek() method
int number = numbers.peek();
System.out.println("Accessed Element: " + number);
}
}
Đầu ra
PriorityQueue: [1, 4, 2] Accessed Element: 1
Loại bỏ phần tử PriorityQueue
remove()– removes the specified element from the queuepoll()– returns and removes the head of the queue
Ví dụ,
import java.util.PriorityQueue;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(4);
numbers.add(2);
numbers.add(1);
System.out.println("PriorityQueue: " + numbers);
// Using the remove() method
boolean result = numbers.remove(2);
System.out.println("Is the element 2 removed? " + result);
// Using the poll() method
int number = numbers.poll();
System.out.println("Removed Element Using poll(): " + number);
}
}
Đầu ra
PriorityQueue: [1, 4, 2] Is the element 2 removed? true Removed Element Using poll(): 1
Lặp lại trên một giá trị ưu tiên
Để lặp lại các phần tử của hàng đợi ưu tiên, chúng ta có thể sử dụng iterator()phương thức này. Để sử dụng phương pháp này, chúng ta phải nhập java.util.Iteratorgói. Ví dụ,
import java.util.PriorityQueue;
import java.util.Iterator;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>();
numbers.add(4);
numbers.add(2);
numbers.add(1);
System.out.print("PriorityQueue using iterator(): ");
//Using the iterator() method
Iterator<Integer> iterate = numbers.iterator();
while(iterate.hasNext()) {
System.out.print(iterate.next());
System.out.print(", ");
}
}
}
Đầu ra
PriorityQueue using iterator(): 1, 4, 2,
Các phương thức ưu tiên khác
| Methods | Decfscriptions |
|---|---|
contains(element) | Searches the priority queue for the specified element. If the element is found, it returns true, if not it returns false. |
size() | Returns the length of the priority queue. |
toArray() | Converts a priority queue to an array and returns it. |
Bộ so sánh giá trị ưu tiên
Trong tất cả các ví dụ trên, các phần tử hàng đợi ưu tiên được truy xuất theo thứ tự tự nhiên (thứ tự tăng dần). Tuy nhiên, chúng tôi có thể tùy chỉnh thứ tự này.
Đối với điều này, chúng ta cần tạo lớp so sánh của riêng mình để triển khai Comparatorgiao diện. Ví dụ,
import java.util.PriorityQueue;
import java.util.Comparator;
class Main {
public static void main(String[] args) {
// Creating a priority queue
PriorityQueue<Integer> numbers = new PriorityQueue<>(new CustomComparator());
numbers.add(4);
numbers.add(2);
numbers.add(1);
numbers.add(3);
System.out.print("PriorityQueue: " + numbers);
}
}
class CustomComparator implements Comparator<Integer> {
@Override
public int compare(Integer number1, Integer number2) {
int value = number1.compareTo(number2);
// elements are sorted in reverse order
if (value > 0) {
return -1;
}
else if (value < 0) {
return 1;
}
else {
return 0;
}
}
}
Đầu ra
PriorityQueue: [4, 3, 1, 2]
Trong ví dụ trên, chúng ta đã tạo một hàng đợi ưu tiên chuyển lớp CustomComparator làm đối số.
Lớp CustomComparator thực hiện Comparatorgiao diện.
Sau đó, chúng tôi ghi đè compare()phương thức. Phương thức bây giờ làm cho phần đầu của phần tử là số lớn nhất.
Để tìm hiểu thêm về trình so sánh, hãy truy cập Trình so sánh Java .