java数据结构与算法-优先级队列

一、优先级队列

/**
 * Created by Xi on 2017/7/29.
 * 优先级队列，及队列中的元素是有顺序的。跟普通队列相比，主要是插入元素时，需找到对应的位置才能插。
 */

public class PriorQueue {
    private long[] queArray;
    private int maxSize;//队列最大值
    private int nItems;//以有元素总数
    public PriorQueue(int size){//用户指定队列最大数
        maxSize=size;
        queArray=new long[maxSize];
        nItems=0;
    }

    /**
     * 插入元素，调用该接口之前需判断队列是否已满。
     */
    public void insert(long element){
        int loc;//要插入的位置
        if(nItems==0){//队列为空，没有元素
            queArray[nItems++]=element;
        }else{//以有元素，需要找对应的位置
            for(loc=nItems-1;loc>=0;loc--){//开始循环，从上往下找，
                if(element>queArray[loc]){//未找到，将元素上移
                    queArray[loc+1]=queArray[loc];// 2
                }else{
                    break;
                }
            }
            queArray[loc+1]=element;//由于loc位置有元素，而且loc+1位置的元素以通过上述2处上移，所以直接插入
            nItems++;
        }
    }

    /**
     * 删除元素，调用该接口之前需判断队列是否有元素
     */
    public long remove(){
        return queArray[--nItems];
    }

    /**
     * 访问元素
     */
    public long peekMin(){
        return queArray[nItems-1];
    }

    /**
     * 队列是否为空
     */
    public boolean isEmpty(){
        return nItems==0;
    }

    /**
     * 判断队列是否以满
     */
    public boolean isFull(){
        return nItems==maxSize;
    }
}

二、调用函数如下

/**
     * 优先级队列
     */
    private void queuePrior() {
        int size = 3;
        PriorQueue queue = new PriorQueue(size);
        if (!queue.isFull()) queue.insert(10);//插入元素
        if (!queue.isFull()) queue.insert(40);
        if (!queue.isFull()) queue.insert(20);
        if (!queue.isFull()) queue.insert(30);

        while (!queue.isEmpty()) {//移除元素
            long remove = queue.remove();
            Log.v(TAG, "被移除的元素为：" + remove);
        }
        if (!queue.isFull()) queue.insert(70);
        if (!queue.isFull()) queue.insert(80);
        if (!queue.isEmpty()) {//取出元素
            long l = queue.peekMin();
            Log.v(TAG, "看到的元素为：" + l);
        }
    }

打印日志如下：

08-14 18:25:32.295 9687-9687/com.tool.wpn.quicksort V/MainActivity: 被移除的元素为：10
08-14 18:25:32.297 9687-9687/com.tool.wpn.quicksort V/MainActivity: 被移除的元素为：20
08-14 18:25:32.297 9687-9687/com.tool.wpn.quicksort V/MainActivity: 被移除的元素为：40
08-14 18:25:32.301 9687-9687/com.tool.wpn.quicksort V/MainActivity: 看到的元素为：70

源码下载地址：点击打开链接