数据结构Java实现——队列的“奇葩”二 优先级队列

写在前面

有很多时候，一些数据的存储不仅需要先进先出，而且还有根据数据的优先级来排序，也就是优先级高的一定先出去，优先级相同的先进先出，此时就会用到优先级队列

应用

其实优先级队列的应用十分广泛，比如说构造哈夫曼树算法，再比如在一些计算机操作系统中用优先级队列来来满足抢先式多任务操作系统等等等等

代码实现

1、优先级队列存储的数据元素的描述

package org.Stone6762.entity;

/**
 * @ClassName_PriorityQData优先级队列的结点中的数据部分的描述
 * @author_Stone6762
 * @CreationTime_2015年1月2日 下午3:39:55
 * @Description_
 */
public class PriorityQData {

	/**@data该节点的数据部分
	 */
	private Object data;
	
	/**@priority该结点的优先级
	 */
	private int priority;

	/**　@Title构造器
	 */
	public PriorityQData(Object data, int priority) {
		super();
		this.data = data;
		this.priority = priority;
	}

	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

	public int getPriority() {
		return priority;
	}

	public void setPriority(int priority) {
		this.priority = priority;
	}

}

2、优先级队列的实现

package org.Stone6762.MQueue.imple;

import org.Stone6762.MQueue.MQueue;
import org.Stone6762.entity.Node;
import org.Stone6762.entity.PriorityQData;

/**
 * @ClassName_PriorityQueue优先级队列
 * @author_Stone6762
 * @CreationTime_2015年1月2日 下午3:42:55
 * @Description_
 */
public class PriorityQueue implements MQueue {

	/**
	 * @front指向队首元素
	 */
	private Node front;

	/**
	 * @rear指向队尾元素
	 */
	private Node rear;

	/**
	 * @bigFront优先级队列的存储顺序_默认的是队首小
	 */
	private boolean bigFront;

	/**
	 * 　@Title构造器
	 */
	public PriorityQueue(boolean bigFront) {
		this();
		this.bigFront = bigFront;
	}

	public PriorityQueue() {
		this.front = this.rear = null;
	}

	@Override
	public void clear() {
		this.front = this.rear = null;
	}

	@Override
	public boolean isEmpty() {

		return this.front == null;
	}

	@Override
	public int length() {
		Node t = this.front;
		int length = 0;
		while (t != null) {
			length++;
			t = t.getNext();
		}
		return length;
	}

	@Override
	public Object peek() {
		if (front != null) {
			return front.getData();
		}
		return null;
	}

	@Override
	public void offer(Object data) throws Exception {

		PriorityQData tData = (PriorityQData) data;
		Node newNode = new Node(tData);
		if (front == null) {// 对第一个元素进行特殊处理
			front = rear = newNode;
		} else {

			// 1.根据优先级找到要插入的合适的位置
			Node currNode = front, lastNode = front;

			if (!bigFront) {
				while (currNode != null
						&& tData.getPriority() >= ((PriorityQData) currNode
								.getData()).getPriority()) {
					lastNode = currNode;
					currNode = currNode.getNext();
				}// -----------跳出循环有两种情况，一，到了队尾，二，找到了合适的位置
			} else {
				while (currNode != null
						&& tData.getPriority() <= ((PriorityQData) currNode
								.getData()).getPriority()) {
					lastNode = currNode;
					currNode = currNode.getNext();
				}// -----------跳出循环有两种情况，一，到了队尾，二，找到了合适的位置
			}

			// 2.对插入的位置进行分类讨论
			if (currNode == null) {// 该结点应该插在队尾
				rear.setNext(newNode);
				rear = newNode;
			} else if (currNode == front) {// 该结点应该插在队首
				newNode.setNext(front);
				front = newNode;
			} else {// 该结点在队中间的某一位置
				newNode.setNext(currNode);
				lastNode.setNext(newNode);
			}
		}
	}

	@Override
	public Object poll() {

		if (front != null) {
			Node t = front;
			front = front.getNext();
			return t;
		}
		return null;
	}

	public void disPly() {
		if (front != null) {
			Node t = front;
			while (t != null) {
				PriorityQData temp = (PriorityQData) t.getData();
				System.out.println("  "+temp.getData() + "       "
						+ temp.getPriority());
				t = t.getNext();
			}
		} else {
			System.out.println("队列为空！！");
		}
	}

}