数据类型之队列的自我总结

Queue

Queue：基本上，一个队列就是一个先入先出（FIFO）的数据结构
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Deque接口，因此我们可以把LinkedList当成Queue来用。
队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。

Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。
Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。
除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。

双端队列Deque：

概述
一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。
特点

1. Deque是一个Queue的子接口，是一个双端队列，支持在两端插入和移除元素
2. deque支持索引值直接存取。
3. Deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。
4. 插入、删除、获取操作支持两种形式：快速失败和返回null或true/false
5. 不推荐插入null元素，null作为特定返回值表示队列为空

双向队列操作
插入元素

• addFirst(): 向队头插入元素，如果元素为null，则发生空指针异常
• addLast(): 向队尾插入元素，如果为空，则发生空指针异常
• offerFirst(): 向队头插入元素，如果插入成功返回true，否则返回false
• offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false

移除元素

• removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
• removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException
• pollFirst(): 返回并移除队头元素，如果队列无元素，则返回null
• pollLast(): 返回并移除队尾元素，如果队列无元素，则返回null

获取元素

• getFirst(): 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException
• getLast(): 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException
• peekFirst(): 获取队头元素但不移除，如果队列无元素，则返回null
• peekLast(): 获取队尾元素但不移除，如果队列无元素，则返回null

栈操作

• pop():
  弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException
• push():
  向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NoSuchElementException，如果栈空间受到限制，则发生IllegalStateException

引用场景
满足FIFO场景时
满足LIFO场景时，曾经在解析XML按标签时使用过栈这种数据结构，但是却选择Stack类，如果在进行栈选型时，更推荐使用Deque类，应为Stack是线程同步

阻塞队列(应用于多线程场景)：

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列。这两个附加的操作支持阻塞的插入和移除方法

1. 支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。
2. 支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空

首先，我们来看看基于内存的队列。在Java的并发包中已经提供了BlockingQueue的实现，比较常用的有ArrayBlockingQueue和LinkedBlockingQueue，前者是以数组的形式存储，后者是以Node节点的链表形式存储。至于数组和链表的区别这里就不多说了。
BlockingQueue 队列常用的操作方法:

1. 往队列中添加元素: add(), put(), offer()
2. 从队列中取出或者删除元素: remove() element() peek() poll() take()

每个方法的说明如下：

• offer()方法往队列添加元素如果队列已满直接返回false,队列未满则直接插入并返回true;
• add()方法是对offer()方法的简单封装.如果队列已满,抛出异常new IllegalStateException(“Queuefull”);
• put()方法往队列里插入元素,如果队列已经满,则会一直等待直到队列为空插入新元素,或者线程被中断抛出异常.
• remove()方法直接删除队头的元素:
• peek()方法直接取出队头的元素,并不删除.
• element()方法对peek方法进行简单封装,如果队头元素存在则取出并不删除,如果不存在抛出异常NoSuchElementException()
• poll()方法取出并删除队头的元素,当队列为空,返回null;
• take()方法取出并删除队头的元素,当队列为空,则会一直等待直到队列有新元素可以取出,或者线程被中断抛出异常
• offer()方法一般跟pool()方法相对应,
• put()方法一般跟take()方法相对应.日常开发过程中offer()与pool()方法用的相对比较频繁.

实例：

       Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for (String q : queue) {
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll=" + queue.poll()); //返回第一个元素，并在队列中删除
        for (String q : queue) {
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element=" + queue.element()); //返回第一个元素
        System.out.println("===");
        System.out.println("peek=" + queue.peek()); //返回第一个元素

输出结果为：

JDK 7 提供了7个阻塞队列，如下

1. 1、ArrayBlockingQueue 数组结构组成的有界阻塞队列。
   此队列按照先进先出（FIFO）的原则对元素进行排序，但是默认情况下不保证线程公平的访问队列，即如果队列满了，那么被阻塞在外面的线程对队列访问的顺序是不能保证线程公平（即先阻塞，先插入）的。
2. LinkedBlockingQueue一个由链表结构组成的有界阻塞队列
   此队列按照先出先进的原则对元素进行排序
3. PriorityBlockingQueue 支持优先级的*阻塞队列
4. DelayQueue 支持延时获取元素的*阻塞队列，即可以指定多久才能从队列中获取当前元素
5. SynchronousQueue不存储元素的阻塞队列，每一个put必须等待一个take操作，否则不能继续添加元素。并且他支持公平访问队列。
6. LinkedTransferQueue由链表结构组成的*阻塞TransferQueue队列。相对于其他阻塞队列，多了tryTransfer和transfer方法
   transfer方法
   如果当前有消费者正在等待接收元素（take或者待时间限制的poll方法），transfer可以把生产者传入的元素立刻传给消费者。如果没有消费者等待接收元素，则将元素放在队列的tail节点，并等到该元素被消费者消费了才返回。
   tryTransfer方法
   用来试探生产者传入的元素能否直接传给消费者。，如果没有消费者在等待，则返回false。和上述方法的区别是该方法无论消费者是否接收，方法立即返回。而transfer方法是必须等到消费者消费了才返回。
7. LinkedBlockingDeque链表结构的双向阻塞队列，优势在于多线程入队时，减少一半的竞争。

非阻塞队列：

阻塞队列和非阻塞队列的区别：
阻塞队列可以阻塞，非阻塞队列不能阻塞，只能使用队列wait(),notify()进行队列消息传送。而阻塞队列当队列里面没有值时，会阻塞直到有值输入。输入也一样，当队列满的时候，会阻塞，直到队列不为空。

   public class ConcurrentLinkedQueue<E> extends AbstractQueue<E> implements Queue<E>, java.io.Serializable {
  private transient volatile Node<E> head;//头指针
  private transient volatile Node<E> tail;//尾指针
  public ConcurrentLinkedQueue() {//初始化，head=tail=（一个空的头结点）
    head = tail = new Node<E>(null);
  }
  private static class Node<E> {
  volatile E item;
  volatile Node<E> next;//内部是使用单向链表实现
  ......
  }
......
}

ConcurrentLinkedQueue是一个基于链接节点的*线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部；当我们获取一个元素时，它会返回队列头部的元素。

本文地址：https://blog.csdn.net/weixin_45371171/article/details/110230261