优先级队列学习及应用

在有些软件系统中，有时要求把进入队列中的数据元素分优先级，这样出队列时就不是把队头数据输出了，而是选择队列中优先级最高的数据元素出队列，当两个数据元素优先级相同时，仍然按照先进先出原则出队列。

只讨论顺序优先级队列，它与顺序循环队列的区别：（1）出队列方式，上段已经陈述。具体操作是先遍历队列找出优先级最高的取出，并把其后的所有元素依次向队头移位。因为存在移位，所以避免了假溢出问题，那么顺序优先级队列就不用设计为循环结构了。（2）加入队列的元素包括两部分，一个是数据本身，一个是优先级（常用int数值），所以要单独定义数据元素类。

元素类和队列类的代码如下：

package StackAndQueue; /** * @author sun * 创建时间：2017年4月4日下午2:37:11 */ /* * 设计顺序优先级队列要先定义数据元素类，该类包括数据值和对应优先级 * 我们约定数值越小优先级越高 * */ class Element{ private Object elem;//数据元素值 private int priority;//优先级 Element(Object obj,int i){//初始化 elem = obj; priority = i; } public Object getElem(){ return elem; } public void setElem(Object obj){ elem = obj; } public int getPriority(){ return priority; } public void setPriority(int i){ priority = i; } } //建立顺序优先级队列类 public class SeqPQueue implements Queue { static final int defaultSize = 10; int front; int rear; int count;//计数器 int maxSize; Element[] data;//存放数据元素对象 public SeqPQueue(){ initiate(10); } public SeqPQueue(int sz){ initiate(sz); } private void initiate(int sz){ maxSize = sz; front = rear = 0; count = 0; data = new Element[sz]; } public void append(Object obj)throws Exception{ if(count >= maxSize){ throw new Exception("队列已满！"); } data[rear] = (Element)obj; rear = rear+1; count++; } public Element delete()throws Exception{ if(count == 0){ throw new Exception("队列已空！"); } //寻找优先级最高的数据元素，且保存在临时变量min中 Element min = data[0]; int minIndex = 0; for(int i=0;i<count;i++){ if(data[i].getPriority()<min.getPriority()){ min = data[i]; minIndex = i; } } //将找到的当前最高优先级元素其后面的所有元素依次向队头移位 for(int i = minIndex+1;i<count;i++){ data[i-1] = data[i]; } rear = rear-1; count--; return min; } public Object getFront()throws Exception{ //其实该方法已经变成了获取优先级最大的元素 if(count >= maxSize){ throw new Exception("队列已满！"); } //寻找优先级最高的数据元素，且保存在临时变量min中 Element min = data[0]; int minIndex = 0; for(int i=0;i<count;i++){ if(data[i].getPriority()<min.getPriority()){ min = data[i]; minIndex = i; } } return min; } public boolean notEmpty(){ return count != 0; } } 操作系统中进程管理的简单模仿：

package StackAndQueue; /** * @author sun * 创建时间：2017年4月4日下午3:12:42 */ /*设计一个程序模仿操作系统的进程管理问题，进程服务按优先级高的先服务 * 优先级相同的先到先服务的原则管理，优先级用数值0~40表示 * 约定0为最高优先级，40为最低优先级 * */ public class PQueueText { public static void main(String[] args) { SeqPQueue myQueue = new SeqPQueue(); Element temp; try{ myQueue.append(new Element(new Integer(1),30)); myQueue.append(new Element(new Integer(2),20)); myQueue.append(new Element(new Integer(3),40)); myQueue.append(new Element(new Integer(4),20)); myQueue.append(new Element(new Integer(5),0)); System.out.println("进程号 优先级"); while(myQueue.notEmpty()){ temp = myQueue.delete(); System.out.print(temp.getElem()+" "); System.out.println(temp.getPriority()); } } catch(Exception e){ System.out.println(e.getMessage()); } } } /*进程号 优先级 5 0 2 20 4 20 1 30 3 40*/