Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
java队列queue实现_java多线程面试题及答案,希望能够帮助你!!!。

目录

1.什么是队列？

2.Queue的特性

1.阻塞队列

1.ArrayBlockingQueue

2.LinkedBlockingQueue

3.PriorityBlockingQueue

4.DelayQueue

5.SynchronousQueue

2.非阻塞队列

1.ConcurrentLinkedQueue

3.双端队列

1.LinkedBlockingDeque

1.什么是队列？

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations(为在处理之前保存元素而设计的集合。除了基本的集合操作之外，队列还提供了额外的插入、提取和检查操作)

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out). Whatever the ordering used, the head of the queue is that element which would be removed by a call to remove() or poll(). In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties.(队列通常(但不一定)以FIFO(先进先出)方式对元素排序。例外情况包括优先级队列，根据提供的比较器或元素的自然顺序对元素进行排序，以及LIFO (或堆栈)的后进先出。无论使用何种排序方式，队列的头就是可以通过调用remove()或poll()删除的元素。在FIFO队列中，所有新元素都插入到队列的尾部。其他类型的队列可能使用不同的放置规则。每个Queue实现必须指定其排序属性。)

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues.(如果可能，offer方法将插入一个元素，否则返回false。这与集合不同。方法，它只能通过抛出未检查的异常来失败添加元素。提供方法设计用于故障是正常的，而不是例外的情况，例如，在固定容量(或“有界”)的队列中。)

The remove() and poll() methods remove and return the head of the queue. Exactly which element is removed from the queue is a function of the queue's ordering policy, which differs from implementation to implementation. The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.(remove()和poll()方法删除并返回队列的头部。究竟从队列中删除哪个元素是队列排序策略的一个函数，这在不同的实现中是不同的。remove()和poll()方法的不同之处在于它们在队列为空时的行为:remove()方法抛出异常，而poll()方法返回null。)

The element() and peek() methods return, but do not remove, the head of the queue.(element()和peek()方法返回但不删除队列头部。)

The Queue interface does not define the blocking queue methods, which are common in concurrent programming. These methods, which wait for elements to appear or for space to become available, are defined in the java.util.concurrent.BlockingQueue interface, which extends this interface.(Queue接口没有定义阻塞队列方法，这在并发编程中很常见。这些方法等待元素出现或空间可用，它们在java.util.concurrent.BlockingQueue接口中定义，该接口扩展了这个接口。)

Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null. Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.(队列实现通常不允许插入空元素，尽管有些实现(如LinkedList)不禁止插入空元素。即使在允许的实现中，null也不应该插入到Queue中，因为null也被poll方法用作特殊的返回值，表示队列不包含元素。)

从jdk的解释上，我们可以知道

• 队列就是为处理之前保存元素而设计的集合。它除了基本的集合操作之外，还有插入，提取，检查操作。
• 队列通常以先进先出对元素进行排序，当然这不是一定的，也有优先级队列和后进先出
• 队列方法的返回值总结

• Queue接口没有定义阻塞队列方法，而是在BlockingQueue中定义的，所有实现该接口的类我们可以认为是阻塞队列(注意阻塞队列不是一定阻塞的，只是提供了阻塞的方法，也有非阻塞的方法可以使用)，例如offer就是实现的BlockingQueue是阻塞的，add不是实现的BlockingQueue是非阻塞的。
• 队列通常不允许插入空元素，即使有些不禁止插入，我们也不应该插入，因为poll方法返回的特殊值就是null，表示不包含元素

2.Queue的特性

队列分为双端队列，阻塞队列，非阻塞队列等3大类

1.阻塞队列

阻塞队列包括:ArrayBlockingQueue，LinkedBlockingQueue，PriorityBlockingQueue，DelayQueue，SynchronousQueue。

阻塞队列常用于生产者和消费者的场景，生产者是往队列里添加元素的线程，消费者是从队列里拿元素的线程。阻塞队列就是生产者存放元素的容器，而消费者也只从容器里拿元素。

1.ArrayBlockingQueue

由数组支持的有界阻塞队列，这个队列对元素先进先出进行排序，容量一旦创建，就不能更改。 

