常用队列

Rocky大约 7 分钟

Queue

继承自Collection接口.

共6个方法，分为三类：插入，移除，检测，每类方法有两个方法:

抛出异常返回特定值
插入add(e)offer(e)
移除removepoll
检测element()peek()

上面6个方法都是非阻塞方法

  • elment()方法：得到队列第一个元素，但不从队列中移除，如果没有元素，则抛出异常
  • peek()方法：得到队列第一个元素，但不从队列中移除，如果没有元素，则返回null

BlockingQueue

  • take() 和 put(e) 是BlockingQueue提供的两个阻塞方法（具体是否阻塞要看具体的实现类，有些实现类虽然可以指定容量，但这个容量是初始容量，也就是允许容量扩大，那么这种情况下put方法是不会阻塞，比如PriorityBlockingQuque，这个实现在执行put方法的时候就不会阻塞）
  • drainTo(Collection c) 将阻塞队列中可用的数据都转移到参数给定的集合中

ArrayBlockingQueue

  1. 基于指定长度的数组实现，不可扩容。维护了两个int型变量，分别执行队首和队尾下标，实现循环数组的效果
  2. 由于采用了一个锁，所以在入队操作和出队操作不能同时进行
  3. 可以指定采用的锁是否为公平锁，默认情况下为非公平锁

LinkedBlockingQueue

  1. 基于带头结点的单向链表实现，不过头结点的指向是变动的，不可扩容。
  2. 采用了两个锁（一个用于入队，一个用于出队），所以入队出队两个操作互不影响。两个锁都是非公平锁。
  3. 初始化时建议制定一个容量，否则是int的最大值。如果生产者速度比消费者快，可能会消耗大量内存。

PriorityBlockingQueue

  1. 物理上基于数组来实现，逻辑上采用的是堆存储结构，可扩容。put方法采用offer方法实现，所以put方法不会阻塞

  2. 排序算法采用的是堆排序，遍历这个队列并不能得到有序输出，只有依次执行出队操作才能得到有序输出。

  3. 使用一个锁来完成

System.out.println(priorityBlockingQueue.offer(4));
System.out.println(priorityBlockingQueue.offer(8));
System.out.println(priorityBlockingQueue.offer(1));

Iterator iterator = priorityBlockingQueue.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
//输出：1，8，4
System.out.println();
# 会发现并非按照1，4，8的顺序输出。但下面的就是就是按照 1，4，8的顺序输出

while (true) {
    try {
        System.out.println(priorityBlockingQueue.take());
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}
//输出：1，4，8
# 但这个队列会保证队列的第一个元素永远是当前优先级最高的元素
  1. 要求要么元素实现了Comparable接口，要么这个队列有一个Comparator实例

SynchronousQueue

  1. 是一个无缓冲的等待队列，手递手队列，生产入队的时候需要有线程等待消费出队，消费出队的时候必须有线程正要生产入队，否则线程阻塞。
  2. 有两种模式
    1. 公平模式 使用FIFO队列来阻塞多余的生产者和消费者，从而体系整体的公平策略
    2. 非公平模式 使用LIFO队列来管理多余的生产者和消费者，如果生产者和消费者的处理速度有差距，则很容易出现饥渴的情况，即可能有某些生产者或者是消费者的数据永远都得不到处理。

DelayQueue

  1. 消息入队后，只有队列成员的延迟时间到了，才能出队。无界队列

  2. 出队和入队使用一个锁来完成。

  3. 实现原理 使用优先级队列来存储消息，出队时检查延迟时间是否满足，满足则出队。否则阻塞当前线程。

  4. 哪些场景下会用到延迟队列？

    1. 定时任务调度，比如java里的Timer，ScheduledThreadPoolExecutor，这两个里都用到的延迟队列（这两个都自己实现了自己的延迟队列，并没有直接采用DelayQueue）

    2. 缓存系统的ttl，比如redis的ttl。（延迟从缓存中清除）

  5. 是否无界这个问题？ 我觉得没有必要去记忆，因为不同的具体实现可以有不同的容量，我甚至可以自己实现一个延迟队列，要求只运行存放100或1000个。所以我觉得用的时候去看下javadoc或者源码就可以了。

LinkedTransferQueue

LinkedBlockingDeque

  1. 数据结构采用的是双向链表
  2. 可以在队列两头进行入队或出队
  3. 使用了一个ReentrantLock实例来完成

ArrayBlockingQueue与LinkedBlockingQueue的区别？

  1. 使用的结构不一样
  2. 使用的锁数量不一样
  3. 两者对gc的影响有些不一样:前者不会额外创建对象，后者会额外创建node对象。所以如果频繁的入队和出队，后者会生成大量的Node对象。在这一点有所不同。

PriorityBlockingQueue和DelayQueue的区别？

  1. 在原理上两个都用到了优先级队列的思想，但在实现上，前者自己实现了优先级队列，后者组合了PriorityQueue来实现优先级队列的
  2. 前者的阻塞条件是如果队列为空阻塞，后者的阻塞条件除了队列为空阻塞外还有一个就是如果延迟时间未到也阻塞

SynchronousQueue和LinkedTransferQueue的区别？

TransferQueue

  1. 生产者生产消息的时候要求同时有消费者等待消费消息的一种队列。
  2. 继承了BlockingQueue，也是一种阻塞队列。
  3. 多加了几个方法的定义
    boolean tryTransfer(E e);
void transfer(E e) throws InterruptedException;
boolean tryTransfer(E e, long timeout, TimeUnit unit) throws InterruptedException;
boolean hasWaitingConsumer();
int getWaitingConsumerCount();

注意

  1. 在线程池中使用无界队列的话，maxPoolSize可以说没有用，消耗队列的线程个数应该只有corePoolSize

Dual Stack

Dual Queue

ScheduledThreadPoolExecutor

  1. 继承自ThreadPoolExecutor，实例化的时候，采用了自己内部实现的延迟队列，进而实现定时功能

  2. 从小到大排序

//从小到大：前者减后者

new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return o1.id - o2.id;
    }
}

//等同于下面的
private class Person implements Comparable<Person> {
    public int id;

    public Person(int id) {
        this.id = id;
    }

    @Override
    public int compareTo(Person o) {
        return id - o.id;
    }
}


//按照指定顺序排序
new Comparator<Person>() {
    @Override
    public int compare(Person o1, Person o2) {
        return sortIndex.indexOf(o1.id) - sortIndex.indexOf(o2.id);
    }
}
//等同于
private class Person implements Comparable<Person> {
    public int id;

    public Person(int id) {
        this.id = id;
    }

    @Override
    public int compareTo(Person o) {
        return sortIndex.indexOf(id) - sortIndex.indexOf(o.id);
    }
}
  1. 堆排序

系统推荐







  • 随机毒鸡汤：有朋自远方来，虽远必诛。