priorityq.java

6个经典数据结构JAVA解法

/**
 * 优先级队列
 * 优先级队列中，数据项按关键字的值有序，这样关键字最小的数据项（或在某些实现中是
 * 关键字最大的数据项）总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列
 * 的顺序。
 */
class PriorityQ {
    private int maxSize;
    private long[] queArray;
    private int nItems;
    /**
     * 构建器（初始化队列的参数）
     * @param int s
     */
    public PriorityQ(int s) {
        maxSize = s;
        queArray = new long[maxSize];
        nItems = 0;
    }
    /**
     * 进入队列
     * @param long item
     */
    public void insert(long item) { // insert item
        int j;
        if (nItems == 0) {
            queArray[nItems++] = item; // if no items, insert at 0
        } 
        else { // if items,
            for (j=nItems-1; j>=0; j--) { // start at end,
                if (item>queArray[j]) {
                    queArray[j+1] = queArray[j]; // shift upward
                } else {
                    break; // done shifting
                } // end if-else
            } // end for
            queArray[j+1] = item;
            nItems++;
        } // end else (nItems > 0)
    } // end insert()
    /**
     * 离开队列
     */
    public long remove() { // remove minimum item
        return queArray[--nItems];
    }
    /**
     * 前端数据
     */
    public long peekMin() { // peek at minimum item
        return queArray[nItems-1];
    }
     /**
     * 是否为空
     */
    public boolean isEmpty() { // true if queue is empty
        return (nItems == 0);
    }
    /**
     * 是否满
     */
    public boolean isFull() { // true if queue is full
        return (nItems == maxSize);
    }
    /**
     * 主函数，测试。
     * @param String[] args
     */
    public static void main(String[] args) {
        PriorityQ thePQ = new PriorityQ(5);
        while (!thePQ.isFull()) {
        thePQ.insert(30);
        thePQ.insert(50);
        thePQ.insert(10);
        thePQ.insert(40);
        thePQ.insert(20);
        }
        while (!thePQ.isEmpty()) {
            long item = thePQ.remove();
            System.out.print(item + " "); // 10, 20, 30, 40, 50
        } // end while
        System.out.println("");
    } // end main()
} // end class PriorityQ