为什么ArrayBlockingQueue是有界的，因为构造方法都有容量的参数

 public ArrayBlockingQueue(int capacity) { this(capacity, false); } public ArrayBlockingQueue(int capacity, boolean fair) { if (capacity <= 0) throw new IllegalArgumentException(); this.items = new Object[capacity]; lock = new ReentrantLock(fair); notEmpty = lock.newCondition(); notFull = lock.newCondition(); } public ArrayBlockingQueue(int capacity, boolean fair, Collection<? extends E> c) { this(capacity, fair); final ReentrantLock lock = this.lock; lock.lock(); // Lock only for visibility, not mutual exclusion try { int i = 0; try { for (E e : c) { checkNotNull(e); items[i++] = e; } } catch (ArrayIndexOutOfBoundsException ex) { throw new IllegalArgumentException(); } count = i; putIndex = (i == capacity) ? 0 : i; } finally { lock.unlock(); } }

为什么是阻塞的，因为提供了put和take方法，我们可以看到在容量满的时候，插入数据将会等待，容量为空的时候取数据等待。

 public void put(E e) throws InterruptedException { checkNotNull(e); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == items.length) notFull.await(); enqueue(e); } finally { lock.unlock(); } } public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (count == 0) notEmpty.await(); return dequeue(); } finally { lock.unlock(); } }

下面我们测试一下阻塞的方法，设定容量为4，在插入4的时候容量已经满了，5插入不进去，进程一直的等待。

 public static void main(String args[]) throws InterruptedException { ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(4); q.put(1); q.put(2); q.put(3); q.put(4); System.out.println("已插入4"); q.put(5); System.out.println("已插入5"); }

 再来测试一下offer阻塞，可以发现插入4和5之间是间隔了10秒，当然5肯定是插入失败了

 public static void main(String args[]) throws InterruptedException { ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(4); q.offer(1,10, TimeUnit.SECONDS); System.out.println("已插入1"+"==当前时间是:"+ new Date()); q.offer(2,10, TimeUnit.SECONDS); System.out.println("已插入2"+"==当前时间是:"+ new Date()); q.offer(3,10, TimeUnit.SECONDS); System.out.println("已插入3"+"==当前时间是:"+ new Date()); q.offer(4,10, TimeUnit.SECONDS); System.out.println("已插入4"+"==当前时间是:"+ new Date()); q.offer(5,10, TimeUnit.SECONDS); System.out.println("已插入5"+"==当前时间是:"+ new Date()); } 已插入1==当前时间是:Thu Mar 10 11:37:20 CST 2022 已插入2==当前时间是:Thu Mar 10 11:37:20 CST 2022 已插入3==当前时间是:Thu Mar 10 11:37:20 CST 2022 已插入4==当前时间是:Thu Mar 10 11:37:20 CST 2022 已插入5==当前时间是:Thu Mar 10 11:37:30 CST 2022

再来测试一下offer非阻塞，可以发现4和5之间没有等待，说明没有阻塞，当然5肯定是插入失败了，所有ArrayBlockingQueue不只有阻塞还有非阻塞

 public static void main(String args[]) throws InterruptedException { ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(4); q.offer(1); System.out.println("已插入1"+"==当前时间是:"+ new Date()); q.offer(2); System.out.println("已插入2"+"==当前时间是:"+ new Date()); q.offer(3); System.out.println("已插入3"+"==当前时间是:"+ new Date()); q.offer(4); System.out.println("已插入4"+"==当前时间是:"+ new Date()); q.offer(5); System.out.println("已插入5"+"==当前时间是:"+ new Date()); } 已插入1==当前时间是:Thu Mar 10 11:40:47 CST 2022 已插入2==当前时间是:Thu Mar 10 11:40:47 CST 2022 已插入3==当前时间是:Thu Mar 10 11:40:47 CST 2022 已插入4==当前时间是:Thu Mar 10 11:40:47 CST 2022 已插入5==当前时间是:Thu Mar 10 11:40:47 CST 2022

