列队数据结构学习

旧城等待， 2023-10-01 22:10 32阅读 0赞

## Queue定义 ##

队列（queue）是一组有序的元素，提取元素时按顺序 **从队头读取** 。队列一般 **按照插入元素的顺序** 实现可分成两类：

1.  先进先出（ﬁrst-in, ﬁrst-out，FIFO）队列
2.  后进先出（last-in, ﬁrst-out，LIFO）队列  
    其中，LIFO 队列也叫栈（stack）

--------------------

Queue与List、Set的区别：

1.  与 List 不同的是：Queue 接口没有定义处理任意 **索引位** 元素的方法，只有队列的头一个元素能访问。
2.  与 Set 不同的是：Queue 的实现往往 **允许出现重复** 的元素。

--------------------

Queue的所有实现都要具有一个**固定的容量**：

1.  队列已满时，不能再添加元素。
2.  队列为空时，不能再删除元素。
3.  基于队列的算法都会用到 **满** 和 **空** 这两个状态，所以 Queue 接口的方法通过返回值表明这两个状态，而不会抛出异常。具体而言，peek() 和 poll() 方法返回 null 表示队列为空，因此，多数 Queue 接口的实现**不允许用 null 作元素**。

--------------------

队列也可以使用其他顺序，如：

*  优先队列（priority queue）根据外部 Comparator 对象或 Comparable 类型元素的自然顺序排序元素。

--------------------

Queue接口在java.util.Queue包中定义，如下：

public interface Queue<E> extends Collection<E>

### 常用方法 ###

#### 1. 添加元素 ####

boolean add(E e);

向队列中添加指定元素。对于有界队列，成功时返回true，如果当前没有可用空间，则抛出非法状态异常。

boolean offer(E e);

向队列中添加指定元素。对于有界队列，由于有界的队列已满而无法添加元素时，这个方法返回 false，而不会抛出异常。

#### 2. 提取元素 ####

E remove();

移除并返回队头的元素。如果队列为空，这个方法会**抛出 NoSuchElementException 异常**。

E poll();

作用和 remove() 方法类似，移除并返回队头的元素， 不过，如果队列为空，这个方法会**返回 null**，而不抛出异常。

E element();

其作用是返回队头的元素，但不将其从队列中移除。如果队列为空，这个方法**抛出 NoSuchElementException 异常**。

E peek();

作用和 element() 方法类似，但队列为空时，**返回 null**;

### 总结 ###

添加方法用**offer（）**

获取方法用**poll（）**

### 队列分类 ###

