文档章节

Java PriorityQueue && PriorityBlockingQueue

秋风醉了
 秋风醉了
发布于 2015/01/12 17:26
字数 945
阅读 150
收藏 1

Java PriorityQueue && PriorityBlockingQueue

我们知道队列是遵循先进先出(First-In-First-Out)模式的,但有些时候需要在队列中基于优先级处理对象。举个例子,比方说我们有一个每日交易时段生成股票报告的应用程序,需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时,实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下,Java的PriorityQueue(优先队列)会很有帮助。

PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个无界队列,这个优先队列中的元素可以默认自然排序或者通过提供的Comparator(比较器)在队列实例化的时排序。

优先队列不允许空值,而且不支持non-comparable(不可比较)的对象,比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序,并且在排序时会按照优先级处理其中的元素。

优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序,那么就可能随机地取其中任意一个。当我们获取队列时,返回队列的头对象。

优先队列的大小是不受限制的,但在创建时可以指定初始大小。当我们向优先队列增加元素的时候,队列大小会自动增加。

PriorityQueue是非线程安全的,所以Java提供了PriorityBlockingQueue(实现BlockingQueue接口)用于Java多线程环境。

我们有一个用户类Customer,它没有提供任何类型的排序。当我们用它建立优先队列时,应该为其提供一个比较器对象。

Customer.java

package com.journaldev.collections;
 
public class Customer {
 
    private int id;
    private String name;
 
    public Customer(int i, String n){
        this.id=i;
        this.name=n;
    }
 
    public int getId() {
        return id;
    }
 
    public String getName() {
        return name;
    }
 
}

我们使用Java随机数生成随机用户对象。对于自然排序,我们使用Integer对象,这也是一个封装过的Java对象。下面是最终的测试代码,展示如何使用PriorityQueue:

PriorityQueueExample.java

package com.journaldev.collections;
 
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
 
public class PriorityQueueExample {
 
    public static void main(String[] args) {
 
        //优先队列自然排序示例
        Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
        Random rand = new Random();
        for(int i=0;i<7;i++){
            integerPriorityQueue.add(new Integer(rand.nextInt(100)));
        }
        for(int i=0;i<7;i++){
            Integer in = integerPriorityQueue.poll();
            System.out.println("Processing Integer:"+in);
        }
 
        //优先队列使用示例
        Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
        addDataToQueue(customerPriorityQueue);
 
        pollDataFromQueue(customerPriorityQueue);
 
    }
 
    //匿名Comparator实现
    public static Comparator<Customer> idComparator = new Comparator<Customer>(){
 
        @Override
        public int compare(Customer c1, Customer c2) {
            return (int) (c1.getId() - c2.getId());
        }
    };
 
    //用于往队列增加数据的通用方法
    private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
        Random rand = new Random();
        for(int i=0; i<7; i++){
            int id = rand.nextInt(100);
            customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
        }
    }
 
    //用于从队列取数据的通用方法
    private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
        while(true){
            Customer cust = customerPriorityQueue.poll();
            if(cust == null) break;
            System.out.println("Processing Customer with ID="+cust.getId());
        }
    }
 
}

 

注意我用实现了Comparator接口的Java匿名类,并且实现了基于id的比较器。

当我运行以上测试程序时,我得到以下输出:

Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96

 

从输出结果可以清楚的看到,最小的元素在队列的头部因而最先被取出。如果不实现Comparator,在建立customerPriorityQueue时会抛出ClassCastException。

Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
    at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
    at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
    at java.util.PriorityQueue.offer(PriorityQueue.java:329)
    at java.util.PriorityQueue.add(PriorityQueue.java:306)
    at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
    at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)

==========END==========

本文转载自:http://www.importnew.com/6932.html

共有 人打赏支持
秋风醉了
粉丝 244
博文 556
码字总数 414003
作品 0
朝阳
程序员
私信 提问
【死磕Java并发】—–J.U.C之阻塞队列:DelayQueue

原文出处http://cmsblogs.com/ 『chenssy』 DelayQueue是一个支持延时获取元素的无界阻塞队列。里面的元素全部都是“可延期”的元素,列头的元素是最先“到期”的元素,如果队列里面没有元素...

chenssy
2017/08/18
0
0
Java 优先队列 PriorityQueue PriorityBlockingQueue 源码分析

基本使用 输出 PriorityQueue 成员变量 通过数组实现一个堆,元素在queue数组中并不是完全有序的,仅堆顶元素最大或最小。 基本方法 以poll方法为例,实际上是获取堆顶元素,然后调整堆。 调...

被称为L的男人
01/04
0
0
基于堆实现的优先级队列:PriorityQueue 解决 Top K 问题

1、认识 PriorityQueue PriorityQueue是从JDK1.5开始提供的新的数据结构接口,它是一种基于优先级堆的极大优先级队列。优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具...

大数据之路
2013/06/02
0
0
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin
2018/05/25
0
0
Android ThreadLocal+PriorityQueue构建多线程队列

一、消息队列 Android中使用了很多消息队列,如Intent,Handler,BroadcastReceiver等。使用消息队列的目的是防止线程阻塞并且将不能及时执行的任务缓存起来,从而提高系统的运行效率。 为了使...

IamOkay
2014/11/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

深入理解Spring MVC 思想

目录 一、前言 二、spring mvc 核心类与接口 三、spring mvc 核心流程图 四、spring mvc DispatcherServlet说明 五、spring mvc 父子上下文的说明 六、springMVC-mvc.xml 配置文件片段讲解 ...

呵呵哒灬
14分钟前
0
0
数据库技术-Mysql主从复制与数据备份

数据库技术-Mysql 主从复制的原理: MySQL中数据复制的基础是二进制日志文件(binary log file)。一台MySQL数据库一旦启用二进制日志后,其作为master,它的数据库中所有操作都会以“事件”...

须臾之余
昨天
12
0
Git远程仓库——GitHub的使用(一)

Git远程仓库——GitHub的使用(一) 一 、 Git远程仓库 由于你的本地仓库和GitHub仓库之间的传输是通过SSH加密的,所以需要一下设置: 步骤一、 创建SSH key 在用户主目录下,看看有没有.ss...

lwenhao
昨天
2
0
SpringBoot 整合

springBoot 整合模板引擎 SpringBoot 整合Mybatis SpringBoot 整合redis SpringBoot 整合定时任务 SpringBoot 整合拦截器...

细节探索者
昨天
1
0
第二个JAVA应用

第二个JAVA应用 方法一:配置文件: # cd /usr/local/tomcat/conf/# vim server.xml</Host> <Host name="www.wangzb.cc" appBase="/data/wwwroot/www.wangzb.cc" //引用所......

wzb88
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部