java库里的PriorityQueue无法满足我,它不能固定容量,不遍历(遍历后就无序了),它的排序因字是从小到大(虽然可以用Comparator来反转大小顺序)。我所要的是可以固定容量(在一大堆数据通信中选择最大或最小的几个数时很有用),可遍历(不是一个个poll())。
于是,在有空的时间里写了一下。内容是一个双向链表(带头的,头不作保存数据),用插入排序。个人认为一个个添加的用插入排序效果比较好。从队尾到队头找合适的插入位置,是稳定的排序。
添加的实体可以用Comparator或Comparable,如果这两个都不是,就失去排序的效果。实现了比较高兴,发表下。
package net.blogjava.chenlb.util;
import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.Iterator;
/**
* @param <E>
* 容量capacity大于0,最多只能添加capacity个,多出的被删除掉.<br/>
* 删除时根据{@link Comparable}或{@link Comparator} 和 desc
* 如果comparator==null时使用Comparable<br/>
* non-thread safe
* @author chenlb 2008-4-23 下午11:31:06
*/
public class TopPriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {
private static final long serialVersionUID = 1L;
private int size;
private LinkedItem head;
private LinkedItem last;
private int top; //top>0后,容量有限制
private Comparator<? super E> comparator;
private boolean desc; //降序
/**
* 容量无限制,升序.
*/
public TopPriorityQueue() {
this(0, null, false);
}
/**
* 容量无限制,
* @param desc true为降序.
*/
public TopPriorityQueue(boolean desc) {
this(0, null, desc);
}
/**
* 容量无限制,升序,用comparator排序
*/
public TopPriorityQueue(Comparator<? super E> comparator) {
this(0, comparator, false);
}
/**
* 容量无限制,用comparator排序
* @param desc true为降序
*/
public TopPriorityQueue(Comparator<? super E> comparator, boolean desc) {
this(0, comparator, desc);
}
/**
* 容量限制为capacity.超出容量限制的,会删除优先级最小(队尾).
*/
public TopPriorityQueue(int capacity) {
this(capacity, null, false);
}
public TopPriorityQueue(int capacity, boolean desc) {
this(capacity, null, desc);
}
public TopPriorityQueue(int capacity, Comparator<? super E> comparator) {
this(capacity, comparator, false);
}
public TopPriorityQueue(int capacity, Comparator<? super E> comparator, boolean desc) {
head = new LinkedItem();
last = head;
top = capacity;
this.comparator = comparator;
this.desc = desc;
}
@Override
public Iterator<E> iterator() {
// TODO 迭代器
return new It(head);
}
@Override
public int size() {
return size;
}
public boolean offer(E o) {
// TODO 添加到适当的位置
if(o == null) {
throw new IllegalArgumentException("不能添加值为null的!");
}
LinkedItem temp = new LinkedItem(o);
/*last.next = temp;
temp.prev = last;*/
if(last == head) { //第一个
last.next = temp;
temp.prev = last;
last = temp;
} else {
LinkedItem tempPrev = last;
if(comparator != null) {
while(tempPrev!=null && tempPrev != head) {
int r = comparator.compare(tempPrev.data, temp.data);
if(desc) {
r = 0 - r;
}
if(r == 1) { //tempPrev > temp
//重置,继续向前找
tempPrev = tempPrev.prev;
} else { //找到插入的位置
break;
}
}
} else if(o instanceof Comparable) { //用Comparable
while(tempPrev!=null && tempPrev != head) {
Comparable<E> tPrev = (Comparable<E>) tempPrev.data;
int r = tPrev.compareTo(temp.data);
if(desc) {
r = 0 - r;
}
if(r == 1) { //tempPrev > temp
//重置,继续向前找
tempPrev = tempPrev.prev;
} else { //找到插入的位置
break;
}
}
}
if(tempPrev != null) { //插入
if(tempPrev == last) { //后面添加的
last = temp;
}
temp.next = tempPrev.next;
if(tempPrev.next != null) {
tempPrev.next.prev = temp;
}
tempPrev.next = temp;
temp.prev = tempPrev;
}
}
size++;
if(top > 0 && size > top) { //去掉优先级最小的
tail();
}
return true;
}
/**
* 从栈底去除
*/
public E tail() {
if(last == head) {
return null;
}
LinkedItem laster = last;
last = last.prev;
last.next = null;
laster.prev = null;
size--;
return laster.data;
}
public E peek() {
// TODO 取得栈顶值
LinkedItem first = head.next;
if(first != null) {
return first.data;
}
return null;
}
public E poll() {
// TODO 从栈顶去除
LinkedItem first = head.next;
if(first != null) {
head.next = first.next;
if(first.next != null) {
first.next.prev = head;
}
size--;
return first.data;
}
return null;
}
private class It implements Iterator<E> {
LinkedItem curr;
public It(LinkedItem curr) {
super();
this.curr = curr;
}
public boolean hasNext() {
if(curr != null && curr.next != null) {
return true;
}
return false;
}
public E next() {
curr = curr.next;
E d = curr.data;
return d;
}
public void remove() {
curr.prev.next = curr.next;
if(curr.next != null) {
curr.next.prev = curr.prev;
}
size--;
}
}
/**
* @param <E>
* 链结点.
* @author chenlb 2008-5-4 下午04:48:17
*/
private class LinkedItem {
LinkedItem prev;
E data;
LinkedItem next;
public LinkedItem() {
}
public LinkedItem(E o) {
this.data = o;
}
}
}
|
sleep和wait有什么区别 收藏
第一种解释:
功能差不多,都用来进行线程控制,他们最大本质的区别是:sleep()不释放同步锁,wait()释放同步缩.
还有用法的上的不同是:sleep(milliseconds)可以用时间指定来使他自动醒过来,如果时间不到你只能调用interreput()来强行打断;wait()可以用notify()直接唤起.
第二种解释:
sleep是Thread类的静态方法。sleep的作用是让线程休眠制定的时间,在时间到达时恢复,也就是说sleep将在接到时间到达事件事恢复线程执行,例如:
try{
System.out.println("I'm going to bed");
Thread.sleep(1000);
System.out.println("I wake up");
}
catch(IntrruptedException e) {
}
wait是Object的方法,也就是说可以对任意一个对象调用wait方法,调用wait方法将会将调用者的线程挂起,直到其他线程调用同一个对象的notify方法才会重新激活调用者,例如:
//Thread 1
try{
obj.wait();//suspend thread until obj.notify() is called
}
catch(InterrputedException e) {
}
第三种解释:
这两者的施加者是有本质区别的.
sleep()是让某个线程暂停运行一段时间,其控制范围是由当前线程决定,也就是说,在线程里面决定.好比如说,我要做的事情是 "点火->烧水->煮面",而当我点完火之后我不立即烧水,我要休息一段时间再烧.对于运行的主动权是由我的流程来控制.
而wait(),首先,这是由某个确定的对象来调用的,将这个对象理解成一个传话的人,当这个人在某个线程里面说"暂停!",也是 thisOBJ.wait(),这里的暂停是阻塞,还是"点火->烧水->煮饭",thisOBJ就好比一个监督我的人站在我旁边,本来该线 程应该执行1后执行2,再执行3,而在2处被那个对象喊暂停,那么我就会一直等在这里而不执行3,但正个流程并没有结束,我一直想去煮饭,但还没被允许, 直到那个对象在某个地方说"通知暂停的线程启动!",也就是thisOBJ.notify()的时候,那么我就可以煮饭了,这个被暂停的线程就会从暂停处 继续执行.
其实两者都可以让线程暂停一段时间,但是本质的区别是一个线程的运行状态控制,一个是线程之间的通讯的问题
在java.lang.Thread类中,提供了sleep(),
而java.lang.Object类中提供了wait(), notify()和notifyAll()方法来操作线程
sleep()可以将一个线程睡眠,参数可以指定一个时间。
而wait()可以将一个线程挂起,直到超时或者该线程被唤醒。
wait有两种形式wait()和wait(milliseconds).
sleep和wait的区别有:
1,这两个方法来自不同的类分别是Thread和Object
2,最主要是sleep方法没有释放锁,而wait方法释放了锁,使得其他线程可以使用同步控制块或者方法。
3,wait,notify和notifyAll只能在同步控制方法或者同步控制块里面使用,而sleep可以在
任何地方使用
synchronized(x){
x.notify()
//或者wait()
}
4,sleep必须捕获异常,而wait,notify和notifyAll不需要捕获异常
|