JavaQueue

Queue 接口

Queue 接口出现在 java.util 包中，它也继承自 Collection 接口，用于保存要按先进先出 FIFO（First In First Out）顺序处理的元素。它是一个有序的对象列表，其使用仅限于在列表末尾插入元素并从列表开头删除元素，即遵循队列先进先出的基本原则。
Queue 接口的继承实现关系
作为一个接口，Queue 需要一个用于声明的具体类，最常见的类是 java 中的 _PriorityQueue_ 和 _LinkedList_。不过，这两个实现类都不是线程安全的。如果需要线程安全的实现，就可以考虑 java.util.concurrent 包下面的 _PriorityBlockingQueue_ 类。
Queue 接口的声明：

  1. public interface Queue extends Collection

创建 Queue 对象，因为 Queue 是一个接口，所以只能使用 Queue 接口的实现类来创建实例，比如：

  1. // Obj 是存储在 Queue 中的对象类型
  2. Queue<Obj> queue = new PriorityQueue<Obj> ();

下面以 LinkedList 为例实现一个普通队列，并进行简单的入队和出队操作：

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  4. public class QueueInterfaceDemo {
  5.     public static void main(String[] args) {
  6.         Queue<Integer> q = new LinkedList<>();
  8.         // 向队列中依次添加 {0, 1, 2, 3, 4} 
  9.         for (int i = 0; i < 5; i++) {
  10.             q.add(i);
  11.         }
  13.         // 打印队列中的元素
  14.         System.out.println("Elements of queue " + q);
  16.         // 移除对头的元素 0 
  17.         int removedEle = q.remove();
  18.         System.out.println("removed element-" + removedEle);
  20.         System.out.println(q);
  22.         // 取出对头元素，但不移除
  23.         int head = q.peek();
  24.         System.out.println("head of queue-" + head);
  26.         // 计算当前的队列大小
  27.         int size = q.size();
  28.         System.out.println("Size of queue-" + size);
  29.     }
  30. }

Queue 接口的操作

添加元素

可以使用 add() 方法向队列中添加元素。此外 _PriorityQueue_ 中不保留元素的插入顺序。元素默认按照升序的优先级顺序存储。关于优先队列 _PriorityQueue_ 的具体实现细节之后分享。

  1. public class QueueAddDemo {
  3.     public static void main(String[] args)
  4.     {
  5.         Queue<String> pq = new PriorityQueue<>();
  7.         pq.add("Love");
  8.         pq.add("For");
  9.         pq.add("Passion");
  11.         System.out.println(pq);
  12.     }
  13. }

删除元素

可以使用 remove() 方法删除队列中的元素。如果要删除的对象在队列中存在多个，则删除第一个匹配到的项。除此之外，poll()方法可用于删除队头元素并返回它。

  1. public class QueueRemoveDemo {
  2.     public static void main(String[] args) {
  3.         Queue<String> pq = new PriorityQueue<>();
  5.         pq.add("Love");
  6.         pq.add("For");
  7.         pq.add("Love");
  9.         System.out.println("初始队列 " + pq);
  11.         pq.remove("Love");
  13.         System.out.println("删除 Love 之后 " + pq);
  15.         System.out.println("Poll 方法 " + pq.poll());
  17.         System.out.println("最终的队列 " + pq);
  18.     }
  19. }

遍历队列

有多种方法可以遍历 _Queue_。常见的方法是将队列转换为数组并使用 for 循环遍历。但是，队列还有一个内置的迭代器，可以用来迭代队列。

  1. public class QueueIterator {
  2.     public static void main(String[] args) {
  3.         Queue<String> pq = new PriorityQueue<>();
  5.         pq.add("Geeks");
  6.         pq.add("For");
  7.         pq.add("Geeks");
  9.         Iterator iterator = pq.iterator();
  11.         while (iterator.hasNext()) {
  12.             System.out.print(iterator.next() + " ");
  13.         }
  14.     }
  15. }

队列的常用实现类

PriorityQueue

在集合框架中实现的 _PriorityQueue_ 类是一种基于优先级的对象处理方法。众所周知，队列是遵循 First-In-First-Out 的算法，但有时需要根据优先级处理队列中的元素，这时就可以选择使用 _PriorityQueue_。简单的使用示例：

  1. class PriorityQueueTest {
  2.     public static void main(String args[]) {
  3.         // 创建优先级队列
  4.         Queue<Integer> pQueue = new PriorityQueue<Integer>();
  6.         // 队列中添加元素
  7.         pQueue.add(10);
  8.         pQueue.add(20);
  9.         pQueue.add(15);
  11.         // 打印堆顶元素
  12.         System.out.println(pQueue.peek());
  14.         // 打印并删除堆顶元素
  15.         System.out.println(pQueue.poll());
  17.         // 再次打印堆顶元素
  18.         System.out.println(pQueue.peek());
  19.     }
  20. }

LinkedList

LinkedList 是集合框架中实现的链表数据结构，同时由于实现了 Queue 接口，也可以用于表示普通队列。链表是一种线性数据结构，其中元素存储在非连续的地址空间，每个元素是一个单独的对象，具有数据部分和地址部分。元素使用指针和地址进行链接。

  1. class LinkedListQueue {
  2.     public static void main(String args[]) {
  3.         // 创建一个空的链表
  4.         Queue<Integer> ll = new LinkedList<Integer>();
  6.         // 添加元素
  7.         ll.add(10);
  8.         ll.add(20);
  9.         ll.add(15);
  11.         // 取队头元素
  12.         System.out.println(ll.peek());
  14.         // 打印并删除队头元素
  15.         System.out.println(ll.poll());
  17.         // 打印队头元素
  18.         System.out.println(ll.peek());
  19.     }
  20. }

PriorityBlockingQueue

PriorityQueue 和 LinkedList 都是非线程安全的类，如果需要线程安全的实现，可以考虑 PriorityBlockingQueue ，它使用与类 PriorityQueue 相同的排序规则并提供阻塞检索操作的无界阻塞队列（unbounded blocking queue）。虽然这个队列在逻辑上是无界的，但是在添加元素时，可能会由于资源耗尽而导致 OutOfMemoryError 。此类不允许空元素。依赖于自然排序的优先级队列也不允许插入不可比对象（否则会导致 ClassCastException）。

  1. class PriorityBlockingQueueDemo {
  2.     public static void main(String[] args) {
  3.         // 创建一个优先级阻塞队列
  4.         Queue<Integer> pbq = new PriorityBlockingQueue<Integer>();
  6.         // 向队列中添加元素
  7.         pbq.add(10);
  8.         pbq.add(20);
  9.         pbq.add(15);
  11.         // 取出堆顶元素
  12.         System.out.println(pbq.peek());
  14.         // 删除 PriorityBlockingQueue 的堆顶元素
  15.         System.out.println(pbq.poll());
  17.         // 打印堆顶元素
  18.         System.out.println(pbq.peek());
  19.     }
  20. }

总结

本文主要介绍了 Queue 队列的基本概念及其主要的实现子类，现将 Queue 的特征总结如下几点：

  1. Queue 用于在队列的末尾插入元素并从队列的头部删除。它遵循 FIFO 先进先出的基本原则。
  2. Queue 接口支持 Collection 接口的所有方法，包括插入和删除等操作。
  3. LinkedList、 **ArrayBlockingQueue** 和 **PriorityQueue** 是 Queue 接口最常用的实现类。
  4. 在 java.util 包中定义的队列是无界队列。在 java.util.concurrent 包中的队列是有界队列。

    参考资料

    优先级阻塞队列: https://docs.oracle.com/javase/8/docs/api/index.html