Java数据结构-delayQueue-优先队列--信号量

原编辑链接：
https://www.yuque.com/zhaozhaozhaozhao-khkij/lp7g2t/blwysxg3ygb00dw6?singleDoc# 《3delayqueue》

Queue问题

• 单端队列和双端队列，分别对应的实现类是哪个？
  ○ Java中的单项队列queue是用链表实现的 ， Queue本身是一个接口，继承了Collection集合 ；
  ○ 双端队列（Deque）继承了单向队列（Queue），也继承了其中所有的抽象方法，所以也包括基本队列的增删查方法。实现类：LinkedList、ArrayDeque、ConcurrentLinkedDeque、LinkedBlockingDeque ；
  

• 简述　延迟队列/优先队列　的实现方式 ？
  ○ 延迟队列实现：
  ○

○ 优先队列实现：
○

○ 也就是这个图：
其中delayed接口有两个方法需要重写，就是图中的获取延迟和比较

• 二叉堆插入/弹出元素的过程 ？
  ○ 这个比较熟悉优先队列的二叉堆是一个小根堆：插入是自下向上的堆化，在队尾加入一个元素，然后不断向上找父节点，判断要是比父节点小就继续向上判断，否则就会停止找到自己的位置；删除是自上向下的堆化，pop出去根节点，然后把最后一个元素作为比较的ｋｅｙ来自根节点向下找小数换到父节点，直到最后一个元素作为ｋｅｙ找到自己的位置。

• 延迟队列的使用场景？
  ○ 半小时未支付自动取消订单
  ○ 预定会议半小时前通知成员
  ○ 下单后消息提醒等等

• 延迟队列为什么添加信号量？
  ○ 处理延迟任务时候，可能会有多个线程同时访问延迟队列就可能造成并发问题，为解决并发问题保证线程的安全性使用信号量来进行控制。这里的１代表只能允许一个线程同时访问队列。

Semaphore semaphore = new Semaphore(int permits 1, boolean fair);
// 构造方法
// public Semaphore(int permits) {
//     sync = new NonfairSync(permits);
// }

○ queue队列-基础数据结构-一种逻辑上的一端进一端出的结构，可以使用数组或者链表实现，逻辑上没有容量局限，可以无限入队出队。可以分为单端队列、双端队列；

1 java延迟队列说明–主要是这个好像用在消息机制中。好重要

应用场景电商平台会更多，对于数据量大实时性高的用延迟队列：
■ 半小时未支付自动取消订单
■ 预定会议半小时前通知成员
■ 下单后消息提醒等等

1. JDK提供的API，位于java.util.concurrent包下；
2. DelayQueue 是一个 BlockingQueue（无界阻塞）队列，它封装了一个使用完全二叉堆排序元素的 PriorityQueue（优先队列–二叉堆树结构）。
3. 在添加元素时给元素一个 Delay（延迟时间）作为排序条件，队列中最小的元素会优先放到队首，元素到了delay时间才允许被取出；
4. 队列中可以放基本数据类型或自定义实体类，在存放基本数据类型时，优先队列中元素默认升序排列，自定义实体类就需要根据类属性值比较计算了 。

2 delayQueue实现

1. 延迟队列的实现，主要为在优先队列的基础上，添加可重入锁 ReentrantLock 对阻塞队列的实现。当数据存放时，按照二叉堆结构排序元素，出队时依照排序结构进行迁移。
2. DelayQueue 的 put 方法是线程安全的，因为 put 方法内部使用了ReentrantLock进行线程同步。DelayQueue 还提供了两种出队的方法 poll() 和 take()。poll() 为非阻塞获取，没有到期的元素直接返回 null；take() 为阻塞方式获取，没有到期的元素线程将会等待。
   代码实现举例：

public class Order implements Delayed {
    //延迟时间
    @JsonFormat(locale = "zh", timezone = "GMT+8", pattern = "yyyy-MM-dd HH:mm:ss")
    private long time;
    String name;

    public Order(String name, long time, TimeUnit unit) {
        this.name = name;
        this.time = System.currentTimeMillis() + (time > 0 ? unit.toMillis(time) : 0);
    } 
    //初始化给缓存时间了，就会设定时间time，后面执行会使用，比较或判断到不到时间

    @Override
    public long getDelay(TimeUnit unit) {
        return time - System.currentTimeMillis();
    }
    @Override
    public int compareTo(Delayed o) {
        Order Order = (Order) o;
        long diff = this.time - Order.time;
        if (diff <= 0) {
            return -1;
        } else {
            return 1;
        }
    }
}

// 　ｔｅｓｔ
public static void main(String[] args) throws InterruptedException {
    Order Order1 = new Order("Order1", 5, TimeUnit.SECONDS);
    Order Order2 = new Order("Order2", 10, TimeUnit.SECONDS);
    Order Order3 = new Order("Order3", 15, TimeUnit.SECONDS);
    DelayQueue<Order> delayQueue = new DelayQueue<>();
    delayQueue.put(Order1);
    delayQueue.put(Order2);
    delayQueue.put(Order3);

    System.out.println("订单延迟队列开始时间:" + LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
    while (delayQueue.size() != 0) {
        //取队列头部元素是否过期
        Order task = delayQueue.poll();
        if (task != null) {
            System.out.format("订单:{%s}被取消, 取消时间:{%s}\n", task.name, LocalDateTime.now().format(DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss")));
        }
        Thread.sleep(1000);
    }
}
// 执行结果：Order1、Order2、Order3 分别在 5秒、10秒、15秒后被执行，

３操作实现

３.１ 入队实现

入队一个元素会先直接插在队尾，然后执行优先队列的算法， 最终会调用到优先队列的 PriorityQueue　#　siftUpComparable 方法，就是小根堆的调整过程。
二叉堆：

３.２ 出队实现

• 出队直接弹出root节点，然后再次进行调整，但是这次不是自下向上调整，而是自上向下进行调整，寻找最小元素放到头顶；也是调用优先队列的　ｓｉｆｔＤｏｗｎＣｏｍｐａｒａｂｌｅ
• 调用参数是根节点下标０　最后一个元素作为比较的关键字ｋｅｙ，队列数组，和最后一个元素的下标

private static <T> void siftDownComparable(int k, T x, Object[] es, int n) 

• 实质是先把最后一个元素先放到根节点位置，然后不断下移，最小的元素不断上移，完成从上往下的堆化。

逻辑右移就是不考虑符号位，右移一位，左边补零即可。 算术右移需要考虑符号位，右移一位，若符号位为1，就在左边补1,；否则，就补0。
所以算术右移也可以进行有符号位的除法，右移,n位就等于除2的n次方。 例如，8位二进制数11001101分别右移一位。
逻辑右移就是[0]1100110　逻辑右移无脑补０ ．
算术右移就是[1]1100110　算数右移补充的是原数据的符号位。

找左右孩子，找小的那个，最小的那个和父节点交换；再在最小那个孩子的位置作为父继续往下找，不断堆化，直到孩子都不比这个ｋｅｙ小才停止。同时size–，最后一个已经加入到堆里面，将其置为空。

３.３ 操作加锁

延迟队列关于元素的操作都会加锁处理。
offer：入队元素

public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
    q.offer(e);
    if (q.peek() == e) {
        available.signal();
    }
    return true;
} finally {
    lock.unlock();
}
}

poll：出队
public E poll() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        E first = q.peek();
        if (first == null || first.getDelay(NANOSECONDS) > 0) {
            return null;
        } else {
            return q.poll();
        }
    } finally {
        lock.unlock();
    }
}

出入队都保证线程安全。