Java程序 实现PriorityQueue API

PriorityQueue是一个线性数据结构，其中的元素根据其自然排序或在构造时在队列中提供的一些自定义比较器来排序。在PriorityQueue中，队列的前部指向最小的元素，而后部则根据自然排序指向最大的元素。对于按字母顺序排列的PriorityQueue，它们的ASCII值将被考虑用于排序。

PriorityQueue的一些重要特征如下。

• 它不允许插入空元素。
• 它是一个无界的队列，意味着它的大小可以扩展。
• 它继承了Object, Abstract Collection, AbstractQueue等类。
• 它不是线程安全的。
• 它不能为不可比较的对象创建。

各种操作的时间复杂性。

• 插入和删除是F阶O(log(n))。
• remove()和contains()方法的阶数是O(n)
• 检索操作是最快的，其顺序为O(1)。

PriorityQueue类继承了Queue接口和它的所有方法。PriorityQueue API实现了可序列化（serializable）、可迭代（Iterable）、集合（Collection）和队列（Queue），这可以从下图所示的架构中感知到。

Serializable, Iterable<E>, Collection<E>, Queue<E>

语法:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

参数: E – 这个队列中持有的元素的类型。

方法:

Implementation:

示例

// Java Program to implement Priority Queue API
 
// Importing all classes from java.util package
import java.util.*;
 
// Class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Creating(Declaring) an object of PriorityQueue of
        // Integer type i.e Integer elements will be
        // inserted in above object
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        // Adding elements to the object created above
        // Custom inputs
        pq.add(89);
        pq.add(67);
        pq.add(78);
        pq.add(12);
        pq.add(19);
 
        // Printing the head of the PriorityQueue
        // using peek() method of Queues
        System.out.println("PriorityQueue Head:"
                           + pq.peek());
 
        // Display message
        System.out.println("\nPriorityQueue contents:");
 
        // Defining the iterator to traverse over elements of
        // object
        Iterator i = pq.iterator();
 
        // Condition check using hasNext() method which hold
        // true till single element is remaining in List
        while (i.hasNext()) {
 
            // Printing the elements of object
            System.out.print(i.next() + " ");
        }
 
        // Removing random element from above elements added
        // from the PriorityQueue
        // Custom removal be element equals 12
        pq.remove(12);
 
        // Display message
        System.out.print("\nPriorityQueue contents:");
 
        // Declaring iterator to traverse over object
        // elements
        Iterator it = pq.iterator();
 
        // Condition check using hasNext() method which hold
        // true till single element is remaining in List
        while (it.hasNext()) {
 
            // Printing the elements
            System.out.print(it.next() + " ");
        }
 
        // Removing all the elements from the PriorityQueue
        // using clear() method
        pq.clear();
 
        // Adding another different set of elements
        // to the Queue object
        // Custom different inputs
        pq.add(5);
        pq.add(7);
        pq.add(2);
        pq.add(9);
 
        // Checking a random element just inserted
        // using contains() which returns boolean value
        System.out.print("The queue has 7 = "
                         + pq.contains(7));
 
        // Display message for content in Priority queue
        System.out.print("\nPriorityQueue contents:");
 
        // Converting PriorityQueue to array
        // using toArray() method
        Object[] arr = pq.toArray();
 
        // Iterating over the array elements
        for (int j = 0; j < arr.length; j++) {
 
            // Printing all the elements in the array
            System.out.print(arr[j] + " ");
        }
    }
}

输出

PriorityQueue Head:12

PriorityQueue contents:
12 19 78 89 67 
PriorityQueue contents:19 67 78 89 The queue has 7 = true
PriorityQueue contents:2 7 5 9