優(yōu)先級隊列
如果我們給每個元素都分配一個數(shù)字來標記其優(yōu)先級，不妨設較小的數(shù)字具有較高的優(yōu)先級，這樣我們就可以在一個集合中訪問優(yōu)先級最高的元素并對其進行查找和刪除操作了。這樣，我們就引入了優(yōu)先級隊列 這種數(shù)據(jù)結構。 優(yōu)先級隊列（priority queue） 是0個或多個元素的集合，每個元素都有一個優(yōu)先權，對優(yōu)先級隊列執(zhí)行的操作有（1）查找（2）插入一個新元素 （3）刪除 一般情況下，查找操作用來搜索優(yōu)先權最大的元素，刪除操作用來刪除該元素 。對于優(yōu)先權相同的元素，可按先進先出次序處理或按任意優(yōu)先權進行。
Java數(shù)組模擬隊列
隊列是一種特殊的線性表，它只允許在表的前端進行刪除操作，而在表的后端進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。這也就是我們平常經常用說到的先進先出原則（FIFO）。Java 中的 List 就可以作為隊列來使用，在隊列尾部添加元素則使用 list.add 方法，從隊列頭部刪除元素則使用 list.remove 方法。
Java數(shù)組模擬優(yōu)先級隊列結構實例:
|
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; /** * 用數(shù)組模擬 優(yōu)先級隊列 優(yōu)先級高的排前、先出 線性表結構 * 類似使用了比較器的 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; //數(shù)組 private int mNextItem; //下一個位置，也可當作 當前的元素數(shù) 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 |
