JDK自带优先队列

简介

我们知道队列是遵循先进先出（First-In-First-Out）模式的，但有些时候需要在队列中基于优先级处理对象。比方说银行的VIP,商场的VIP等等。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，Java的PriorityQueue(优先队列)会很有帮助。
PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境。
这篇文章主要使用了PriorityQueue与PriorityBlockingQueue;

PriorityQueue

测试代码如下

private static void priorityQueueTest() {
        Queue<Integer> qi = new PriorityQueue<Integer>();

        qi.add(5);
        qi.add(2);
        qi.add(1);
        qi.add(10);
        qi.add(3);

        while (!qi.isEmpty()) {
            System.out.print(qi.poll() + ",");
        }
        System.out.println();
        System.out.println("-----------------------------");
        // 自定义的比较器，默认是从小到大排序,我们可以自由定义比较的顺序 Comparator<Integer> cmp;
        Comparator cmp = new Comparator<Integer>() {
            public int compare(Integer e1, Integer e2) {
                return e2 - e1;
            }
        };
        Queue<Integer> q2 = new PriorityQueue<Integer>(5, cmp);
        q2.add(2);
        q2.add(8);
        q2.add(9);
        q2.add(1);
        while (!q2.isEmpty()) {
            System.out.print(q2.poll() + ",");
        }
    }

运行之后可以看到输出结果为
没上自定义构造器的是默认排序,上构造器的是从大到小

test1输出效果.png

实际使用场景

我们业务场景中需要用到的是根据订单的金额排序,如果订单金额相等,就用下单时间进行排序

首先我们定义一个实体类

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor // 这里是使用了lombok注释,不用写get/set方法,注解没特殊意思
public class MoniDto {

    private Long userId;

    private Double price;

    private Date date;
}

然后看业务代码

 private static void priorityQueueTest1() {
        Queue<MoniDto> q2 = new PriorityQueue<MoniDto>(new Comparator<MoniDto>() {
            @Override
            public int compare(MoniDto o1, MoniDto o2) {
                //比较价格相等就用日期排序
                if (o1.getPrice().equals(o2.getPrice())) {
                    return o2.getDate().compareTo(o1.getDate());
                }
               //按价格比较
                return (int) (o2.getPrice() - o1.getPrice());
            }
        });
        for (int i = 0; i < 1000; i++) {
            q2.add(new MoniDto(Long.valueOf(i), Double.valueOf(i), new Date()));
        }

        while (!q2.isEmpty()) {
            System.out.println(q2.poll());
        }
    }

查看输出结果,跟预期一样

test2输出结果

PriorityBlockingQueue

考虑到我们的业务场景肯定是多线程的,没看到PriorityBlockingQueue之前,我一直在想自己加锁怎么加,看到PriorityBlockingQueue我就豁然开朗了,内部使用数组实现，插入和获取数据使用同一把锁。不同的是，不管有无指定长度，都会实现可以实现自动扩容；在构造函数需传入comparator,用于插入元素时继续排序，若没有传入comparator，则插入的元素必须实现Comparatable接口。

我这边使用的是插入的实体类实现Comparable接口

@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class MoniDto implements Comparable<MoniDto> {

    private Long userId;

    private Double price;

    private Date date;

    @Override
    public int compareTo(MoniDto o) {
        if (o.getPrice().equals(this.getPrice())) {
            return o.getDate().compareTo(this.getDate());
        }
        return (int) (o.getPrice() - this.getPrice());
    }
}

模拟多线程进行测试

 private static void priorityBlockingQueueTest2(){
        final PriorityBlockingQueue q = new PriorityBlockingQueue();
        ExecutorService se = Executors.newCachedThreadPool();
        //producer
        se.execute(new Runnable() {
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    q.add(new MoniDto(Long.valueOf(i), Double.valueOf(i), new Date()));
                }
            }
        });

        //consumer
        se.execute(new Runnable() {
            public void run() {
                while (true) {
                    try {
                        System.out.println("take-- " + q.poll() + " left:-- [" + q.toString() + "]");
                        try {
                            TimeUnit.MILLISECONDS.sleep(r.nextInt(1000));
                        } catch (InterruptedException e) {
                            // TODO Auto-generated catch block
                            e.printStackTrace();
                        }
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                }
            }
        });
        try {
            TimeUnit.SECONDS.sleep(5);
        } catch (InterruptedException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        System.out.println("shutdown");
    }

代码跑起来之后输出的结果是:

test3输出结果.png