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

Question

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

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

但是，使用这种方法的问题是，我是否默认创建 map ，或者仅在设置了标志的情况下创建 map (考虑到动态创建 map 的成本很高，我倾向于默认情况下创建 map )。

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

这是我目前拥有的:

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(时间顺序)队列转换为带有标志的优先级队列。您的 map 需要进行排序并且能够保存重复的值。否则，您将需要搜索 map 以找到最高优先级或搜索队列。我不会这么做。

编辑

使用包装类怎么样:

class Pointer<T>{
    T element
}

还有两个指针队列，其中队列共享指针，但它们返回的指针不同？您需要做的唯一一件事是检查“element”是否不为空(当它离开队列之一时将其设置为空。

指针引用保留在另一个队列中，但在返回之前检查是否为空。

编辑

您的代码没有 map 。

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

不正确。如果不是自定义的，你应该从 this.queue 中查看

编辑

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