数据结构学习系列——队列Queue（一）

一、基本概念：

队列（Queue）：一种先进先出（FIFO）的数据结构，即先入队的数据，出队的时候也要先出队。

二、Java中Queue的方法

在Java中，Queue接口与List、Set同一级别，都是继承了Collection接口。因此，具有从Collection接口处继承来的相关方法：addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, parallelStream, remove, removeAll, removeIf, retainAll, size, spliterator, stream, toArray, toArray；同时也具有继承自Iterable接口的forEach方法。在Queue中新引入的方法如下表：

方法返回数据类型描述add(E e)boolean增加一个元素，成功则返回true，如果队列已满，则回抛出一个IllegalStateException异常element()E检索并返回当前队列的头部元素，但不会删除。若队列为空，则回抛出一个NoSuchElementException异常offer(E e)boolean向队列中添加一个元素，成功则返回true。若队列已满，则返回false。peek()E返回队列的头部元素，但不删除。若队列为空，则返回nullpoll()E删除并返回队列的头部元素，当队列为空时返回nullremove()E删除并返回队列的头部元素

三、Java中Queue的实现

在Java中Queue只是一个接口（Interface），不能直接实例化的调用上述方法，需要借助实例化其实现类来调用。Java中Queue的实现有：

没有实现阻塞接口的LinkedList，实现了Deque接口（双向队列）。实现了AbstractQueue接口的PriorityQueue和ConcurrentLinkedQueue： 1)PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。 2)ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小。ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。实现了阻塞接口的： 名称描述ArrayBlockingQueue一个由数组支持的有界队列LinkedBlockingQueue一个由链接节点支持的可选有界队列PriorityBlockingQueue一个由优先级堆支持的无界优先级队列DelayQueue一个由优先级堆支持的、基于时间的调度队列SynchronousQueue一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制

练习代码：

这里使用ArrayBlockingQueue来学习Queue的基本方法。

package com.fuqi.queuelearn; import java.util.Queue; import java.util.concurrent.ArrayBlockingQueue; /** * @Description: 队列学习 * @Author 傅琦 * @Date 2019/5/25 20:50 * @Version V1.0 */ public class QueueLearning { public static void main(String[] args){ Queue<Integer> queue = new ArrayBlockingQueue<>(5); System.out.println("the init queue: "+ queue); // 在队列为空时调用remove方法，会有NoSuchElementException异常抛出 // queue.remove(); // 此时抛出了NullPointerException：因为此时返回结果为null，所以不能进行引用，强行引用就抛出了空指针异常 // int head = queue.peek(); // int head = queue.poll(); // System.out.println("now, the head of queue: " + head); queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); queue.offer(5); // 此时回抛出异常：IllegalStateException: Queue full // queue.add(6); boolean res2 = queue.offer(6); System.out.println("the result of function offer: " + res2); boolean res3 = queue.contains(6); System.out.println("the result of function contains: " + res3); // 若队列为空，会抛出NoSuchElementException异常 int number1 = queue.element(); System.out.println("the head of queue: " + number1); System.out.println("the queue: " + queue); int number2 = queue.poll(); System.out.println("the current head: "+ number2); System.out.println("the queue now: " + queue); queue.poll(); queue.poll(); queue.poll(); queue.poll(); System.out.println("the current head of queue: " + queue.poll()); System.out.println("the current head of queue: " + queue.peek()); } }

参考链接： java队列——queue详细分析 https://docs.oracle.com/javase/8/docs/api/