文档章节

数据结构——队列——优先级队列

清风傲剑
 清风傲剑
发布于 2014/09/21 11:27
字数 546
阅读 12
收藏 0
package jxau.lyx.pQueue;
/**
 * 
 * @author liyixiang
 * @2014-9-21
 * @DataStrutureType: 队列——优先级队列
 * @TODO:
 * 		优先级队列
 * 		在优先级队列中,数据按关键字的值有序,这样关键字最小的数据项(或者最大)
 * 总是在队头
 * 		本以为会有一个数据项来表示优先级的大小,其实不用,insert到队列中时,就已经
 * 比较后排序!
 * 		优先级队列不需要front rear 因为front总是nItems-1,rear==0
 */
public class PriorityQueue {

	private int maxSize;                      //队列最大空间
	private long[] queueArray;                //队列空间(此处我们申请的是可比较的整数型数组)
	private int nItems;                        //队中含有的元素个数
	
	/**
	 * 初始化
	 * @param s:队空间大小
	 */
	public PriorityQueue(int s){
		maxSize = s;
		queueArray = new long[maxSize];
		nItems = 0;
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-20
	 *@param:obj 入队元素
	 *@return:void
	 *@TODO:
	 *		入队:
	 *		先检查队列是否有数据项,如果没有,就插入到下标为0的单元中,否则,从数组
	 *顶部开始上移存在的数据项,直到找到新数据项应当插入的位置,然后,插入数据项,
	 *并把nItems+1,优先级队列可能出现队满情况,应当在insert之前判断isFull
	 *
	 */
	public void insert(long item){
		int j;
		
		if(nItems == 0){
			queueArray[nItems++] = item;
		}else {
			//比较元素大小,使队列中的元素有序
			for(j=nItems-1;j>=0;j--){
				
				if(item > queueArray[j]){
					queueArray[j+1] = queueArray[j];
				}else {
					break;
				}
			}
			
			queueArray[j+1] = item;
			nItems++;
		}
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:Object:移除元素
	 *@TODO:
	 *		出队
	 *		由于优先级队列,元素有序,所以只有最大或者最小元素出队
	 */
	public long remove(){
		return queueArray[--nItems];	                                                                                                                                   
	}
						
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:Object
	 *@TODO:
	 *		获取优先级最小元素
	 */
	public Object peekMin(){
		 return queueArray[nItems-1];
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:boolean
	 *@TODO:
	 *		判断队列是否为空
	 */
	public boolean isEmpty(){
		return (nItems == 0);
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:boolean
	 *@TODO:
	 *		判断队列是否为满
	 *
	 */
	public boolean isFull(){
		return nItems == maxSize;
	}
	
	/**
	 * 
	 *@liyixiang
	 *@2014-9-21
	 *@param
	 *@return:int
	 *@TODO:
	 *		获取当前队列元素个数
	 */
	public int size(){
		return nItems;
	}
}


© 著作权归作者所有

清风傲剑
粉丝 33
博文 75
码字总数 40365
作品 0
蚌埠
高级程序员
私信 提问
每周一练 之 数据结构与算法(Queue)

这是第二周的练习题,这里补充下咯,五一节马上就要到了,自己的计划先安排上了,开发一个有趣的玩意儿。 下面是之前分享的链接: 1.每周一练 之 数据结构与算法(Stack) 2.每周一练 之 数据...

pingan8787
04/27
0
0
STL系列之五 priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素...

长平狐
2012/12/10
60
0
【死磕Java并发】-----J.U.C之阻塞队列:BlockingQueue总结

原文出处http://cmsblogs.com/ 『chenssy』 经过前面六篇博客的阐述,我想各位应该对阻塞队列BlockingQueue有了较为深入的理解,下面来一个总结,先看整个类图: BlockingQueue BlockingQueu...

chenssy
2017/10/04
0
0
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89
2015/10/24
250
0
STL系列之五 priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素...

彭博
2012/04/12
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Guava RateLimiter + AOP注解实现单机限流、统计QPS

1、基于springboot项目pom.xml添加如下依赖: <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-aop</artifactId></dependency><d......

铁骨铮铮
45分钟前
3
0
龙芯版办公软件下载

金山wps office   rpm包:http://ftp.loongnix.org/os/loongnix/1.0/os/Packages/w/wps-office-10.8.0.6472-1.a20p1.mips64el.rpm   deb包:http://packages.deepin.com/loongson/pool/......

gugudu
51分钟前
3
0
BI报表分析和数据可视化,推荐这三个开源工具!

开源篇 一、Superset 1、技术架构:Python + Flask + React + Redux + SQLAlchemy 2、使用人群: (1)开发/分析人员做好看板,业务人员浏览看板数据 (2)业务人员可自行编辑图表,查看满足...

飓风2000
57分钟前
3
0
CountDownLatch

CountDownLatch的概念 CountDownLatch是一个同步工具类,用来协调多个线程之间的同步,或者说起到线程之间的通信(而不是用作互斥的作用)。 CountDownLatch能够使一个线程在等待另外一些线程...

少年已不再年少
今天
2
0
centos7 新手阿里云服务器安装mongodb

简介 MongoDB 是一个基于分布式 文件存储的NoSQL数据库 由C++语言编写,运行稳定,性能高 旨在为 WEB 应用提供可扩展的高性能数据存储解决方案 MongoDB特点 模式自由 :可以把不同结构的文档存...

醉雨
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部