優先隊列(存儲結構數組)--Java實作

1 /*優先隊列--是對隊列的一種改進
 2  *要存儲的資料存在優先級--數值小的優先級高--在隊頭
 3  *優先隊列的實作
 4  *1.數組：适合資料量小的情況(沒有用rear+front實作)
 5  *優先隊列頭在items-1,隊列尾在0是固定的
 6  *2.堆：适合資料量大的情況
 7  *優先隊列的效率：插入O(N)移除O(1)
 8  *優先隊列的應用：作業系統線程排程算法
 9  * */
10 public class MyPriorityQueue {
11     private int maxSize;
12     private long[] arr;//插入的時候保證有序
13     private int items;
14     
15     public MyPriorityQueue(int s) {
16         maxSize = s;
17         arr = new long[maxSize];
18         items = 0;
19     }
20     
21     public void insert(long key){
22         int j;
23         if(items == 0){//為空直接加入
24             arr[items++] = key;
25         }
26         else{//不為空就将小元素方在最上面--隊列頭
27             for(j = items-1;j >= 0;j--){
28                 if(key > arr[j]){
29                     arr[j+1] = arr[j];
30                 }
31                 else{
32                     break;
33                 }
34             }
35             arr[j+1] = key;
36             items++;
37         }
38     }
39     
40     public long remove(){
41         return arr[--items];
42     }
43     
44     public boolean isEmpty(){
45         return items == 0;
46     }
47     
48     public boolean isFull(){
49         return items == maxSize;
50     }
51     
52     public long getPeekMin(){
53         return arr[items -1];
54     }
55     
56     public void diaplayPQ(){
57         for(int i = items- 1;i >= 0;i--){
58             System.out.print(arr[i] + " ");
59         }
60         System.out.println();
61     }
62 }