java 具有动态优先级标志的队列

Question

我需要建立一个队列，默认情况下，元素将按时间顺序添加和删除。但是如果客户端为队列设置了优先级标志，我需要能够根据元素的优先级顺序拉取元素。

我正在考虑创建一个由地图支持的优先级队列，该地图按优先级顺序跟踪队列索引，并且基于优先级标志，我可以从地图中提取项目并从队列中的索引中弹出项目。

但是使用这种方法的问题是，天气我默认创建地图或仅在设置标志时创建地图（考虑到在飞行中创建地图的成本很高，我倾向于默认使用它） .

如果有更好的方法或者是否存在现有的实现，请告诉我。

这是我目前拥有的：

import javax.naming.OperationNotSupportedException;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

public class DynamicPriorityQueue<ComparableQueueElement> implements IQueue<ComparableQueueElement> {

    private static final int CONSTANT_HUNDRED = 100;
    private boolean fetchByCustomPriority = false;
    private final ReentrantLock lock;
    private final PriorityQueue<ComparableQueueElement> queue;
    private final PriorityQueue<ComparableQueueElement> customPriorityQueue;

    public DynamicPriorityQueue() {
        this(null);
    }

    public DynamicPriorityQueue(Comparator<ComparableQueueElement> comparator) {
        this.lock = new ReentrantLock();
        this.queue = new PriorityQueue<>(CONSTANT_HUNDRED);
        if (comparator != null)
            this.customPriorityQueue = new PriorityQueue<ComparableQueueElement>(CONSTANT_HUNDRED, comparator);
        else
            this.customPriorityQueue = null;
    }

    public void setFetchByCustomPriority(boolean fetchByCustomPriority) throws OperationNotSupportedException {
        if (this.customPriorityQueue == null)
            throw new OperationNotSupportedException("Object was created without a custom comparator.");

        this.fetchByCustomPriority = fetchByCustomPriority;
    }

    public void push(ComparableQueueElement t) throws InterruptedException {
        if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) {
            try {
                this.queue.offer(t);
                if (this.customPriorityQueue != null)
                    this.customPriorityQueue.offer(t);
            } finally {
                this.lock.unlock();
            }
        }
    }

    public ComparableQueueElement peek() {
        return this.fetchByCustomPriority ? this.queue.peek()
                : (this.customPriorityQueue != null ? this.customPriorityQueue.peek() : null);
    }

    public ComparableQueueElement pop() throws InterruptedException {
        ComparableQueueElement returnElement = null;
        if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) {
            try {
                if (this.fetchByCustomPriority && this.customPriorityQueue != null) {
                    returnElement = this.customPriorityQueue.poll();
                    this.queue.remove(returnElement);
                }
                else {
                    returnElement = this.queue.poll();
                    if (this.customPriorityQueue != null) {
                        this.customPriorityQueue.remove(returnElement);
                    }
                }
            } finally {
                this.lock.unlock();
            }
        }
        return returnElement;
    }
}

Answer 1

我在重新阅读问题后删除了我的评论，它可能会变得复杂。您需要将 fifo（时间顺序）队列转换为带有标志的优先级队列。您的地图需要进行排序并能够保存重复值。否则，您将需要搜索地图以找到最高优先级或搜索队列。我才不会呢

编辑

使用包装怎么样class:

class Pointer<T>{
    T element
}

还有两个指针队列，其中队列共享指针但它们 return 不同？您唯一需要做的就是检查 "element" 是否不为空（当它离开其中一个队列时将其设置为空。

指针引用保留在另一个队列中，但您在 returning 之前检查是否为 null。

编辑

您的代码没有地图。

public ComparableQueueElement peek() {
        return this.fetchByCustomPriority ? this.queue.peek()
                : (this.customPriorityQueue != null ? this.customPriorityQueue.peek() : null);
    }

不正确。如果不是习惯，你应该从 this.queue

偷看

编辑

请注意，通过使用包装 class，您可以将删除调用保存在另一个队列中。唯一增加的开销是你需要在获取时检查 null

Answer 2

对我来说，如果您的应用程序要求标志经常更改，那么实现看起来不错。在这种情况下，您有两个队列都准备好提供或从队列中轮询对象。虽然它使您的添加操作很繁重，但检索速度很快。

但是如果这些变化不频繁那么你可以考虑仅在标志变化时从FIFO队列重新初始化自定义优先级队列。并仅在一个队列而不是两个队列上执行所有的 peek、offer 操作。如果使用 FIFO 优先级，效率会更高。如果你这样做修改你的推送操作如下 -

public void push(ComparableQueueElement t) throws InterruptedException {
    if (this.lock.tryLock(CONSTANT_HUNDRED, TimeUnit.MILLISECONDS)) {
        try {
            this.queue.offer(t);
            if (this.fetchByCustomPriority) // add to customPriorityQueue only when flag is enabled
                this.customPriorityQueue.offer(t);
        } finally {
            this.lock.unlock();
        }
    }
}

java 具有动态优先级标志的队列

java queue with dynamic priority flag

java

multithreading

priority-queue

data-structures