为什么说它是数组支持的，因为在插入数据时，我们可以看到它实现是用数组[]实现的

 public boolean offer(E e) { checkNotNull(e); final ReentrantLock lock = this.lock; lock.lock(); try { if (count == items.length) return false; else { enqueue(e); return true; } } finally { lock.unlock(); } } private void enqueue(E x) { // assert lock.getHoldCount() == 1; // assert items[putIndex] == null; final Object[] items = this.items; items[putIndex] = x; if (++putIndex == items.length) putIndex = 0; count++; notEmpty.signal(); }

2.LinkedBlockingQueue

基于链接节点的可选有界阻塞队列，这个队列对元素先进先出进行排序，如果容量未指定，则容量等于Integer.MAX_VALUE。

为什么说它是基于节点的，因为在插入的时候我们可以看到都有创建一个Node对象

 public boolean offer(E e) { if (e == null) throw new NullPointerException(); final AtomicInteger count = this.count; if (count.get() == capacity) return false; int c = -1; Node<E> node = new Node<E>(e); final ReentrantLock putLock = this.putLock; putLock.lock(); try { if (count.get() < capacity) { enqueue(node); c = count.getAndIncrement(); if (c + 1 < capacity) notFull.signal(); } } finally { putLock.unlock(); } if (c == 0) signalNotEmpty(); return c >= 0; }

为什么说它是可选的有界队列，因为我们可以看到构造方法可以传容量参数也可以不穿，不传的话队列默认容量为Integer.MAX_VALUE

 public LinkedBlockingQueue() { this(Integer.MAX_VALUE); } public LinkedBlockingQueue(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; last = head = new Node<E>(null); } public LinkedBlockingQueue(Collection<? extends E> c) { this(Integer.MAX_VALUE); final ReentrantLock putLock = this.putLock; putLock.lock(); // Never contended, but necessary for visibility try { int n = 0; for (E e : c) { if (e == null) throw new NullPointerException(); if (n == capacity) throw new IllegalStateException("Queue full"); enqueue(new Node<E>(e)); ++n; } count.set(n); } finally { putLock.unlock(); } }

为什么说它是阻塞的，我们可以看到取2和3之间差了10s,另外可以看到poll方法在队列是空的时候返回的是null

 public static void main(String args[]) throws InterruptedException { LinkedBlockingQueue<Integer> q = new LinkedBlockingQueue<>(10); q.offer(1); System.out.println("已插入1"+"==当前时间是:"+ new Date()); q.offer(2); System.out.println("已插入2"+"==当前时间是:"+ new Date()); Integer q1 = q.poll(10l,TimeUnit.SECONDS); System.out.println("当前元素是："+q1+"==当前时间是:"+ new Date()); Integer q2 = q.poll(10l,TimeUnit.SECONDS); System.out.println("当前元素是："+q2+"==当前时间是:"+ new Date()); Integer q3 = q.poll(10l,TimeUnit.SECONDS); System.out.println("当前元素是："+q3+"==当前时间是:"+ new Date()); } 已插入1==当前时间是:Thu Mar 10 12:13:24 CST 2022 已插入2==当前时间是:Thu Mar 10 12:13:24 CST 2022 当前元素是：1==当前时间是:Thu Mar 10 12:13:24 CST 2022 当前元素是：2==当前时间是:Thu Mar 10 12:13:24 CST 2022 当前元素是：null==当前时间是:Thu Mar 10 12:13:34 CST 2022

3.PriorityBlockingQueue

有优先级的无界阻塞队列，内部由数组实现

测试下优先级的效果，默认由到大，当然也可以指定比较器，内部有个构造参数可以指定比较器

public class MyProducer implements Runnable{ private BlockingQueue blockingQueue; MyProducer(BlockingQueue blockingQueue){ this.blockingQueue = blockingQueue; } @Override public void run() { int[] arry = {5,1,20,3,100}; for (int i : arry) { System.out.println("正在生产:"+i); blockingQueue.offer(i); } } } public class MyCustomer implements Runnable{ private BlockingQueue blockingQueue; MyCustomer(BlockingQueue blockingQueue){ this.blockingQueue = blockingQueue; } @Override public void run() { while(true){ Object o = blockingQueue.poll(); System.out.println("正在消费："+o); try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } } } } public static void main(String args[]) throws InterruptedException { PriorityBlockingQueue q = new PriorityBlockingQueue<Integer>(); new Thread(new MyProducer(q),"producer thread").start(); new Thread(new MyCustomer(q),"customer thread").start(); } 正在生产:5 正在生产:1 正在生产:20 正在生产:3 正在生产:100 正在消费：1 正在消费：3 正在消费：5 正在消费：20 正在消费：100 正在消费：null

4.DelayQueue

一个被延迟的元素的无界阻塞队列，元素只有在其延迟过期时才能被取走。

我们查看DelayQueue的源码，看到类是这么写的

public class DelayQueue<E extends Delayed>说明队列元素需要实现Delay接口

由Delayed定义可以得知，队列元素需要实现getDelay(TimeUnit unit)方法和compareTo(Delayed o)方法, getDelay定义了剩余到期时间，compareTo方法定义了元素排序规则

下面我们来测试一下

class DelayTest implements Delayed{ String name; //触发时间 private long time; DelayTest(String name,int time,TimeUnit unit){ this.name=name; this.time=System.currentTimeMillis()+(time > 0? unit.toMillis(time): 0); } @Override public long getDelay(TimeUnit unit) { return time-System.currentTimeMillis(); } @Override public int compareTo(Delayed o) { DelayTest d = (DelayTest) o; long diff = this.time-d.time; if(diff<0){ return -1; }else{ return 1; } } } public static void main(String args[]) throws InterruptedException { DelayTest t1 = new DelayTest("t1",5,TimeUnit.SECONDS); DelayTest t2 = new DelayTest("t2",15,TimeUnit.SECONDS); DelayTest t3 = new DelayTest("t3",10,TimeUnit.SECONDS); DelayQueue<DelayTest> d = new DelayQueue(); d.offer(t1); d.offer(t2); d.offer(t3); while(true){ DelayTest dt = d.take(); System.out.println("当前时间:"+new Date()+"==name:"+dt.name); } } 当前时间:Thu Mar 10 16:38:07 CST 2022==name:t1 当前时间:Thu Mar 10 16:38:12 CST 2022==name:t3 当前时间:Thu Mar 10 16:38:17 CST 2022==name:t2

5.SynchronousQueue

一个阻塞队列，其中每个插入操作必须等待另一个线程相应的删除操作，反之亦然。同步队列没有任何内部容量，甚至没有1的容量，您不能偷看(peek)队列,因为元素只有在被试图删除时才会出现，非常适合用来做切换设计，在这种设计中,在一个线程中运行的对象必须与在另一个线程中运行的对象同步，以便向它传递一些信息，事件或任务

2.非阻塞队列

1.ConcurrentLinkedQueue

基于链接节点的无界线程安全队列。 这个队列将元素排序为FIFO(先进先出)。当许多线程将共享对公共集合的访问时，ConcurrentLinkedQueue是一个合适的选择。 与大多数其他并发集合实现一样，该类不允许使用空元素。 

 public boolean offer(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); for (Node<E> t = tail, p = t;;) { Node<E> q = p.next; if (q == null) { // p is last node if (p.casNext(null, newNode)) { // Successful CAS is the linearization point // for e to become an element of this queue, // and for newNode to become "live". if (p != t) // hop two nodes at a time casTail(t, newNode); // Failure is OK. return true; } // Lost CAS race to another thread; re-read next } else if (p == q) // We have fallen off list. If tail is unchanged, it // will also be off-list, in which case we need to // jump to head, from which all live nodes are always // reachable. Else the new tail is a better bet. p = (t != (t = tail)) ? t : head; else // Check for tail updates after two hops. p = (p != t && t != (t = tail)) ? t : q; } }

我们可以看到offer方法没有lock，所以不是个阻塞的方法

3.双端队列

Deque 全称为double ended queue，即双端队列，运行在队列2端进行插入或删除等操作，因此不仅可以作为队列先进先出使用，还可以作为栈先进后出使用。

常见的实现Deque接口的类有：LinkedBlockingDeque，ConcurrentLinkedDeque，ArrayDeque

Deque常见的方法如下

//在队首添加元素 void addFirst(E e); //在队首添加元素 boolean offerFirst(E e); //在队尾添加元素 void addLast(E e); boolean offerLast(E e); //删除队首元素 E removeFirst(); E pollFirst(); //删除队尾元素 E removeLast(); E pollLast(); //获取队首元素 E getFirst(); E peekFirst(); //获取队尾元素 E getLast(); E peekLast();

下面以LinkedBlockingDeque为例说明

1.LinkedBlockingDeque

public class TestDeque { public static void main(String args[]){ LinkedBlockingDeque deque= new LinkedBlockingDeque<>(5); deque.offer(1); deque.offer(2); deque.offer(3); deque.offerFirst(0); deque.offerLast(4); while(!deque.isEmpty()){ System.out.println("element:"+deque.poll()); } } } element:0 element:1 element:2 element:3 element:4

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。