java 如何实现一个用来只读,一个用来只写的队列,要是有优先级高的,优先读取,优先级低的在读队列中只存在一次
时间: 2024-03-10 17:43:14 浏览: 100
Java优先队列的实现
Java中可以通过自定义数据结构实现一个只读、只写的队列,并且可以考虑加入优先级的特性。
首先,我们可以定义一个Node类,用于存储队列中的元素,其中包含value和priority两个属性:
```java
class Node<T> {
T value;
int priority;
Node(T v, int p) {
value = v;
priority = p;
}
}
```
然后,我们可以定义一个Queue类,用于存储元素和实现队列的操作,其中包含两个LinkedList,一个用于存储只读的元素,一个用于存储只写的元素。同时,我们可以定义一个add方法,用于向只写的队列中添加元素,并且保证只添加一次:
```java
import java.util.*;
class Queue<T> {
private LinkedList<Node<T>> readOnlyQueue;
private LinkedList<Node<T>> writeOnlyQueue;
private Set<T> uniqueSet;
Queue() {
readOnlyQueue = new LinkedList<>();
writeOnlyQueue = new LinkedList<>();
uniqueSet = new HashSet<>();
}
void add(T value, int priority) {
if (!uniqueSet.contains(value)) {
writeOnlyQueue.add(new Node<>(value, priority));
uniqueSet.add(value);
}
}
// 其他操作(如read、peek等)省略
}
```
有了只写的队列之后,我们可以在读取元素时添加一个优先级的特性。可以在读取时先遍历只读队列,如果队列为空,则从只写队列中取出最大优先级的元素,进行读取。如下所示:
```java
import java.util.*;
class Queue<T> {
private LinkedList<Node<T>> readOnlyQueue;
private LinkedList<Node<T>> writeOnlyQueue;
private Set<T> uniqueSet;
Queue() {
readOnlyQueue = new LinkedList<>();
writeOnlyQueue = new LinkedList<>();
uniqueSet = new HashSet<>();
}
void add(T value, int priority) {
if (!uniqueSet.contains(value)) {
writeOnlyQueue.add(new Node<>(value, priority));
uniqueSet.add(value);
}
}
T read() {
if (!readOnlyQueue.isEmpty()) {
return readOnlyQueue.poll().value;
} else if (!writeOnlyQueue.isEmpty()) {
// 获取最高优先级
int maxPriority = Integer.MIN_VALUE;
for (Node<T> node : writeOnlyQueue) {
if (node.priority > maxPriority) {
maxPriority = node.priority;
}
}
// 取出最高优先级的元素
Iterator<Node<T>> it = writeOnlyQueue.iterator();
while (it.hasNext()) {
Node<T> node = it.next();
if (node.priority == maxPriority) {
it.remove();
readOnlyQueue.add(node);
uniqueSet.remove(node.value);
return node.value;
}
}
}
return null;
}
// 其他操作(如peek等)省略
}
```
这样,我们就可以实现一个只读、只写的队列,并且可以加入优先级的特性,满足题目要求。
阅读全文