![https//p3juejinbyteimgcom/toscnik3u1fbpfcp/f54994efac0d43de9c8a93f0b8ef9f5atplvk3u1fbpfcpzoomincropmark1304000awebp][https_p3juejinbyteimgcom_toscnik3u1fbpfcp_f54994efac0d43de9c8a93f0b8ef9f5atplvk3u1fbpfcpzoomincropmark1304000awebp]

## 阻塞队列 ##

阻塞式队列（blocking queue）： 是一种定义了阻塞式 put() 和 take() 方法的队列。

*  put() 方法的作用是把元素添加到队列中。阻塞式队列中，如果需要，这个方法会一直等待，直到队列中有存储元素的空间为止。
 *  而 take() 方法的作用是从队头移除元素。阻塞式队列中，如果需要，这个方法会一直等待，直到队列中有元素可供移除为止。
 *  阻塞式队列是很多多线程算法的重要组成部分，因此 BlockingQueue 接口（扩展 Queue 接口）在 java.util.concurrent 包中定义。![https//images2017cnblogscom/blog/1182892/201711/118289220171122100317930842768608png][https_images2017cnblogscom_blog_1182892_201711_118289220171122100317930842768608png]

BlockingQueue 对插入操作、移除操作、获取元素操作提供了四种不同的方法用于不同的场景中使用：

1、抛出异常；

2、返回特殊值（null 或 true/false，取决于具体的操作）；

3、阻塞等待此操作，直到这个操作成功；

4、阻塞等待此操作，直到成功或者超时指定时间。总结如下：

**检查操作不消耗元素**

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>Throws exception</th> 
   <th>Special value</th> 
   <th>Blocks</th> 
   <th>Times out</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>Insert</strong></td> 
   <td>add(e)</td> 
   <td>offer(e)</td> 
   <td><strong>put(e)</strong></td> 
   <td>offer(e, time, unit)</td> 
  </tr> 
  <tr> 
   <td><strong>Remove</strong></td> 
   <td>remove()</td> 
   <td>poll()</td> 
   <td><strong>take()</strong></td> 
   <td>poll(time, unit)</td> 
  </tr> 
  <tr> 
   <td><strong>检查</strong></td> 
   <td>element()</td> 
   <td>peek()</td> 
   <td>not applicable</td> 
   <td>not applicable</td> 
  </tr> 
 </tbody> 
</table>

### 四种阻塞队列 ###

**LinkedBlockingQueue**的容量是没有上限的（说的不准确，在不指定时容量为Integer.MAX\_VALUE），但是也可以选择指定其最大容量，它是基于链表的队列，此队列按 FIFO（先进先出）排序元素。

**ArrayBlockingQueue**在构造时需要指定容量， 并可以选择是否需要公平性，如果公平参数被设置true，等待时间最长的线程会优先得到处理（其实就是通过将ReentrantLock设置为true来 达到这种公平性的：即等待时间最长的线程会先操作）。通常，公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队 列，此队列按 FIFO（先进先出）原则对元素进行排序。

**PriorityBlockingQueue**是一个带优先级的 队列，而不是先进先出队列。元素按优先级顺序被移除，该队列也没有上限（看了一下源码，PriorityBlockingQueue是对 PriorityQueue的再次包装，是基于堆数据结构的，而PriorityQueue是没有容量限制的，与ArrayList一样，所以在优先阻塞 队列上put时是不会受阻的。虽然此队列逻辑上是无界的，但是由于资源被耗尽，所以试图执行添加操作可能会导致 OutOfMemoryError），但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。另外，往入该队列中的元 素要具有比较能力。

**DelayQueue**（基于PriorityQueue来实现的）是一个存放Delayed 元素的无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

### ArrayBlockingQueue源码学习 ###

**API定义**

由**数组**支持的**有界**阻塞队列。此队列对元素进行 FIFO（先进先出）排序。队列的头部是在队列中时间最长的元素。队列的尾部是在队列中时间最短的元素。新元素被插入到队列的尾部，队列检索操作获取队列头部的元素。  
这是一个经典的“有界缓冲区”，其中一个固定大小的数组保存由生产者插入并由消费者提取的元素。一旦创建，容量将无法更改。尝试put元素放入完整队列将导致操作阻塞；尝试从空队列中take元素同样会阻塞。  
此类支持对等待的生产者和消费者线程进行排序的可选公平策略。默认情况下，不保证此排序。但是，公平性设置为true的队列以 FIFO 顺序授予线程访问权限。公平性通常会降低吞吐量，但会降低可变性并避免饥饿。  
此类及其迭代器实现了Collection和Iterator接口的所有可选方法

public static void main(String[] args) throws InterruptedException {
        
            ArrayBlockingQueue<Integer> arrayBlockingQueue = new ArrayBlockingQueue<Integer>(10);
            for (int i = 0; i < 10; i++) {
        
                arrayBlockingQueue.put(i);
            }
            arrayBlockingQueue.stream().forEach(m -> System.out.println(m));
        }

结果【0~9】

可以看出默认是采用FIFO机制

**构造函数**

/**   
        *创建具有给定（固定）容量和默认访问策略的ArrayBlockingQueue 。
        *参数：
        *容量——这个队列的容量
        */
       public ArrayBlockingQueue(int capacity) {
        
            this(capacity, false);
        } 
         /**
         创建具有给定（固定）容量和指定访问策略的ArrayBlockingQueue 。
         参数：
         容量——这个队列的容量
         fair – 表示该队列中的可重入锁是否公平，默认为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();
        }**

**成员变量**

final Object[] items;//队列
    
    
    /** 下次出队下标（take、poll、remove） */
    int takeIndex;
    
    /** 下次入队下标（pull、offer、add） */
    int putIndex;
    
    /** 队列中元素个数 */
    int count;
    
    
    
    /** 锁 */
    final ReentrantLock lock;
    
    /** 等待条件（出队） */
    private final Condition notEmpty;
    
    /** 等待条件（入队） */
    private final Condition notFull;
    
    /**
     * 迭代器
     */
    transient Itrs itrs = null;

**put()方法**

可以看到在添加元素的时候使用变量notFull.await()判断列队是否满了一直阻塞，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();
            }
        }

ArrayBlockingQueue 实现并发同步的原理就是，读操作和写操作都需要获取到 AQS 独占锁才能进行操作。如果队列为空，这个时候读操作的线程进入到**读线程队列**排队，等待写线程写入新的元素，然后唤醒读线程队列的第一个等待线程。如果队列已满，这个时候写操作的线程进入到**写线程队列**排队，等待读线程将队列元素移除腾出空间，然后唤醒写线程队列的第一个等待线程。

对于 ArrayBlockingQueue，我们可以在构造的时候指定以下三个参数：

1.  队列容量，其限制了队列中最多允许的元素个数；
2.  指定独占锁是公平锁还是非公平锁。非公平锁的吞吐量比较高，公平锁可以保证每次都是等待最久的线程获取到锁；
3.  可以指定用一个集合来初始化，将此集合中的元素在构造方法期间就先添加到队列中。

[https_p3juejinbyteimgcom_toscnik3u1fbpfcp_f54994efac0d43de9c8a93f0b8ef9f5atplvk3u1fbpfcpzoomincropmark1304000awebp]: https://img-blog.csdnimg.cn/img_convert/b047b3295b9603be298806e74103eabb.webp?x-oss-process=image/format,png
[https_images2017cnblogscom_blog_1182892_201711_118289220171122100317930842768608png]: https://img-blog.csdnimg.cn/img_convert/3c7f0da4ef551f71f15827155082e5e7.png