優先級隊列
如果我們給每個元素都分配一個數字來標記其優先級，不妨設較小的數字具有較高的優先級，這樣我們就可以在一個集合中訪問優先級最高的元素并對其進行查找和刪除操作了。這樣，我們就引入了優先級隊列 這種數據結構。 優先級隊列（priority queue） 是0個或多個元素的集合，每個元素都有一個優先權，對優先級隊列執行的操作有（1）查找（2）插入一個新元素 （3）刪除 一般情況下，查找操作用來搜索優先權最大的元素，刪除操作用來刪除該元素 。對于優先權相同的元素，可按先進先出次序處理或按任意優先權進行。
Java數組模擬隊列
隊列是一種特殊的線性表，它只允許在表的前端進行刪除操作，而在表的后端進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。這也就是我們平常經常用說到的先進先出原則（FIFO）。Java 中的 List 就可以作為隊列來使用，在隊列尾部添加元素則使用 list.add 方法，從隊列頭部刪除元素則使用 list.remove 方法。
Java數組模擬優先級隊列結構實例:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
package datastruct; import java.util.Arrays; import java.util.Comparator; /** * 用數組模擬 優先級隊列 優先級高的排前、先出 線性表結構 * 類似使用了比較器的 TreeSet、TreeMap */public class SimulatePriorityQueue { public static void main(String[] args) { SimulatePriorityQueue queue = new SimulatePriorityQueue(4); // SimulateQueue queue = new SimulateQueue(); // System.out.println("取出元素：" + queue.remove()); queue.insert(1); queue.insert(3); queue.insert(2); queue.insert(5); queue.insert(4); System.out.println("size:" + queue.size()); System.out.println("peek:" + queue.peek()); System.out.println("取出元素：" + queue.remove()); System.out.println("取出元素：" + queue.remove()); System.out.println("取出元素：" + queue.remove()); System.out.println("取出元素：" + queue.remove()); // System.out.println("取出元素：" + queue.remove()); System.out.println("size:" + queue.size()); System.out.println(); } private int mSize = 3; //大小 private int[] mArray; //數組 private int mNextItem; //下一個位置，也可當作 當前的元素數 public SimulatePriorityQueue() { mArray = new int[mSize]; mNextItem = 0; } public SimulatePriorityQueue(int size) { this.mSize = size; mArray = new int[mSize]; mNextItem = 0; } /** * 插入元素 * @param item */ public void insert(int item) { if (!isFull()) { mArray[mNextItem++] = item; for (int i = 0; i < mNextItem; i++) {//冒泡排序 for (int j = 0; j < mNextItem - 1; j++) { if (mArray[j] > mArray[j + 1]) { mArray[j] = mArray[j + 1] + 0 * (mArray[j + 1] = mArray[j]); System.out.println(Arrays.toString(mArray)); } } } System.out.println(Arrays.toString(mArray)); } else { System.out.println("----不能插入元素了，隊列已滿----"); } } /** * 移出元素 先進先出 * @return */ public int remove() { if (!isEmpty()) { return mArray[--mNextItem]; } else { throw new IllegalArgumentException("沒有元素可以取出了"); } } /** * 查看前面的元素 * @return */ public int peek() { return mArray[mNextItem - 1]; } /** * 是否為空 * @return */ public boolean isEmpty() { return mNextItem == 0; } /** * 是否滿 * @return */ public boolean isFull() { return mNextItem == mSize; } /** * size * @return */ public int size() { return mNextItem; } } |
輸出結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
[1, 0, 0, 0][1, 3, 0, 0][1, 2, 3, 0][1, 2, 3, 0][1, 2, 3, 5]----不能插入元素了，隊列已滿----size:4peek:5取出元素：5取出元素：3取出元素：2取出元素：1size:0 |
