正在删除优先级队列的尾部元素

Question

如何删除优先级队列的尾部元素？我正在尝试使用优先级队列实现波束搜索，一旦优先级队列满了，我想删除最后一个元素(具有最低优先级的元素)。

谢谢!

Answer 1

没有简单的方法。将图元从原始复制到新的，最后一个除外。

PriorityQueue removelast(PriorityQueue pq)
{

    PriorityQueue pqnew;

    while(pq.size() > 1)
    {
        pqnew.add(pq.poll());
    }

    pq.clear();
    return pqnew;
}

调用为

pq = removelast(pq);

Answer 2

您可能可以使用Guava的MinMaxPriorityQueue来完成此任务。它为队列两端提供了peek、poll和remove方法。

另一种选择是编写一个队列包装器来强制绑定，类似于this answer。您需要实现offer、add和addAll来检查容量。类似于：

public class BoundedQueue<E> implements Serializable, Iterable<E>, Collection<E>, Queue<E> {
    private final Queue<E> queue;
    private int capacity;

    public BoundedQueue(Queue<E> queue, int capacity) {
        this.queue = queue;
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E o) {
        if (queue.size() >= capacity)
            return false;
        return queue.add(o);
    }

    @Override
    public boolean add(E o) throws IllegalStateException {
        if (queue.size() >= capacity)
            throw new IllegalStateException("Queue full"); // same behavior as java.util.ArrayBlockingQueue
        return queue.add(o);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        boolean changed = false;
        for (E o: c)
            changed |= add(o);
        return changed;
    }

    // All other methods simply delegate to 'queue'
}

Answer 3

使用倒置比较器，从头上取下。如果你同时需要头部和尾部，那么你使用了错误的数据结构。