优先级队列
如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了优先级队列 这种数据结构。 优先级队列（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:4
peek:5
取出元素：5
取出元素：3
取出元素：2
取出元素：1
size:0
|