欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现--优先级队列

程序员文章站 2022-05-04 15:15:06
...

《Java数据结构和算法》-->像栈和队列一样,优先级队列也经常用作程序员的编程工具。

  很多情况下需要访问具有最小关键字的项或者是最大关键字的项,,具有最高或最小的关键字具有最高的优先级。我们就可以采用优先级队列。这里使用的是简单的数组来实现优先级队列,这种实现方法插入比较慢,但是它比较简单,适用于数据量比较小的并且不是特别在意插入速度的情况。有一种比数组要快的,就是使用堆来建立优先级队列。这篇博文说的是按关键字小的有较高的优先级。

这优先级队列没有上一篇博文(循环队列)中的front、rear,我们在构造这个优先级队列的时候已经把他们排序好了。我们remove的时候永远都是从上层把最小关键字的元素丢出去,队尾,只要这个优先级队列不为空,就一直指向QueueArray[0]。

思考Inesrt方法的时候,可以结合下图来思考:

Java实现--优先级队列

Java实现--优先级队列

 

Java实现--优先级队列

  因为优先级队列除了Insert,其它的都相对比较简单,在这里其它的就不多解释,对于Insert有详细的注解

/**
 * 自定义优先级队列
 * @author Administrator
 *
 */
public class PriorityQ {
	private int maxSize;
	private long[] QueueArray;
	private int nItems;
	
	public PriorityQ(int maxSize) {
		this.maxSize = maxSize;
		QueueArray = new long[maxSize];
		nItems = 0;
	}
	
	public void insert(int temp) {
		if(!isFull()) {
			int j;
			//如果nItems里面是空的话,那么就将temp直接赋值给QueueArray[nItems],并将nItems自增		
			if(nItems==0) {
				QueueArray[nItems++] = temp;
			}else{
				//从第二个开始,跟数组中已有的元素比较,若是比temp小的数,就将这个数往后移,
				//这种操作一直持续到找到比temp大的元素,即break,如果没有比temp大的就将其放在第一个位置即QueueArray[0]
				for(j=nItems-1;j>=0;j--) {
					if(temp>QueueArray[j]) {
						QueueArray[j+1] = QueueArray[j];
					}else {
						break;
					}
				}
				QueueArray[j+1] = temp;
				//nItems自增
				nItems++;
			}
		}else {
			//若优先级队列是满的则抛出异常
			try {
				throw new Exception("The Queue is full!");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
	}
	
	public String remove() {
		if(!isEmpty()) {
			return ("Remove successful! The number is:"+QueueArray[--nItems]); 
		}else {
			return ("Sorry!The queue is Empty!");
		}
	} 
	
	public String peekMin() {
		if(!isEmpty()) {
			return ("Peekmin successful! The Minnumber is:"+QueueArray[nItems-1]); 
		}else {
			return ("Sorry!The queue is Empty!");
		}	
	}
	
	public boolean isEmpty() {
		return (nItems==0);
	}
	
	public boolean isFull() {
		return (nItems==maxSize-1);
	}
	
	public int size() {
		return nItems;
	}
}

 

/**
 * 测试优先级队列
 * @author Administrator
 *
 */
public class TestPriorityQ {
	public static void main(String[] args) {
		PriorityQ q = new PriorityQ(10);
		System.out.println(q.isEmpty());
		q.insert(10);
		q.insert(50);
		q.insert(30);
		q.insert(40);
		q.insert(60);
		q.insert(80);
		q.insert(100);
		q.insert(120);
		q.insert(110);
		
		System.out.println(q.isFull());
		System.out.println(q.peekMin());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.remove());
		System.out.println(q.peekMin());
		
	}
}
结果显示:
true
true
Peekmin successful! The Minnumber is:10
Remove successful! The number is:10
Remove successful! The number is:30
Remove successful! The number is:40
Peekmin successful! The Minnumber is:50

优先级队列的插入操作需要为O(N)的时间,而删除操作只要O(1),我们后面会用堆来改进插入操作的时间。

相关标签: FQueue